論文の概要: Near-Optimal Gap Amplification for Nonnegative Unentangled Quantum Proofs

• arxiv url: http://arxiv.org/abs/2608.07986v1
• Date: Sat, 08 Aug 2026 07:45:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-11 19:16:36.593651
• Title: Near-Optimal Gap Amplification for Nonnegative Unentangled Quantum Proofs
• Title（参考訳）: 非負の量子証明のための準最適ギャップ増幅
• Abstract要約: 量子証明の非絡み合いを特徴とするクラス$mathsfQMA+(2)$のギャップ増幅について検討する。 我々の証明は対称部分空間射影と$mathsfQMA+(1)=mathsfNEXP$ of Bassirian, Fefferman, Marwahaの関係を組み合わせる。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study gap amplification of the class $\mathsf{QMA}^{+}(2)$ characterized by unentangled quantum proofs whose amplitudes are nonnegative in the computational basis. This class was recently introduced by Jeronimo and Wu (STOC 2023), and its behavior depends sharply on the completeness-soundness gap: although it captures the power of $\mathsf{NEXP}$ for some small constant gap, it is equal to $\mathsf{QMA}(2)$ for larger constant gap. This is in stark contrast to $\mathsf{QMA}(2)$ where strong gap amplification is known due to the product test by Harrow and Montanaro (FOCS 2010, JACM 2013). In this paper, we prove for every completeness $c$ and soundness $s$ with $c-s=1/\mathrm{poly}(n)$, \[ \mathsf{NEXP} = \mathsf{QMA}^{+}(2,c,s) = \mathsf{QMA}^{+}\left(2,1-\frac1{\mathrm{poly}(n)},\frac14+\frac1{\mathrm{poly}(n)}\right). \] Our result gives a clean complexity phase transition for $\mathsf{QMA}^{+}(2)$ since we have \[ \mathsf{QMA}^{\mathbb R}(2) = \mathsf{QMA}^{+}\left(2,1-\frac1{\mathrm{poly}(n)},\frac14-\frac1{\mathrm{poly}(n)}\right), \] where $\mathsf{QMA}^{\mathbb R}(2)$ denotes $\mathsf{QMA}(2)$ with witnesses restricted to real amplitudes. Our amplification is thus optimal in the sense that a slight improvement of our soundness would have the collapse \[ \mathsf{QMA}^{\mathbb R}(2)=\mathsf{NEXP}. \] Our proof combines symmetric-subspace projections with the relation $\mathsf{QMA}^{+}(1)=\mathsf{NEXP}$ of Bassirian, Fefferman, and Marwaha (ITCS 2024). The main technical ingredient is a dimension-independent de Finetti theorem in Hilbert-Schmidt norm that applies when the number of registers under consideration grows logarithmically.
• Abstract（参考訳）: 計算ベースで振幅が非負の非絡み合った量子証明によって特徴づけられるクラス $\mathsf{QMA}^{+}(2)$ のギャップ増幅について検討する。 このクラスは、最近Jeronimo と Wu (STOC 2023) によって導入され、その振舞いは完全性-健全性ギャップ(英語版)に大きく依存している:ある小さな定数ギャップに対して $\mathsf{NEXP}$ のパワーを捉えるが、より大きい定数ギャップに対して $\mathsf{QMA}(2)$ に等しい。 これは、Harrow and Montanaro (FOCS 2010, JACM 2013)による製品テストにより、強いギャップ増幅が知られている$\mathsf{QMA}(2)$とは対照的である。 本稿では、すべての完全性$c$と音響性$s$ with $c-s=1/\mathrm{poly}(n)$, \[ \mathsf{NEXP} = \mathsf{QMA}^{+}(2,c,s) = \mathsf{QMA}^{+}\left(2,1-\frac1{\mathrm{poly}(n)},\frac14+\frac1{\mathrm{poly}(n)}\rightとする。 この結果は、$\mathsf{QMA}^{\mathbb R}(2) = \mathsf{QMA}^{+}\left(2,1-\frac1{\mathrm{poly}(n)},\frac14-\frac1{\mathrm{poly}(n)}\right), \] ここで、$\mathsf{QMA}^{\mathbb R}(2)$は、実振幅に制限された証人を持つので、$\mathsf{QMA}^{\mathbb R}(2)$に対してクリーンな複雑性相転移を与える。 したがって、我々の増幅は、音質をわずかに改善すると、[ \mathsf{QMA}^{\mathbb R}(2)=\mathsf{NEXP} が崩壊するという意味で最適である。 この証明は、対称部分空間の射影と、バシリアン、フェーファーマン、マルワハ(ITCS 2024)の$\mathsf{QMA}^{+}(1)=\mathsf{NEXP}$の関係を結合する。 主な技術的要素はヒルベルト=シュミットノルムにおける次元非依存のデ・フィネッティの定理であり、考慮中のレジスタの数が対数的に増加するときに適用される。

関連論文リスト

• Optimal Neural Network Approximation via Empirical Least Squares with Deterministic Samples [7.864201093845001]
  線形化されたReLU$k$ニューラルネットワークを用いた楕円型スペクトル方程式の離散最小二乗近似の理論を考案する。 我々は、対数係数と任意に小さな滑らかさ損失まで、高い確率の残差推定値を確立する。 重要な解析的要素は、線形化されたReLU$k$ネットワーク空間に対するベルンシュタインの不等式である。
  論文  参考訳（メタデータ） (2026-08-07T01:22:27Z)
• Hardness Amplification for (Sparse) LPN [5.1105538244022135]
  雑音を学習するパリティ(mathsfLPN$)とそのスパース変種に対する新しい硬度増幅結果を示す。 で$mathsfLPN$を解くアルゴリズムは、"ほとんどすべてのインスタンス"で$mathsfLPN$を解くアルゴリズムに変換することができる。 同じ増幅アプローチを$mathsfLPN$ over $mathbbF_q$とSparse-$mathsfLPN$に拡張します。
  論文  参考訳（メタデータ） (2026-05-11T06:34:37Z)
• 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)
• On the Complexity of Pure-State Consistency of Local Density Matrices [0.0]
  我々は、Aharanov と Regev [FOCS 2003] の複雑性クラス QMA+ の純粋状態類似体を定義し、PureSuperQMA と呼ぶ。 2-qubit還元密度行列の硬さを証明し、混合N-表現性はQMA完全であることを示す。 我々はこれを、PureCLDMがQMA(2)完全かどうかという長年の未解決問題に対する否定的な答えの証拠とみなす。
  論文  参考訳（メタデータ） (2024-11-05T13:43:21Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Dimension Independent Disentanglers from Unentanglement and Applications [55.86191108738564]
  両部非絡み込み入力から次元独立なk-パーティイトディジアンタングル(類似)チャネルを構築する。 NEXP を捉えるためには、$| psi rangle = sqrta | sqrt1-a | psi_+ rangle という形の非負の振幅を持つのに十分であることを示す。
  論文  参考訳（メタデータ） (2024-02-23T12:22:03Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。 本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。 最悪の場合、$m$に対する指数的依存は避けられないことを示す。
  論文  参考訳（メタデータ） (2024-02-06T15:39:09Z)
• 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)
• Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization [49.090785356633695]
  非対称な低ランク分解問題: [mathbbRm min d , mathbfU$ および MathV$ について検討する。
  論文  参考訳（メタデータ） (2021-06-27T17:25:24Z)
• 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)

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

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