論文の概要: The Computational Advantage of MIP* Vanishes in the Presence of Noise
- arxiv url: http://arxiv.org/abs/2312.04360v1
- Date: Thu, 7 Dec 2023 15:28:40 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-08 14:31:42.775827
- Title: The Computational Advantage of MIP* Vanishes in the Presence of Noise
- Title（参考訳）: 騒音下におけるMIP*Vanishesの計算的優位性
- Authors: Yangjing Dong, Honghao Fu, Anand Natarajan, Minglong Qin, Haochen Xu
and Penghui Yao
- Abstract要約: 本稿では,量子多目的対話型証明システムの計算能力に及ぼす雑音の影響を特徴付ける。
プローバが任意に多くのEPR状態を共有することができ、各EPR状態が任意に小さなノイズ量の影響を受けている場合、その複雑性クラスはNEXP = MIPに含まれる。
また、このパワーの崩壊はO(1)応答サイズではなくノイズによるものであることが示され、ノイズのないEPR状態がRE = MIP*[poly, poly]のフルパワーをクラスに与えることが示される。
- 参考スコア（独自算出の注目度）: 4.2441960155849285
- License: http://creativecommons.org/publicdomain/zero/1.0/
- Abstract: Quantum multiprover interactive proof systems with entanglement MIP* are much
more powerful than their classical counterpart MIP (Babai et al. '91, Ji et al.
'20): while MIP = NEXP, the quantum class MIP* is equal to RE, a class
including the halting problem. This is because the provers in MIP* can share
unbounded quantum entanglement. However, recent works of Qin and Yao '21 and
'23 have shown that this advantage is significantly reduced if the provers'
shared state contains noise. This paper attempts to exactly characterize the
effect of noise on the computational power of quantum multiprover interactive
proof systems. We investigate the quantum two-prover one-round interactive
system MIP*[poly, O(1)], where the verifier sends polynomially many bits to the
provers and the provers send back constantly many bits. We show noise
completely destroys the computational advantage given by shared entanglement in
this model. Specifically, we show that if the provers are allowed to share
arbitrarily many EPR states, where each EPR state is affected by an arbitrarily
small constant amount of noise, the resulting complexity class is contained in
NEXP = MIP. This improves significantly on the previous best-known bound of
NEEEXP (nondeterministic triply exponential time) by Qin and Yao '21. We also
show that this collapse in power is due to the noise, rather than the O(1)
answer size, by showing that allowing for noiseless EPR states gives the class
the full power of RE = MIP*[poly, poly]. Along the way, we develop two
technical tools of independent interest. First, we give a new, deterministic
tester for the positivity of an exponentially large matrix, provided it has a
low-degree Fourier decomposition in terms of Pauli matrices. Secondly, we
develop a new invariance principle for smooth matrix functions having bounded
third-order Fr\'echet derivatives or which are Lipschitz continous.
- Abstract（参考訳）: 絡み合うmip*を持つ量子マルチプロファー対話型証明系は、古典的なmip (babai et al. '91, ji et al. '20): mip = nexp であるのに対し、量子クラスmip* はre に等しい。
これは、MIP* のプローバーが非有界量子絡み合いを共有できるためである。
しかし、qinとyao '21と'23の最近の研究は、provers'共有状態がノイズを含む場合、この利点は大幅に減少することを示している。
本稿では,量子マルチプロペラ対話型証明システムの計算能力に及ぼすノイズの影響を正確に評価する。
検証器が多項式的に多くのビットをプローバーに送信し、プローバーが常に多くのビットを返送する量子二プローラーワンラウンド対話システム MIP*[poly, O(1)] について検討する。
このモデルにおける共有絡み合いによる計算上のアドバンテージを,ノイズが完全に破壊することを示す。
具体的には、各EPR状態が任意に小さなノイズに影響を受けるような任意の数のEPR状態を共有することが許された場合、その複雑性クラスはNEXP = MIPに含まれることを示す。
This improves significantly on the previous best-known bound of NEEEXP (nondeterministic triply exponential time) by Qin and Yao '21. We also show that this collapse in power is due to the noise, rather than the O(1) answer size, by showing that allowing for noiseless EPR states gives the class the full power of RE = MIP*[poly, poly]. Along the way, we develop two technical tools of independent interest. First, we give a new, deterministic tester for the positivity of an exponentially large matrix, provided it has a low-degree Fourier decomposition in terms of Pauli matrices. Secondly, we develop a new invariance principle for smooth matrix functions having bounded third-order Fr\'echet derivatives or which are Lipschitz continous.
関連論文リスト
- The status of the quantum PCP conjecture (games version) [0.6144680854063939]
多重対数的に長いメッセージを持つ多目的対話型証明システムはREにおける任意の決定問題を解くことができることを示す。
本稿では,(1)標準AM完全問題に対する効率的なプロバーを用いた簡潔なMIP*プロトコルを新たに構築し,(2)ナタラジャンとヴィディックのエネルギー増幅手順における誤差を説明する。
論文 参考訳（メタデータ） (2024-03-19T18:30:32Z) - The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。
特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。
QMA(2) が $textQMA+(2)$ に等しいことを示す。
論文 参考訳（メタデータ） (2024-02-29T01:35:46Z) - Maximum expectation of observables with restricted purity states [2.7624021966289605]
実用的な量子情報処理(QIP)の評価は、ノイズによって課される限界を理解せずに部分的に行われている。
我々は、ノイズの多い量子状態の準備、検証、観察を行うための推定の必要性を満たす。
ノイズの多いシステムは、ノイズのないシステムよりも常に高い基底状態エネルギーを与えます。
論文 参考訳（メタデータ） (2023-11-13T19:02:35Z) - Simulating Noisy Variational Quantum Algorithms: A Polynomial Approach [1.806183113759115]
大規模変動量子アルゴリズムは量子優位性を達成するための潜在的な経路として広く認識されている。
本稿では,可観測物のバックプロパゲーションの積分経路に基づく新しい$gammaPPP法を提案する。
我々は,IBMの127量子ビットイーグルプロセッサにおけるゼロノード化実験結果の古典的シミュレーションを行う。
論文 参考訳（メタデータ） (2023-06-09T10:42:07Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Quantum Lyapunov exponent in dissipative systems [68.8204255655161]
時間外秩序相関器(OTOC)は閉量子系で広く研究されている。
これら2つのプロセス間の相互作用について研究する。
OTOC崩壊速度は古典的なリャプノフと密接に関連している。
論文 参考訳（メタデータ） (2022-11-11T17:06:45Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Quantum Proofs of Proximity [6.160793572747927]
近接検定のQMA証明は古典的近接検定や量子検定よりも指数関数的に強いことを示す。
この結果には、表現力のある特性のクラスをテストするための量子スピードアップを可能にするアルゴリズムフレームワークが含まれている。
また、このファミリーの外部にある特性であるグラフ双分極性をテストするためのQMAアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-08T13:15:30Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。
我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。
我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文 参考訳（メタデータ） (2020-04-14T11:05:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。