論文の概要: The Computational Advantage of MIP* Vanishes in the Presence of Noise

• arxiv url: http://arxiv.org/abs/2312.04360v2
• Date: Tue, 23 Jul 2024 15:51:20 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-24 23:23:10.439363
• 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, Penghui Yao,
• Abstract要約: エンタングルメント MIP* を持つ量子マルチプロペラ対話型証明システムは、古典的な MIP よりもはるかに強力である。 QinとYao '21と'23の最近の研究は、プローサの共有状態がノイズを含む場合、この利点は著しく減少することを示した。 提案手法では,各EPR状態が任意に小さなノイズ量で影響を受ける場合,その複雑性クラスはNEXP = MIPと等価であることを示す。
• 参考スコア（独自算出の注目度）: 4.041530553470258
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: Quantum multiprover interactive proof systems with entanglement MIP* are much more powerful than its 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 noisy EPR states, where each EPR state is affected by an arbitrarily small constant amount of noise, the resulting complexity class is equivalent to 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* のプローバーが非有界量子絡み合いを共有できるためである。 しかし、近年の秦と八尾の「21」と「23」の研究では、プローサの共有状態がノイズを含む場合、この優位性が著しく低下することが示されている。 本稿では,量子マルチプロペラ対話型証明システムの計算能力に及ぼすノイズの影響を正確に評価する。 検証器が多項式的に多くのビットをプローバーに送信し、プローバーが常に多くのビットを返送する量子二プローラーワンラウンド対話システム MIP*[poly, O(1)] について検討する。 このモデルでは、共有絡みによる計算上の優位性を完全に損なうことを示す。 具体的には、各EPR状態が任意に小さなノイズ量によって影響を受けるような、任意のノイズの多いEPR状態を共有することが許された場合、複雑性クラスはNEXP = MIPと等価であることを示す。 これは、Qin と Yao '21 による NEEEXP (非決定的三重指数時間) の既知バウンダリにおいて大きく改善され、また、このパワーの崩壊は、ノイズのない EPR 状態が RE = MIP*[poly, poly] のフルパワーをクラスに与えることを示し、O(1) の応答サイズよりもノイズによるものであることも示している。

関連論文リスト

• 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)

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

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