論文の概要: Unentangled stoquastic Merlin-Arthur proof systems: the power of unentanglement without destructive interference

• arxiv url: http://arxiv.org/abs/2604.27886v1
• Date: Thu, 30 Apr 2026 14:04:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-01 16:31:54.123467
• Title: Unentangled stoquastic Merlin-Arthur proof systems: the power of unentanglement without destructive interference
• Title（参考訳）: 絡み合う確率的メルリン・アーサー証明系:破壊的干渉のない絡み合いの力
• Authors: Yupan Liu, Pei Wu,
• Abstract要約: Sf StoqMA(2)$ は非絡み合いのメルリン・アーサー証明系のクラスである。 $sf StoqMA(2)$は半量子であり、$sf MA$に崩壊することもあるが、$sf StoqMA(2)$は驚くほど強力である。
• 参考スコア（独自算出の注目度）: 0.5586191108738564
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Stoquasticity, originating in sign-problem-free physical systems, gives rise to $\sf StoqMA$, introduced by Bravyi, Bessen, and Terhal (2006), a quantum-inspired intermediate class between $\sf MA$ and $\sf AM$. Unentanglement similarly gives rise to ${\sf QMA}(2)$, introduced by Kobayashi, Matsumoto, and Yamakami (CJTCS 2009), which generalizes $\sf QMA$ to two unentangled proofs and still has only the trivial $\sf NEXP$ upper bound. In this work, we initiate a systematic study of the power of unentanglement without destructive interference via ${\sf StoqMA}(2)$, the class of unentangled stoquastic Merlin-Arthur proof systems. Although $\sf StoqMA$ is semi-quantum and may collapse to $\sf MA$, ${\sf StoqMA}(2)$ turns out to be surprisingly powerful. We establish the following results: - ${\sf NP} \subseteq {\sf StoqMA}(2)$ with $\widetilde{O}(\sqrt{n})$-qubit proofs and completeness error $2^{-{\rm polylog}(n)}$. Conversely, ${\sf StoqMA}(2) \subseteq {\sf EXP}$ via the Sum-of-Squares algorithm of Barak, Kelner, and Steurer (STOC 2014); with our lower bound, our refined analysis yields the optimality of this algorithm under ETH. - ${\sf StoqMA}(2)_1 \subseteq {\sf PSPACE}$, and the containment holds with completeness error $2^{-2^{{\rm poly}(n)}}$. - ${\sf PreciseStoqMA}(2)$, a variant of ${\sf StoqMA}(2)$ with exponentially small promise gap, cannot achieve perfect completeness unless ${\sf EXP}={\sf NEXP}$. In contrast, ${\sf PreciseStoqMA}$ achieves perfect completeness, since ${\sf PSPACE} \subseteq {\sf PreciseStoqMA}_1$. - When the completeness error is negligible, ${\sf StoqMA}(k) = {\sf StoqMA}(2)$ for $k\geq 2$. Our lower bounds are obtained by stoquastizing the short-proof ${\sf QMA}(2)$ protocols via distribution testing techniques. Our upper bounds for the nearly perfect completeness case are proved via our new rectangular closure testing framework.
• Abstract（参考訳）: Stoquasticity (Stoquasticity) は符号プロブレムのない物理系に由来するもので、Bravyi, Bessen, and Terhal (2006) によって導入された$\sf StoqMA$, $\sf MA$ と $\sf AM$ の中間クラスである。 同様にアンタングル化は、小林、松本、山上(CJTCS 2009)によって導入された${\sf QMA}(2)$を生じさせ、これは、$\sf QMA$を2つのアンタングル証明に一般化し、それでも自明な$\sf NEXP$上界しか持たない。 本研究では, 絡み合ったメルリン・アーサー証明系のクラスである${\sf StoqMA}(2)$を介して, 破壊的干渉を伴わない非絡み合いのパワーの系統的研究を開始する。 $\sf StoqMA$は半量子であり、$\sf MA$, ${\sf StoqMA}(2)$は驚くほど強力である。 ${\sf NP} \subseteq {\sf StoqMA}(2)$ with $\widetilde{O}(\sqrt{n})$-qubit proofs and completeness error $2^{-{\rm polylog}(n)}$。 逆に、${\sf StoqMA}(2) \subseteq {\sf EXP}$ は Barak,Kelner,Steurer (STOC 2014) の Sum-of-Squares アルゴリズムを介して行われる。 -${\sf StoqMA}(2)_1 \subseteq {\sf PSPACE}$, and the containment holded with completeness error $2^{-2^{{\rm poly}(n)}}$。 -${\sf PreciseStoqMA}(2)$, ${\sf StoqMA}(2)$の変種で指数的に小さな約束ギャップを持つが、${\sf EXP}={\sf NEXP}$がなければ完全な完全性は達成できない。 対照的に${\sf PreciseStoqMA}$は、${\sf PSPACE} \subseteq {\sf PreciseStoqMA}_1$であるから、完全性を達成する。 - 完全性エラーが無視されるとき、${\sf StoqMA}(k) = {\sf StoqMA}(2)$ for $k\geq 2$。 我々の下限は、分布試験手法による短文${\sf QMA}(2)$プロトコルの確率化によって得られる。 ほぼ完全な完全性の場合の上限は、新しい長方形クロージャ試験フレームワークによって証明される。

関連論文リスト

• ${\sf QMA}={\sf QMA}_1$ with an infinite counter [0.5064404027153093]
  sf QMA=sf QMAinfty=sf QMA_1inftyを示す。 完全性を増幅するだけで、音性ではなく、以前の$sf QMA$アンプよりもはるかに少ない時間で、$sf QMA$アンプが得られます。 我々の新しい構成は、元の検証子とその逆数に対する$O(1)$呼び出しと$O(log q)$他のゲートを使用して、完全性1-2-q$を達成する。
  論文  参考訳（メタデータ） (2025-06-18T15:23:40Z)
• Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs [54.28273395444243]
  我々は,モノトニック値 Omega (MVP) アルゴリズムが,差分を考慮した差分依存残差境界を$tildeOleft(left(sum_Delta_h(s,a)>0 fracH2 log K land MathttVar_maxtextc$。
  論文  参考訳（メタデータ） (2025-06-06T20:33:57Z)
• On the $O(\frac{\sqrt{d}}{K^{1/4}})$ Convergence Rate of AdamW Measured by $\ell_1$ Norm [52.95596504632859]
  本稿では、$ell_1$ノルムで測定されたAdamWに対して、収束速度 $frac1Ksum_k=1KEleft[||nabla f(xk)||_1right]leq O(fracsqrtdCK1/4)$を確立する。 結果は、二重モーメント機構を用いたAdamW変種であるNAdamWに拡張し、同じ収束率を維持していることを示す。
  論文  参考訳（メタデータ） (2025-05-17T05:02:52Z)
• Space-bounded quantum interactive proof systems [2.623117146922531]
  空間有界量子対話型証明システムの2つのモデル、$sf QIPL$と$sf QIP_rm UL$を紹介する。 一方、$sf QIPL$は検証動作毎に多数のピンチ中間測度を対数的に許容する。
  論文  参考訳（メタデータ） (2024-10-31T14:11:08Z)
• 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)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• The planted matching problem: Sharp threshold and infinite-order phase transition [25.41713098167692]
  ランダムに重み付けされた$ntimes n$ bipartite graphに隠された完全マッチング$M*$を再構築する問題について検討する。 任意の小さな定数 $epsilon>0$ に対して $sqrtd B(mathcalP,mathcalQ) ge 1+epsilon$ が成り立つ場合、任意の推定値の再構築誤差は $0$ から有界であることが示される。
  論文  参考訳（メタデータ） (2021-03-17T00:59:33Z)
• StoqMA meets distribution testing [0.0]
  We provide a novel connection between $mathsfStoqMA$ and distribution testing via reversible circuits。 いずれの変種も$mathsfStoqMA$は、任意の無作為な乱数ビットと完全音性を持たず、$mathsfNP$に含まれることを示す。 我々の結果は、$mathsfMA subseteq mathsfStoqMA subseteq mathsfSBP$ [BBT06]という階層構造を崩壊させる一歩を踏み出した。
  論文  参考訳（メタデータ） (2020-11-11T12:30:42Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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