論文の概要: Quantum Advantage with Sign-Free Proofs: An Oracle Separation between $\mathsf{StoqMA}$ and $\mathsf{MA}$
- arxiv url: http://arxiv.org/abs/2611.08180v1
- Date: Thu, 05 Nov 2026 15:34:43 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-07 04:55:13.565344
- Title: Quantum Advantage with Sign-Free Proofs: An Oracle Separation between $\mathsf{StoqMA}$ and $\mathsf{MA}$
- Title（参考訳）: 符号なし証明による量子アドバンテージ:$\mathsf{StoqMA}$と$\mathsf{MA}$の間のOracle分離
- Abstract要約: 最小限の量子資源は、すべての古典的検証器より優れていることを示す。
我々の分離問題は、隣接リストのオラクルを介して与えられるスパース高密度グラフが、大きなあるいは小さなペロン−フロベニウス固有値を持つかどうかを決定することである。
- 参考スコア（独自算出の注目度）: 0.6308539010172308
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Several landmark oracle results (FOCS 2000, FOCS 2025, STOC 2026) establish strict separations along the chain $\mathsf{MA} \subseteq \mathsf{QCMA} \subseteq \mathsf{QMA}$, showing that quantum verification and quantum witnesses can each provide additional power over classical proof systems. These separations, however, use substantial coherent quantum computation, often through the quantum Fourier transform. We prove that a minimal quantum resource already suffices to outperform every classical verifier. Namely, we show the separation $$\mathsf{MA} \subsetneq \mathsf{StoqMA}$$ relative to a classical oracle. The class $\mathsf{StoqMA}$, introduced by Bravyi, Bessen, and Terhal (arXiv 2006), restricts the verifier to classical reversible computation, followed by a single Hadamard-basis measurement. Its power is closely tied to the complexity of stoquastic Hamiltonians, a sign-problem-free and seemingly more tractable class of quantum Hamiltonians. Our separating problem is to determine whether a sparse high-girth graph, given via an adjacency-list oracle, has a large or small Perron--Frobenius eigenvalue. This amounts to a ground-energy estimation task for a related stoquastic Hamiltonian. Our construction builds on a line of work on graph exploration problems with exponential quantum speedups, from welded trees (STOC 2003) to recent constructions (STOC 2021, arXiv 2026).
- Abstract（参考訳）: いくつかのランドマークオラクルの結果 (FOCS 2000, FOCS 2025, STOC 2026) は、チェーン $\mathsf{MA} \subseteq \mathsf{QCMA} \subseteq \mathsf{QMA}$ に沿って厳密な分離を確立し、量子検証と量子目撃者がそれぞれ古典的な証明システムにさらなるパワーを与えることを示した。
しかし、これらの分離は、しばしば量子フーリエ変換を通じて、かなりのコヒーレントな量子計算を使用する。
我々は、最小限の量子資源が全ての古典的検証器より優れていることを証明している。
すなわち、古典的なオラクルに対して$$\mathsf{MA} \subsetneq \mathsf{StoqMA}$$の分離を示す。
Bravyi, Bessen, and Terhal (arXiv 2006) によって導入されたクラス $\mathsf{StoqMA}$ は、検証器を古典的可逆計算に制限し、その後に1つのアダマール・ベイズ測度が続く。
量子ハミルトニアン(英: quantum Hamiltonians)は、量子ハミルトニアン(英語版)(量子ハミルトニアン)の複雑性と密接に結びついている。
我々の分離問題は、隣接リストのオラクルを介して与えられるスパース高密度グラフが、大きなあるいは小さなペロン−フロベニウス固有値を持つかどうかを決定することである。
これは関連する確率的ハミルトニアンに対する基底エネルギー推定タスクに相当する。
本研究は, 溶接木 (STOC 2003) から最近の構造 (STOC 2021, arXiv 2026) まで, 指数量子スピードアップによるグラフ探索問題に関する一連の研究に基づいている。
関連論文リスト
- Verifiable quantum advantage in extremely low depth [52.51019642214249]
浅量子回路では解けない問題を格子ベースの仮定で解くのが困難である。
浅量子回路は、解を効率よく検証できる古典的な難題を解くのに十分な構造を持っていることを証明している。
論文 参考訳（メタデータ） (2026-09-01T15:54:34Z) - Collapses in quantum-classical probabilistically checkable proofs and the quantum polynomial hierarchy [0.7321157455672144]
証明に特有の量子古典的PCPの制限は、そのパワーを低下させるものではないことを示す。
また、カルプ・リプトンの定理の非一様量子類似性も証明する。
これらの結果は、量子証明システムの構造に関する新たな洞察を与える。
論文 参考訳（メタデータ） (2025-06-24T16:59:50Z) - Exponential improvement in quantum simulations of bosons [0.22399170518036918]
デジタル量子コンピュータ上のボソンのハミルトン量子シミュレーションでは、ヒルベルト空間を有限次元に切り離す必要がある。
ヤン=ミルズ理論やQCDのような格子量子論では、いくつかのハミルトンの定式化と対応するトランケーションが近年進行している。
3人の著者によって提唱された普遍的枠組みは、回路複雑性の指数的スケーリングを$Q$で解決する自然な方法であることを示す。
論文 参考訳（メタデータ） (2025-05-05T10:48:52Z) - Classical versus quantum queries in quantum PCPs with classical proofs [0.3004066195320147]
量子古典PCPを一般化し、古典的な証明に$q$の量子クエリを適用できるようにします。
驚くべきことに、このことは、定数量子古典量に対して逆から定数への約束のギャップを増幅できることを示している。
約束のギャップは達成できるが、我々の結果は、$mathsfQCMA$に対する定型クエリ量子古典的PCPが存在しないという強い証拠を与える。
論文 参考訳（メタデータ） (2024-11-01T18:00:56Z) - On the complexity of unique quantum witnesses and quantum approximate counting [2.4475760284813255]
量子オラクルを$mathsfBQPmathsfUniqueQMA$と$mathsfQMA$で分離する。
局所ハミルトン問題のどんな構造的特性を活用できるのか?
局所ハミルトンの基底エネルギーを$mathsfUniqueQMA$プロトコルで推定できることを示すことによって、物理的動機付けの候補を導入する。
論文 参考訳（メタデータ） (2024-10-31T10:53:51Z) - The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。
特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。
QMA(2) が $textQMA+(2)$ に等しいことを示す。
論文 参考訳（メタデータ） (2024-02-29T01:35:46Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳（メタデータ） (2022-01-31T22:19:49Z) - Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
量子計算の2つのモデル: CQ_dとQC_d。
CQ_dは、d-d-deepth量子コンピュータのシナリオを何度も捉え、QC_dは測定ベースの量子計算に類似している。
CQ_dとQC_dの類似性にもかかわらず、2つのモデルは本質的にはCQ_d $nsubseteq$QC_dとQC_d $nsubseteq$CQ_dである。
論文 参考訳（メタデータ） (2022-01-06T03:10:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。