論文の概要: A Dichotomy for MIP* in the Presence of Unital Noise

• arxiv url: http://arxiv.org/abs/2609.39318v1
• Date: Wed, 30 Sep 2026 08:57:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-01 18:57:27.463595
• Title: A Dichotomy for MIP* in the Presence of Unital Noise
• Title（参考訳）: 単発騒音下におけるMIP*の2分割法
• Abstract要約: 我々は、$$が量子最大相関$_max()1$のノイズの多いEPR状態である場合、結果として生じる複雑性クラスは$mathsfNEXP=mathsfMIP$と等価であることを示す。 mathsfMIP[textpoly,textpoly]=mathsfMIP =mathsfNEXP,textif $ is separable or $_max()1$;]
• 参考スコア（独自算出の注目度）: 12.137299376764206
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A recent work studied quantum two-prover one-round proof systems $\mathsf{MIP}^ψ[\text{poly},O(1)]$. It showed that when $ψ$ is a noisy EPR state with quantum maximal correlation $ρ_{\max}(ψ)<1$, the resulting complexity class is equivalent to $\mathsf{NEXP}=\mathsf{MIP}$. In contrast, $\mathsf{MIP}^{\text{EPR}}[\text{poly},O(1)]=\mathsf{RE}$. Not all noise, however, decreases quantum maximal correlation. A basic example is dephasing noise: a dephased EPR pair retain quantum maximal correlation $1$. In this work, we remove the constant-answer restriction and establish a complete dichotomy for $\mathsf{MIP}^ψ[\text{poly},\text{poly}]$, where the provers share arbitrarily many copies of EPR pairs subject to unital noise. Equivalently, let $ψ$ be a fixed two-qubit state with maximally mixed marginals. We prove that \[\mathsf{MIP}^ψ[\text{poly},\text{poly}]=\mathsf{MIP} =\mathsf{NEXP},~\text{if $ψ$ is separable or $ρ_{\max}(ψ)<1$};\]\[\mathsf{MIP}^ψ[\text{poly},\text{poly}]=\mathsf{MIP}^ψ[\text{poly},O(1)]=\mathsf{RE},\text{if $ψ$ is entangled and $ρ_{\max}(ψ)=1$.}\] Beyond the complexity classification, our proof develops two techniques that may be useful more broadly in quantum information and quantum complexity. First, we introduce a positivity-preserving low-degree approximation framework for quantum measurements: instead of truncating positive operators directly in the Pauli basis, we approximate suitable square-root factorizations, simultaneously achieving low Pauli degree, positivity, and global control over an entire POVM. Second, we develop a new dimension-reduction method, called Pauli folding, for low-degree positive operators. Its key ingredient is an almost-multiplicativity theorem for randomized Pauli hashing, which allows noncommutative products, positivity, and normalization to survive compression with controlled error.
• Abstract（参考訳）: 最近の研究は量子双発一周証明システム $\mathsf{MIP}^*[\text{poly},O(1)]$ について研究している。 量子極大相関を持つノイズの多い EPR 状態であるとき、結果として生じる複雑性クラスは $\mathsf{NEXP}=\mathsf{MIP}$ と同値である。 対照的に、$\mathsf{MIP}^{\text{EPR}}[\text{poly},O(1)]=\mathsf{RE}$である。 しかし、全てのノイズが量子最大相関を減少させるわけではない。 基本的な例はノイズの除去である: 脱相のEPR対は量子最大相関を1ドルで保持する。 本研究では, 一定応答制限を除去し, $\mathsf{MIP}^*[\text{poly},\text{poly}]$ の完全二分法を確立する。 等しく、$$ を極大に混合された二量子状態とする。 我々は、 \[\mathsf{MIP}^*[\text{poly},\text{poly}]=\mathsf{MIP} =\mathsf{MIP} =\mathsf{NEXP},~\text{if $\$ is separable or $ρ_{\max}( )<1$};\]\[\mathsf{MIP}^*[\text{poly},\text{poly}]=\mathsf{MIP}^*[\text{poly},O(1)]=\mathsf{RE},\text{if$'s entangled and $ρ_{\max}( )=1$であることを示す。 我々の証明は、複雑性分類の他に、量子情報と量子複雑性においてより広く役立つ2つの手法を開発した。 まず, 正の演算子を直接パウリ基底で振る舞う代わりに, 適切な平方根分解を近似し, 同時に低パウリ次数, 正の値, 全POVMのグローバル制御を実現する。 第二に、低次正作用素に対するパウリ折り畳みと呼ばれる新しい次元還元法を開発する。 その鍵となる要素は、ランダム化されたパウリハッシュに対するほぼ多重性定理であり、これは非可換積、正の積、正規化が制御誤差で圧縮に耐えることができる。

関連論文リスト

• Computational Bounds for $f$-Routing [1.2604738912025477]
  我々は、一様攻撃者に対する無条件リソースの低い境界を証明した。 入力長 $n$ と十分小さい定数 $>0$ に対して、$q$ qubits を用いた一様生成戦略は、以下の計算境界を$f$ で表している。 これらの境界は、内積関数 $f=mathrmIP$ に対して、Bluhm, Christandl, Speelman (2022) の$qlelog n$ を超える。
  論文  参考訳（メタデータ） (2026-09-30T17:46:42Z)
• Quantum Algorithms and Hardness for Point-Count Approximation over Finite Fields [1.4323566945483497]
  有限体上のローレントルムの解数の近似について検討する。 我々の最初の主要な結果は、成功確率1-$で、$widehat(f)$ fulfilling [ |widehatN(f) - N(f)| le varepsilon qn+s/2-]を出力する量子アルゴリズムである。 2つ目の主要な結果として、ランダム時間チューリング還元の下で同じ問題が$#$P-hardになることを示す。
  論文  参考訳（メタデータ） (2026-08-25T00:23:27Z)
• 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)
• $\mathsf{P} \neq \mathsf{NP}$: A Non-Relativizing Proof via Quantale Weakness and Geometric Complexity [0.0]
  We work in the weak Quantale $w_Q=K_mathrmpoly(cdotmidcdot)$. ランダムな3ドルCNFをマスキングした効率よくサンプリング可能なアンサンブル$D_m$に対して、スイッチング・バイ・ウェイクネスの正規形式を証明する。
  論文  参考訳（メタデータ） (2025-10-09T21:01:17Z)
• Fourier Spectrum of Noisy Quantum Algorithms [0.0]
  量子アルゴリズムに作用する雑音は、ノイズの種類と複雑に結びついている方法でフーリエ成長を阻害することを示す。 特に,2-Forrelationと3-Forrelationは,それぞれ$mathsfDQC_k$と$frac12mathsfBQP$モデルで,$NOmega(1)$クエリを必要とすることを示す。
  論文  参考訳（メタデータ） (2025-10-07T19:07:59Z)
• Dimension Independent Disentanglers from Unentanglement and Applications [55.86191108738564]
  両部非絡み込み入力から次元独立なk-パーティイトディジアンタングル(類似)チャネルを構築する。 NEXP を捉えるためには、$| psi rangle = sqrta | sqrt1-a | psi_+ rangle という形の非負の振幅を持つのに十分であることを示す。
  論文  参考訳（メタデータ） (2024-02-23T12:22:03Z)
• Monogamy of entanglement between cones [43.57338639836868]
  モノガミーは量子論の特徴であるだけでなく、凸錐の一般対の極小テンソル積を特徴づけることを示した。 我々の証明は、アフィン同値まで単純化された生成物の新たな特徴を生かしている。
  論文  参考訳（メタデータ） (2022-06-23T16:23:59Z)
• 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)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。 次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。 我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
  論文  参考訳（メタデータ） (2022-02-23T16:10:23Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• On the complexity of zero gap MIP* [0.11470070927586014]
  クラス $mathsfMIP*$ が $mathsfRE$ に等しいことを示す。 特にこのことは、非局所ゲーム$G$の量子値の近似の複雑さがハルティング問題の複雑性と同値であることを示している。
  論文  参考訳（メタデータ） (2020-02-24T19:11:01Z)

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

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