論文の概要: $\mathsf{BQP} \subseteq \mathsf{IP}$ Does Not Relativize
- arxiv url: http://arxiv.org/abs/2609.25680v1
- Date: Tue, 22 Sep 2026 04:34:07 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-23 18:04:04.224481
- Title: $\mathsf{BQP} \subseteq \mathsf{IP}$ Does Not Relativize
- Title（参考訳）: $\mathsf{BQP} \subseteq \mathsf{IP}$ Don Not Relativize
- Abstract要約: 我々は、$mathsfBQPnotsubseteqmathsfIP$ に関するオラクルを構築し、量子複雑性理論における長年の未解決問題を解決する。
我々の結果は、$mathsfBQP$の証明効率の良い古典的対話プロトコルは、非相対化技術に頼らなければならないことを示唆している。
- 参考スコア（独自算出の注目度）: 0.767122984156099
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We construct an oracle relative to which $\mathsf{BQP} \not\subseteq \mathsf{IP}$, resolving a long-standing open question in quantum complexity theory. Together with recent work due to Aaronson et al., our work also gives the first oracle separation between $\mathsf{IP}$ and $\mathsf{MIP}$, answering a question dating back to Fortnow's thesis. Our separation is based on the Forrelation problem, where given Boolean functions $f$ and $g$, the goal is to determine if $f$ is correlated with the Fourier spectrum of $g$. While this task is solvable by a query-efficient quantum algorithm, we show that it admits no classical interactive protocol with polynomial communication and a polynomial-query verifier. Our proof is based on (i) a new structural result showing how to approximate Avg-Max circuits (which are well-known to capture the power of interactive proofs in the oracular setting) by convex functions with small first and second derivatives and (ii) a novel analysis establishing that the Forrelation distribution suggested by Aaronson and Ambainis fools such functions. Our results imply that any prover-efficient classical interactive protocol for $\mathsf{BQP}$ must rely on non-relativizing techniques. This might serve as a partial explanation for the lack of progress towards doubly-efficient, unconditionally sound classical verification of quantum computation.
- Abstract（参考訳）: 我々は、量子複雑性理論における長年の未解決問題を解決するために、 $\mathsf{BQP} \not\subseteq \mathsf{IP}$ に関するオラクルを構築する。
Aaronsonらによる最近の研究とともに、我々の研究は$\mathsf{IP}$と$\mathsf{MIP}$の間の最初のオラクル分離を与え、Fortnowの論文に遡る質問に答える。
我々の分離は Forrelation 問題に基づいており、 Boolean 関数 $f$ と $g$ が与えられたとき、$f$ が $g$ のフーリエスペクトルと相関しているかどうかを決定することが目的である。
このタスクは、クエリ効率のよい量子アルゴリズムで解けるが、多項式通信と多項式クエリ検証を伴う古典的な対話プロトコルは認めていない。
私たちの証明は
(i)Avg-Max回路を小さな第一導関数と第二導関数の凸関数によって近似する方法を示す新しい構造結果。
(二)アーロンソンとアムバイニスが示唆する有意関係分布がそのような機能を騙すという新たな分析。
我々の結果は、$\mathsf{BQP}$の証明効率のよい古典的対話プロトコルは、非相対化技術に頼らなければならないことを示唆している。
これは、量子計算の2倍効率で無条件の古典的検証への進歩の欠如を部分的に説明するのに役立つかもしれない。
関連論文リスト
- Quantum-Classical Equivalence for AND-Functions [4.0075720392218335]
量子通信複雑性の大きな問題は、量子プロトコルが古典的プロトコルよりも指数関数的に効率的であるかどうかである。
各ブール関数$f$に対して、有界エラー量子および古典的通信複雑性は決定論的に関連していることを示す。
論文 参考訳（メタデータ） (2026-06-02T07:10:16Z) - A Relativizing MIP for BQP [2.060642030400714]
例えば、$mathsfBQP subseteq mathsfMIP$ は任意の古典的オラクルに対して成り立つことを示す。
我々は、証明効率のプロキシとして相対化を提案し、オラクルの世界における$mathsfBQP$の$mathsfIP$への進展が、非暗号化対話プロトコルに繋がることを期待している。
論文 参考訳（メタデータ） (2026-04-13T18:45:12Z) - Fourier Spectrum of Noisy Quantum Algorithms [0.0]
量子アルゴリズムに作用する雑音は、ノイズの種類と複雑に結びついている方法でフーリエ成長を阻害することを示す。
特に,2-Forrelationと3-Forrelationは,それぞれ$mathsfDQC_k$と$frac12mathsfBQP$モデルで,$NOmega(1)$クエリを必要とすることを示す。
論文 参考訳（メタデータ） (2025-10-07T19:07:59Z) - Forrelation is Extremally Hard [0.0]
フォルレレーション問題(Forrelation problem)は、量子能力と古典的能力の指数的分離を示す中心的な問題である。
この問題を1つの量子クエリと成功確率1で解くことができるが、$tildeOmegaleft (2n/4right)$ classical randomized queryが必要である。
論文 参考訳（メタデータ） (2025-08-04T15:19:19Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
量子順序付き二項決定図($OBDD$)モデルについて検討する。
入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。
read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
論文 参考訳（メタデータ） (2022-04-22T12:37:56Z) - A Law of Robustness beyond Isoperimetry [84.33752026418045]
我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。
次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。
我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
論文 参考訳（メタデータ） (2022-02-23T16:10:23Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳（メタデータ） (2022-01-31T22:19:49Z) - Classical algorithms for Forrelation [2.624902795082451]
1対の$n$-bit Boolean 関数 $f$ と $g$ が与えられたとき、$f$ と $g$ のフーリエ変換の間の相関を推定する。
この問題は、クエリの複雑さの観点から最大の量子スピードアップをもたらすことが知られている。
グラフに基づく回帰問題は、任意の二部グラフに対して時間$O(n)$で解けることを示す。
論文 参考訳（メタデータ） (2021-02-13T17:25:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。