論文の概要: A Relativizing MIP for BQP

• arxiv url: http://arxiv.org/abs/2604.11952v1
• Date: Mon, 13 Apr 2026 18:45:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-15 19:11:32.066743
• Title: A Relativizing MIP for BQP
• Title（参考訳）: BQPのための相対化MIP
• Authors: Scott Aaronson, Anand Natarajan, Avishay Tal, Agi Villanyi,
• Abstract要約: 例えば、$mathsfBQP subseteq mathsfMIP$ は任意の古典的オラクルに対して成り立つことを示す。 我々は、証明効率のプロキシとして相対化を提案し、オラクルの世界における$mathsfBQP$の$mathsfIP$への進展が、非暗号化対話プロトコルに繋がることを期待している。
• 参考スコア（独自算出の注目度）: 2.060642030400714
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Complexity class containments involving interactive proof classes are famously nonrelativizing: although $\mathsf{IP} = \mathsf{PSPACE}$, Fortnow and Sipser showed that that there exists an oracle relative to which $\mathsf{coNP} \not\subseteq \mathsf{IP}$. In contrast, the question of whether the containment $\mathsf{BQP} \subseteq \mathsf{IP}$ is relativizing remains wide open. In this work we make progress towards resolving this question by showing that the containment $\mathsf{BQP} \subseteq \mathsf{MIP}$ holds with respect to any classical oracle. We obtain this result by constructing, for any classical oracle $O$, a $\mathsf{PCP}$ proof system for $\mathsf{BQP}^{O}$ where the verifier makes polynomially many classical queries to an exponentially-long proof, and to the oracle $O$. Our construction is inspired by the state synthesis algorithm of Grover and Rudolph, and serves as a complement to the "exponential PCP" constructed by Aharonov, Arad, and Vidick, which achieves similar parameters but which is based on different ideas and does not relativize. We propose relativization as a proxy for prover efficiency, and hope that progress towards an $\mathsf{IP}$ for $\mathsf{BQP}$ in the oracle world will lead to a non-cryptographic interactive protocol for proving any quantum computation to a classical skeptic in the unrelativized world, which is a longstanding open problem in quantum complexity theory.
• Abstract（参考訳）: しかし、$\mathsf{IP} = \mathsf{PSPACE}$, Fortnow and Sipser は、$\mathsf{coNP} \not\subseteq \mathsf{IP}$ に対してオラクルが存在することを示した。 これとは対照的に、$\mathsf{BQP} \subseteq \mathsf{IP}$ の包含に関する問題は広く開である。 本研究では、この問題の解決に向けて、古典的なオラクルに対して $\mathsf{BQP} \subseteq \mathsf{MIP}$ が成り立つことを示す。 この結果は、任意の古典的オラクル$O$に対して$\mathsf{BQP}^{O}$の証明システムを構築して得られる。 我々の構成はGroverとRudolphの状態合成アルゴリズムに着想を得ており、Aharonov, Arad, Vidickによって構築された「指数PCP」を補完する役割を果たしている。 我々は、証明効率のプロキシとして相対化を提案し、オラクル世界では$\mathsf{IP}$ for $\mathsf{BQP}$への進歩が、量子複雑性理論における長年のオープンな問題である非相対化世界の古典的懐疑者に量子計算を証明するための非暗号的対話プロトコルをもたらすことを期待する。

関連論文リスト

• Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability [85.07238533644636]
  $Phi$-equilibriaは、オンライン学習とゲーム理論の中心にある、強力で柔軟なフレームワークだ。 効率的なオンラインアルゴリズムは、$textpoly(d, k)/epsilon2$ラウンドを使用して、平均$Phi$-regretを最大$epsilon$で生成することを示す。 また、オンライン設定において、ほぼ一致した下限を示し、その結果、$Phi$-regretの学習可能性を取得する偏差の族が初めて得られる。
  論文  参考訳（メタデータ） (2025-02-25T19:08:26Z)
• Classical versus quantum queries in quantum PCPs with classical proofs [0.3004066195320147]
  量子古典PCPを一般化し、古典的な証明に$q$の量子クエリを適用できるようにします。 驚くべきことに、このことは、定数量子古典量に対して逆から定数への約束のギャップを増幅できることを示している。 約束のギャップは達成できるが、我々の結果は、$mathsfQCMA$に対する定型クエリ量子古典的PCPが存在しないという強い証拠を与える。
  論文  参考訳（メタデータ） (2024-11-01T18:00:56Z)
• A Fast Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [55.2480439325792]
  多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。 本稿では,差分に基づく探索法 (CombGapE) アルゴリズムを提案する。 我々は,CombGapEアルゴリズムが,合成データセットと実世界のデータセットの両方において,既存の手法を大幅に上回っていることを数値的に示す。
  論文  参考訳（メタデータ） (2023-06-15T15:37:31Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  浅量子回路の計算能力と古典計算の組合せを包括的に評価する。 いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
  論文  参考訳（メタデータ） (2022-10-12T17:54:02Z)
• An optimal oracle separation of classical and quantum hybrid schemes [0.0]
  任意の深さパラメータ$d$に対して、計算時間古典が許されるとき、量子深さ$d$と2d+1$を分離するオラクルが存在することを示す。 これは古典的および量子的ハイブリッドスキームの最適オラクル分離を与える。
  論文  参考訳（メタデータ） (2022-05-10T02:31:19Z)
• 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)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
  論文  参考訳（メタデータ） (2022-03-17T23:52:08Z)
• The Acrobatics of BQP [1.7136832159667206]
  量子時間(mathsfBQP$)の挙動をブラックボックスで設定すると、$mathsfNP$のような古典的な複雑性クラスと著しく分離できることが示される。 また、独立した関心を持つかもしれない新しいツールも導入します。 ランダム制限法の「量子対応」バージョン、$mathsfAC0$回路のブロック感度に対する集中定理、スパースオークスに対するアーロンソン・アンバイニス・コンジェクチャの(証明可能な)アナログを含む。
  論文  参考訳（メタデータ） (2021-11-19T19:40:05Z)
• On the complexity of zero gap MIP* [0.11470070927586014]
  クラス $mathsfMIP*$ が $mathsfRE$ に等しいことを示す。 特にこのことは、非局所ゲーム$G$の量子値の近似の複雑さがハルティング問題の複雑性と同値であることを示している。
  論文  参考訳（メタデータ） (2020-02-24T19:11:01Z)

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

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