Fugu-MT 論文翻訳(概要): QMA(2) with Limited Shared Entanglement

論文の概要: QMA(2) with Limited Shared Entanglement

arxiv url: http://arxiv.org/abs/2609.39668v1
Date: Wed, 30 Sep 2026 13:04:57 GMT
ステータス: 翻訳完了
システム内更新日: 2026-10-01 18:57:27.803849
Title: QMA(2) with Limited Shared Entanglement
Title（参考訳）: 限定共有絡み付きQMA(2)
Abstract要約: $mathsfQMA(2)$プロトコルは、H時間量子検証器に無絡証人を提出する2つのプローバーを含む。我々は$mathsfQMA(2)$のパワーが、対数的に多くの共有EPRペアに対して変わらないことを示す。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: A $\mathsf{QMA}(2)$ protocol involves two provers submitting unentangled witnesses to a polynomial-time quantum verifier. In The Power of Unentanglement (ToC, 2009), Aaronson et al. proposed $\mathsf{QMA}(2;h)$, a variant of $\mathsf{QMA}(2)$ in which the two provers may share $h$ EPR pairs. Our main result shows that the power of $\mathsf{QMA}(2)$ remains unchanged for up to logarithmically many shared EPR pairs: $\mathsf{QMA}(2;h)=\mathsf{QMA}(2)$ for $h=O(\log n)$, where $n$ is the input length. The result follows from a simulation using four unentangled witnesses, combined with the Harrow-Montanaro equality $\mathsf{QMA}(4)=\mathsf{QMA}(2)$ (FOCS, 2010). We also prove monotonicity in the EPR budget: $\mathsf{QMA}(2;h)\subseteq\mathsf{QMA}(2;H)$ for $h\le H$, preserving completeness and soundness. Combined with input padding, this shows that establishing $\mathsf{QMA}(2;n^\varepsilon)=\mathsf{QMA}(2)$ for any fixed $\varepsilon>0$ would imply equality for every polynomially bounded budget, resolving the open problem raised by Aaronson et al. Finally, we extend these results to a variant of the model in which the provers may use local operations and classical communication (LOCC) during witness preparation. For logarithmic-size witnesses and inverse-polynomial gaps, both models remain equivalent to their unentangled counterpart when $h=O(\log n)$. We show that extending this equivalence to any superlogarithmic EPR budget in the LOCC model would imply $\mathsf{NP}\subseteq\mathsf{BQP}$.
Abstract（参考訳）: $\mathsf{QMA}(2)$プロトコルは、多項式時間量子検証器に無絡証人を提出する2つのプローバーを含む。 The Power of Unentanglement (ToC, 2009)において、アーロンソンらは$\mathsf{QMA}(2;h)$を提案した。我々の主な結果は、$\mathsf{QMA}(2)$のパワーが対数的に多くの共有EPRペアに対して変わらないことを示している: $\mathsf{QMA}(2;h)=\mathsf{QMA}(2)$ for $h=O(\log n)$。その結果は、4つの無絡証人を用いたシミュレーションと、Harrow-Montanaroの等式 $\mathsf{QMA}(4)=\mathsf{QMA}(2)$ (FOCS, 2010) との組み合わせによるものである。 EPR予算の単調性も証明する: $\mathsf{QMA}(2;h)\subseteq\mathsf{QMA}(2;H)$ for $h\le H$,serving completeness and soundness。入力パディングと組み合わせると、$\mathsf{QMA}(2;n^\varepsilon)=\mathsf{QMA}(2)$ for any fixed $\varepsilon>0$ would imply equality for every polynomially bounded budget,solving the open problem by Aaronson et al 最後に、これらの結果は、プローバーが証人準備中にローカル操作と古典的コミュニケーション(LOCC)を使用することができるモデルの変種に拡張されることを示す。対数サイズの目撃者や逆ポリノミカルギャップの場合、どちらのモデルも、$h=O(\log n)$のときのアンタングルと等価である。この等価性をLOCCモデルにおける任意の超対数的EPR予算に拡張すると、$\mathsf{NP}\subseteq\mathsf{BQP}$となる。

関連論文リスト

PureSuperQMA(exp) = BellPureSymQMA(poly) = QMA via Dimension-Free Bosonic Argmax [36.23068106699028]
純粋状態整合性問題は自然に量子証明システムにつながり、1人の証人が多くの受理制約を満たす必要がある。 $mathsfBellPureSymQMA(textpoly)$は、証明者が純粋状態の多くのコピーを検証しなければならない関連するモデルである。 k$-local pure-state consistency is $mathsfQMA$-complete for every fixed $kge2$, so is the exact bosonic and fermionic pure $N$-representability problem。
論文参考訳（メタデータ） (2026-09-10T17:37:22Z)
A quantum oracle separation between QMA(2) and QMA [0.9068953081227296]
量子相対は、$mathsfQMA neq mathsfQMA(2)$である。すべての$+1$に対して、任意の$(, symmetric)$-disentanglerは出力キュービット数で指数関数的な入力サイズを必要とする。
論文参考訳（メタデータ） (2026-09-02T17:50:05Z)
Near-Optimal Gap Amplification for Nonnegative Unentangled Quantum Proofs [0.0]
量子証明の非絡み合いを特徴とするクラス$mathsfQMA+(2)$のギャップ増幅について検討する。我々の証明は対称部分空間射影と$mathsfQMA+(1)=mathsfNEXP$ of Bassirian, Fefferman, Marwahaの関係を組み合わせる。
論文参考訳（メタデータ） (2026-08-08T07:45:56Z)
The Complexity of Stoquastic Sparse Hamiltonians [0.30079490585515334]
確率スパースハミルトン問題(mathsfStoqSH$)が$mathsfStoqMA$であることを示す。 Stoquastic Local Hamiltonian は $mathsfStoqMA$-hard であるため、$mathsfStoqSH$ は $mathsfStoqMA$-complete となる。また、$mathsfStoqMA(2)$の分離可能なバージョンが$mathsfStoqMAであることも示します。
論文参考訳（メタデータ） (2026-05-04T17:22:02Z)
The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文参考訳（メタデータ） (2024-10-26T06:21:42Z)
A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文参考訳（メタデータ） (2023-09-25T17:54:19Z)
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)
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)
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)

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

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