論文の概要: Quantum Speedups Require Structure or Depth

• arxiv url: http://arxiv.org/abs/2608.19158v1
• Date: Wed, 19 Aug 2026 17:42:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-20 20:13:55.480949
• Title: Quantum Speedups Require Structure or Depth
• Title（参考訳）: 量子スピードアップは構造や深さを必要とする
• Abstract要約: すべての$t$-query $d$-round量子アルゴリズムが、$tO(d2)$古典的なクエリでほとんどの入力でシミュレート可能であることを示す。 非構造問題に対して、超多項式スピードアップは超定常深さの量子回路を必要とし、指数的なスピードアップはさらに深さを必要とする。
• 参考スコア（独自算出の注目度）: 6.942576237126963
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: One of the most basic conjectures in quantum complexity theory states that every $t$-query quantum algorithm can be simulated on most inputs by a $\mathrm{poly}(t)$-query classical algorithm. If true, this would provide broad justification for the need for structure in quantum speedups. We settle this conjecture for parallel quantum algorithms, showing that every $t$-query $d$-round quantum algorithm can be simulated on most inputs with $t^{O(d^2)}$ classical queries. This suggests that for unstructured problems, superpolynomial speedups would require quantum circuits of superconstant depth, and exponential speedups would further require polynomial depth. In contrast, most known speedups for structured problems are achieved by highly parallel, low-depth algorithms. Our techniques also carry new implications for the status of $\mathsf{BPP}$ vs. $\mathsf{BQP}$ relative to a random oracle, a similarly longstanding problem.
• Abstract（参考訳）: 量子複雑性理論における最も基本的な予想の一つは、全ての$t$-query量子アルゴリズムが$\mathrm{poly}(t)$-query古典アルゴリズムによってほとんどの入力でシミュレートできるということである。 もし本当なら、これは量子スピードアップの構造の必要性を広く正当化するものである。 並列量子アルゴリズムのこの予想は、すべての$t$-query $d$-round量子アルゴリズムが、$t^{O(d^2)}$古典的なクエリでほとんどの入力でシミュレート可能であることを示す。 これは、非構造的な問題に対して、超多項式的なスピードアップは超定常深さの量子回路を必要とし、指数的なスピードアップはさらに多項式深さを必要とすることを示唆している。 対照的に、構造化された問題に対する最もよく知られたスピードアップは、高並列で低深度なアルゴリズムによって達成される。 我々の手法は、同様に長く続く問題であるランダムオラクルに対して、$\mathsf{BPP}$ vs. $\mathsf{BQP}$のステータスに対する新しい意味を持つ。

関連論文リスト

• Parallel Quantum Advantage with Limited Adaptivity Requires Structure [2.6546344072296084]
  我々はAaronsonとAmbainisの予想を証明し、量子クエリアルゴリズムが古典的なシミュレーションをほぼすべての場所に含んでいることを証明した。 指数量子スピードアップは十分に構造化された入力でのみ可能であることを示す。 我々の主な技術的貢献は、密分布から引き出されたオラクルにオラクル上の一様分布を関連付ける結合定理である。
  論文  参考訳（メタデータ） (2026-08-20T17:37:03Z)
• Limitation of Quantum Walk Approach to the Maximum Matching Problem [0.0]
  最大マッチング問題は、隣接行列で表される$n$頂点上のグラフに対して$Omega(n3/2)$以下の量子クエリ複雑性を持つ。 現在の最良の量子アルゴリズムは、クエリ複雑性$O(n7/4)$であり、これは自明な有界な$O(n2)$に対する改善である。 量子ウォーク法は、既知の(あるいは自明な)上界をクエリの複雑さで改善する高速なアルゴリズムを作成できないことを示す。
  論文  参考訳（メタデータ） (2025-10-30T08:29:44Z)
• Learning quantum states prepared by shallow circuits in polynomial time [1.127500169412367]
  有限次元格子上に$vertpsirangle$を作成する定数深さ量子回路を学習する。 このアルゴリズムは、$U$の深さが$mathrmpolylog(n)$であり、準多項式実行時である場合に拡張される。 応用として、格子上の未知の量子状態が量子回路の複雑さが低いか高いかをテストするための効率的なアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2024-10-31T04:12:49Z)
• 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)
• Quantum Speedups for Bayesian Network Structure Learning [12.02309220445177]
  ノードが$n$のネットワークの場合、最も高速な既知のアルゴリズムは、最悪の場合は$O(2nn2)$で実行され、20年で改善はない。 量子コンピューティングの最近の進歩に触発されて、ある定数$c$が2ドル以下であれば、時間$O(cn)$で量子アルゴリズムによって解けるかどうかを問う。
  論文  参考訳（メタデータ） (2023-05-31T09:15:28Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。 我々は距離の計算を高速化するために量子現象を利用する。 我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
  論文  参考訳（メタデータ） (2022-12-13T16:04:16Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  浅量子回路の計算能力と古典計算の組合せを包括的に評価する。 いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
  論文  参考訳（メタデータ） (2022-10-12T17:54:02Z)
• 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)
• Limits of quantum speed-ups for computational geometry and other problems: Fine-grained complexity via quantum walks [0.0]
  いくつかの計算問題に対して、量子アルゴリズムの時間的複雑さを最適に下界として証明する。 我々の下界のほとんどは、既知の上界と一致しているため、量子スピードアップに厳しい制限が課せられるため、最適である。
  論文  参考訳（メタデータ） (2021-06-03T17:22:08Z)
• Quantum Algorithm for Fidelity Estimation [8.270684567157987]
  2つの未知の混合量子状態 $rho$ と $sigma$ に対して、それらの忠実度 $F(rho,sigma)$ は基本的な問題である。 我々は、この問題を$namepoly(log (N), r, 1/varepsilon)$ timeで解く量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-03-16T13:57:01Z)
• 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)

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

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