論文の概要: Dequantizing Short-Path Quantum Algorithms

• arxiv url: http://arxiv.org/abs/2604.12131v1
• Date: Mon, 13 Apr 2026 23:31:53 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-15 19:11:32.157763
• Title: Dequantizing Short-Path Quantum Algorithms
• Title（参考訳）: 短パルス量子アルゴリズムの定式化
• Authors: François Le Gall, Suguru Tamaki,
• Abstract要約: ショートパス量子アルゴリズム(英: Short-path quantum algorithm)は、アダイバティック量子アルゴリズムの一種。 制約満足度問題に対するショートパス量子アルゴリズムは超二次的優位性を達成できないことを示す。
• 参考スコア（独自算出の注目度）: 1.1602089225841632
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The short-path quantum algorithm introduced by Hastings (Quantum 2018, 2019) is a variant of adiabatic quantum algorithms that enables an easier worst-case analysis by avoiding the need to control the spectral gap along a long adiabatic path. Dalzell, Pancotti, Campbell, and Brandão (STOC 2023) recently revisited this framework and obtained a clear analysis of the complexity of the short-path algorithm for several classes of constraint satisfaction problems (MAX-$k$-CSPs), leading to quantum algorithms with complexity $2^{(1-c)n/2}$ for some constant $c>0$. This suggested a super-quadratic quantum advantage over classical algorithms. In this work, we identify an explicit classical mechanism underlying a substantial part of this line of work, and show that it leads to clean dequantizations. As a consequence, we obtain classical algorithms that run in time $2^{(1-c')n}$, for some constant $c'>c$, for the same classes of constraint satisfaction problems. This shows that current short-path quantum algorithms for these problems do not achieve a super-quadratic advantage. On the positive side, our results provide a new ``quantum-inspired'' approach to designing classical algorithms for important classes of constraint satisfaction problems.
• Abstract（参考訳）: Hastingsによって導入されたショートパス量子アルゴリズム(Quantum 2018, 2019)は、長い断熱経路に沿ったスペクトルギャップを制御する必要性を回避し、より簡単な最悪のケース分析を可能にする断熱量子アルゴリズムの変種である。 Dalzell, Pancotti, Campbell, and Brandão (STOC 2023) はこのフレームワークを再検討し、いくつかの制約満足度問題 (MAX-$k$-CSPs) に対するショートパスアルゴリズムの複雑さを明確に解析し、いくつかの定数$c>0$に対して複雑性が 2^{(1-c)n/2}$ となる。 これは古典的アルゴリズムよりも超四進法的な量子優位性を示している。 本研究では,この研究の根底にある明示的な古典的メカニズムを同定し,清潔な復調につながることを示す。 その結果、制約満足度の同じクラスに対して、ある一定の$c'>c$に対して2^{(1-c')n}$で走る古典的アルゴリズムを得る。 このことは、これらの問題に対する現在のショートパス量子アルゴリズムが超二次的優位性を達成できないことを示している。 その結果,制約満足度問題の重要なクラスに対して,古典的アルゴリズムを設計するための<quantum-inspired' アプローチが得られた。

関連論文リスト

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• Quantum algorithms for Hopcroft's problem [45.45456673484445]
  計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。 この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。 我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
  論文  参考訳（メタデータ） (2024-05-02T10:29:06Z)
• Making the cut: two methods for breaking down a quantum algorithm [0.0]
  現在、ノイズの多い小規模量子ハードウェアの時代において、計算上の優位性に達する可能性のある量子アルゴリズムを見つけることは、依然として大きな課題である。 我々は、量子アルゴリズムを低い(クエリ)深さのラウンドに分解する2つの方法を特定し、特徴付ける。 最初の問題では並列化が最高のパフォーマンスを提供するのに対し、2番目はより良い選択であることを示す。
  論文  参考訳（メタデータ） (2023-05-17T18:00:06Z)
• Experimentally demonstrating indefinite causal order algorithms to solve the generalized Deutsch's problem [4.555392897705548]
  Deutschのアルゴリズムは、古典的アルゴリズムよりも優位性を示す最初の量子アルゴリズムである。 この問題を解決するために、不明確な因果順序を持つ新しい量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-05-09T13:04:28Z)
• Recovering the original simplicity: succinct and deterministic quantum algorithm for the welded tree problem [0.0]
  この研究は、よく知られた溶接木問題に対する量子アルゴリズムを再考する。 最も単純な量子ウォークに基づく非常に簡潔な量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-04-17T16:03:50Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。 このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。 また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
  論文  参考訳（メタデータ） (2022-12-03T02:45:23Z)
• A single $T$-gate makes distribution learning hard [56.045224655472865]
  この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。 ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
  論文  参考訳（メタデータ） (2022-07-07T08:04:15Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。