論文の概要: Parallel Quantum Advantage with Limited Adaptivity Requires Structure
- arxiv url: http://arxiv.org/abs/2608.20297v1
- Date: Thu, 20 Aug 2026 17:37:03 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-21 20:28:51.661476
- Title: Parallel Quantum Advantage with Limited Adaptivity Requires Structure
- Title（参考訳）: 限定適応性を持つ並列量子アドバンテージは構造を必要とする
- Abstract要約: 我々はAaronsonとAmbainisの予想を証明し、量子クエリアルゴリズムが古典的なシミュレーションをほぼすべての場所に含んでいることを証明した。
指数量子スピードアップは十分に構造化された入力でのみ可能であることを示す。
我々の主な技術的貢献は、密分布から引き出されたオラクルにオラクル上の一様分布を関連付ける結合定理である。
- 参考スコア（独自算出の注目度）: 2.6546344072296084
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Aaronson and Ambainis (Theory of Computing, 2014) conjectured that quantum query algorithms admit efficient almost-everywhere classical simulation: for any $T$-query quantum algorithm, its acceptance probability can be approximated on a $(1-δ)$ fraction of inputs, up to $ε$ additive error, using $\mathrm{poly}(T, 1/ε, 1/δ)$ classical queries. At a high level, the conjecture suggests that exponential quantum speedups are possible only on sufficiently structured inputs. In this work, we make progress on this conjecture by proving it for quantum algorithms that make massively parallel quantum queries. In contrast, Yamakawa and Zhandry (Journal of the ACM, 2024) showed that quantum algorithms restricted to parallel queries can still achieve exponential speedups over classical algorithms for sampling problems. We establish our simulation theorem by proving the stronger statement that parallel-query quantum algorithms cannot distinguish the uniform distribution over oracles from oracles drawn from so-called "dense distributions". Our main technical contribution is a coupling theorem that relates the uniform distribution over oracles to oracles drawn from dense distributions. We further extend this approach beyond the purely parallel setting, obtaining simulation theorems both for algorithms with a bounded quantum-query prefix followed by a massively parallel quantum-query stage, and for hybrid algorithms that make an arbitrary polynomial number of adaptive classical queries before the massively parallel quantum-query stage. Finally, using the parallel-query simulation theorem as a base case, we obtain simulation theorems for quantum algorithms with constant rounds of adaptivity.
- Abstract（参考訳）: Aaronson and Ambainis (Theory of Computing, 2014) は、量子クエリアルゴリズムが全ての古典的シミュレーションを効率的に行うことができると予測した:任意の$T$-query量子アルゴリズムの場合、その受容確率は$(1-δ)$の入力の分数で近似でき、$\mathrm{poly}(T, 1/ε, 1/δ)$の古典的クエリを使って$ε$加法誤差が与えられる。
高いレベルでは、指数量子スピードアップは十分に構造化された入力でのみ可能であると推測される。
本研究では,超並列な量子クエリを生成する量子アルゴリズムに対して,これを証明することによって,この予想を推し進める。
対照的に、山川とZhandry(ACMのジャーナル、2024年)は、並列クエリに制限された量子アルゴリズムは、サンプリング問題に対する古典的アルゴリズムよりも指数的なスピードアップを達成できることを示した。
我々は,並列暗号量子アルゴリズムが,いわゆる「高密度分布」から引き出されたオラクルと,オラクル上の均一分布を区別できないという強い主張を証明し,シミュレーション定理を確立した。
我々の主な技術的貢献は、密分布から引き出されたオラクルにオラクル上の一様分布を関連付ける結合定理である。
さらに、このアプローチは純粋に並列的な設定を超えて拡張され、有界な量子クエリプレフィックスを持つアルゴリズムと、超並列な量子クエリを持つアルゴリズムと、超並列な量子クエリの前の任意の多項式数を生成するハイブリッドアルゴリズムの両方に対してシミュレーション定理が得られた。
最後に、並列キューシミュレーションの定理を基本ケースとして、適応性の一定のラウンドを持つ量子アルゴリズムのシミュレーション定理を得る。
関連論文リスト
- Verifiable quantum advantage in extremely low depth [52.51019642214249]
浅量子回路では解けない問題を格子ベースの仮定で解くのが困難である。
浅量子回路は、解を効率よく検証できる古典的な難題を解くのに十分な構造を持っていることを証明している。
論文 参考訳（メタデータ） (2026-09-01T15:54:34Z) - Quantum Speedups Require Structure or Depth [6.942576237126963]
すべての$t$-query $d$-round量子アルゴリズムが、$tO(d2)$古典的なクエリでほとんどの入力でシミュレート可能であることを示す。
非構造問題に対して、超多項式スピードアップは超定常深さの量子回路を必要とし、指数的なスピードアップはさらに深さを必要とする。
論文 参考訳（メタデータ） (2026-08-19T17:42:10Z) - Quantum multi-row iteration algorithm for linear systems with non-square coefficient matrices [7.174256268278207]
古典的マルチロー反復法に着想を得た量子アルゴリズムを提案する。
本アルゴリズムは,不整合系の解法に適した係数行列の要求を小さくする。
論文 参考訳（メタデータ） (2024-09-06T03:32:02Z) - The Power of Adaptivity in Quantum Query Algorithms [0.5702169790677977]
問合せモデルにおける深度計算のトレードオフについて検討し、その深さは適応的な問合せラウンドの数と1ラウンド当たりの並列クエリ数に対応する。
我々は、量子アルゴリズム間の最も強力な分離を$r$対$r-1$の適応性を持つラウンドで達成する。
論文 参考訳（メタデータ） (2023-11-27T18:21:32Z) - A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games [95.50895904060309]
最適行列乗算重み更新(OMMWU)アルゴリズムを導入し,平均収束複雑性を$mathcalO(d/epsilon)$ to $epsilon$-Nash equilibriaとする。
この二次的なスピードアップは、量子ゼロサムゲームにおける$epsilon$-Nash平衡の計算のための新しいベンチマークを定めている。
論文 参考訳（メタデータ） (2023-11-17T20:38:38Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。
我々は距離の計算を高速化するために量子現象を利用する。
我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
論文 参考訳（メタデータ） (2022-12-13T16:04:16Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳（メタデータ） (2022-09-28T17:53:25Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Quantifying Grover speed-ups beyond asymptotic analysis [0.0]
古典的なエミュレーションと、すべての定数を含む詳細な複雑性境界を組み合わせたアプローチを考える。
本手法を古典的アルゴリズムの単純量子スピードアップに適用し,よく研究されたMAX-$k$-SAT最適化問題を解く。
これは、2つの重要な量子サブルーチンの期待と最悪のケースの複雑さに厳密な境界(全定数を含む)を必要とする。
論文 参考訳（メタデータ） (2022-03-09T19:00:00Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。
我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。
我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文 参考訳（メタデータ） (2020-04-14T11:05:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。