論文の概要: PureSuperQMA(exp) = BellPureSymQMA(poly) = QMA via Dimension-Free Bosonic Argmax
- arxiv url: http://arxiv.org/abs/2609.11854v1
- Date: Thu, 10 Sep 2026 17:37:22 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-11 23:53:35.459006
- Title: PureSuperQMA(exp) = BellPureSymQMA(poly) = QMA via Dimension-Free Bosonic Argmax
- Title（参考訳）: PureSuperQMA(exp) = BellPureSymQMA(poly) = QMA via Dimension-free Bosonic Argmax
- Abstract要約: 純粋状態整合性問題は自然に量子証明システムにつながり、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。
- 参考スコア（独自算出の注目度）: 36.23068106699028
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Pure-state consistency problems naturally lead to quantum proof systems in which a single pure witness must satisfy many acceptance constraints. The corresponding class $\mathsf{PureSuperQMA}$ was previously known to lie between $\mathsf{QMA}$ and $\mathsf{QMA}(2)$, and Kamminga and Rudolph (ITCS'26) conjectured that both containments are strict. In this paper, we prove the following surprising complexity collapses $$ \mathsf{QMA} = \mathsf{PureSuperQMA} = \mathsf{PureSuperQMA}(\text{exp}) = \mathsf{BellPureSymQMA}(\text{poly}) $$ Here $\mathsf{PureSuperQMA}(\text{exp})$ allows exponentially many checks which are uniformly indexed and efficiently generated, while requiring an inverse-polynomial violation margin and an inverse-polynomial fraction of violated checks for the NO cases. $\mathsf{BellPureSymQMA}(\text{poly})$ is a related model that requires the prover to give the verifier polynomially many copies of a pure state, which the verifier measures separately with logarithmic output length for each local measurement, before processing the outcomes jointly. The main technical ingredient is a dimension-free stability bound for symmetric tensor states. Our simulations use polynomially many witness registers and combine a random-pair SWAP test with a permutation-invariant lift of the original verification procedure. The key step is to show that, on the symmetric subspace, the extremal verification value is close to that of some tensor-power witness with dimension-independent error. Applying this argument to the two verification models yields both simulations. As a consequence, exact $k$-local pure-state consistency is $\mathsf{QMA}$-complete for every fixed $k\ge2$, and so are the corresponding exact bosonic and fermionic pure $N$-representability problems.
- Abstract（参考訳）: 純粋状態整合性問題は自然に量子証明システムにつながり、単一の純粋証人は多くの受理制約を満たさなければならない。
対応するクラス $\mathsf{PureSuperQMA}$ は、以前は $\mathsf{QMA}$ と $\mathsf{QMA}(2)$ の間にあり、Kamminga と Rudolph (ITCS'26) はどちらも厳密であると予想していた。
本稿では、以下の驚くべき複雑性の崩壊を証明した:$$ \mathsf{QMA} = \mathsf{PureSuperQMA}(\text{exp}) = \mathsf{BellPureSymQMA}(\text{poly})$$$$ $\mathsf{PureSuperQMA}(\text{exp})$は、一様にインデックス付けされ、効率よく生成された指数的に多くのチェックを許容するが、逆ポリノミカルな違反マージンと、NOの場合の逆ポリノミカルなチェックの逆ポリノミカルな割合を必要とする。
$\mathsf{BellPureSymQMA}(\text{poly})$は、証明者が純粋状態の多項式的に多くのコピーを与える必要がある関連するモデルである。
主な技術的要素は対称テンソル状態に対する次元自由安定性である。
シミュレーションでは、多項式的に多数の証人レジスタを使用し、ランダムペアのSWAPテストと元の検証手順の置換不変リフトを組み合わせる。
鍵となるステップは、対称部分空間において、極大検証値は次元に依存しない誤差を持つテンソルパワー証人のそれに近いことを示すことである。
この議論を2つの検証モデルに適用すると、両方のシミュレーションが得られる。
結果として、正確な$k$-ローカルな純状態一貫性は、すべての固定された$k\ge2$に対して$\mathsf{QMA}$-完全であり、従って対応する正のボソニックおよびフェルミオンな純粋な$N$-表現可能性問題である。
関連論文リスト
- A quantum oracle separation between QMA(2) and QMA [0.9068953081227296]
量子相対は、$mathsfQMA neq mathsfQMA(2)$である。
すべての$+1$に対して、任意の$(, symmetric)$-disentanglerは出力キュービット数で指数関数的な入力サイズを必要とする。
論文 参考訳（メタデータ） (2026-09-02T17:50:05Z) - An Argmax Principle for Sum-of-Squares Relaxations on the Sphere [42.540924632302925]
単位球面上の最適化問題の総和緩和を解析するためのargmax原理を開発する。
私たちの指導原則は、最大値が丸みを帯びた候補であることです。
論文 参考訳（メタデータ） (2026-08-03T17:58:00Z) - An Optimal Analysis of the Product Test [42.29010058743949]
製品テストは、純多部量子状態が特定のテンソル分解に完全に絡み合っているかどうかを決定する。
基本的なプロパティテストタスクであり、多くのアプリケーションがあるにもかかわらず、製品テストの正確な(最悪のケース)受け入れ確率曲線は、まだ完全には決定されていない。
複雑性理論の応用として,Harrow-Montanaro還元の1ショット音響パラメータを$mathsfQMA(k)$から$mathsfQMA(2)$に改善した。
論文 参考訳（メタデータ） (2026-07-23T16:17:44Z) - Faster quantum linear system solver beyond the condition number [50.84794327094274]
線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。
フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
論文 参考訳（メタデータ） (2026-07-08T17:49:40Z) - The Collapse of Unentangled Stoquastic Merlin-Arthur Proof Systems [46.657699628769336]
絡み合いと干渉は量子力学の最も基本的な性質の一つである。
我々は絡み合いが確率的検証に余分な力を与えないことを証明する。
論文 参考訳（メタデータ） (2026-05-15T17:52:33Z) - Hardness of High-Dimensional Linear Classification [58.29089693778071]
我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。
どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
論文 参考訳（メタデータ） (2026-03-19T15:53:41Z) - Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learning [51.820005667020354]
有限状態と作用空間を持つ平均回帰型MDPに対して、弱い通信仮定の下で、単純だが効果的なQ-ラーニングアルゴリズムについて検討する。
We proof that the collaborations the per-agent sample complexitys to $widetildeOleft(frac|mathcalA||hstar|_mathsfsp3Mvarepsilon3right)$, with only $widetildeOleft(frac|hstar|_mathsfsp3Mvareps)。
論文 参考訳（メタデータ） (2026-01-20T06:21:54Z) - Average-Case Complexity of Tensor Decomposition for Low-Degree
Polynomials [93.59919600451487]
多くの統計的推論タスクにおいて「統計計算ギャップ」が発生する。
1つの成分が他の成分よりもわずかに大きいランダムオーダー3分解モデルを考える。
テンソルエントリは$ll n3/2$のとき最大成分を正確に推定できるが、$rgg n3/2$のとき失敗する。
論文 参考訳（メタデータ） (2022-11-10T00:40:37Z) - Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
制約付き非線形最適化問題のオンライン統計的推測を考察する。
これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
論文 参考訳（メタデータ） (2022-05-27T00:34:03Z) - 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) - Statistical Query Lower Bounds for Tensor PCA [10.701091387118023]
Richard と Montanari が導入した PCA 問題では、$n$サンプル $mathbbEmathbfT_1:n$ of i.d. Perkins Gaussian tensors of order $k$ からなるデータセットが与えられ、$mathbbEmathbfT_1:n$ はランク 1 である。
目標は$mathbbE mathbfT_1$を見積もることである。
最適なサンプルの複雑さを鋭く分析する。
論文 参考訳（メタデータ） (2020-08-10T13:14:34Z) - Naive Exploration is Optimal for Online LQR [49.681825576239355]
最適後悔尺度は$widetildeTheta(sqrtd_mathbfu2 d_mathbfx T)$で、$T$は時間ステップの数、$d_mathbfu$は入力空間の次元、$d_mathbfx$はシステム状態の次元である。
我々の下界は、かつての$mathrmpoly(logT)$-regretアルゴリズムの可能性を排除する。
論文 参考訳（メタデータ） (2020-01-27T03:44:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。