論文の概要: Quantum space, ground space traversal, and how to embed multi-prover interactive proofs into unentanglement

• arxiv url: http://arxiv.org/abs/2206.05243v1
• Date: Fri, 10 Jun 2022 17:35:10 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-09 23:05:10.084224
• Title: Quantum space, ground space traversal, and how to embed multi-prover interactive proofs into unentanglement
• Title（参考訳）: 量子空間, 地上空間トラバーサル, およびマルチプロファー対話型証明をエンタングルメントに組み込む方法
• Authors: Sevag Gharibian and Dorian Rudolph
• Abstract要約: サビッチの定理は、NPSPACE計算はPSPACEでシミュレートできると述べている。 SQCMASPACE=NEXP のように、サビッチの定理の量子アナログが成り立たないことを示す。 SQCMASPACE を[Chailloux, Sattath, 2012] のスパース分離ハミルトン問題に組み込む方法を示す (QMA(2)-complete for 1/poly promise gap)。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Savitch's theorem states that NPSPACE computations can be simulated in PSPACE. We initiate the study of a quantum analogue of NPSPACE, denoted Streaming-QCMASPACE (SQCMASPACE), where an exponentially long classical proof is streamed to a poly-space quantum verifier. Besides two main results, we also show that a quantum analogue of Savitch's theorem is unlikely to hold, as SQCMASPACE=NEXP. For completeness, we introduce Streaming-QMASPACE (SQMASPACE) with an exponentially long streamed quantum proof, and show SQMASPACE=QMA_EXP (quantum analogue of NEXP). Our first main result shows, in contrast to the classical setting, the solution space of a quantum constraint satisfaction problem (i.e. a local Hamiltonian) is always connected when exponentially long proofs are permitted. For this, we show how to simulate any Lipschitz continuous path on the unit hypersphere via a sequence of local unitary gates, at the expense of blowing up the circuit size. This shows quantum error-correcting codes can be unable to detect one codeword erroneously evolving to another if the evolution happens sufficiently slowly, and answers an open question of [Gharibian, Sikora, ICALP 2015] regarding the Ground State Connectivity problem. Our second main result is that any SQCMASPACE computation can be embedded into "unentanglement", i.e. into a quantum constraint satisfaction problem with unentangled provers. Formally, we show how to embed SQCMASPACE into the Sparse Separable Hamiltonian problem of [Chailloux, Sattath, CCC 2012] (QMA(2)-complete for 1/poly promise gap), at the expense of scaling the promise gap with the streamed proof size. As a corollary, we obtain the first systematic construction for obtaining QMA(2)-type upper bounds on arbitrary multi-prover interactive proof systems, where the QMA(2) promise gap scales exponentially with the number of bits of communication in the interactive proof.
• Abstract（参考訳）: サビッチの定理は、NPSPACE計算はPSPACEでシミュレートできると述べている。 NPSPACEの量子アナログであるStreaming-QCMASPACE(SQCMASPACE)の研究を開始し、指数関数的に長い古典的証明を多空間量子検証器にストリームする。 2つの主要な結果の他に、SQCMASPACE=NEXP のように、サヴィッチの定理の量子アナログが成り立たないことも示している。 本稿では,SQMASPACE(SQMASPACE)を導入し,SQMASPACE=QMA_EXP(NEXPの量子アナログ)を示す。 最初の主な結果は、古典的設定とは対照的に、量子制約満足度問題(すなわち局所ハミルトニアン)の解空間は指数関数的に長い証明が許されるとき常に連結であることを示している。 このために、回路サイズを拡大するために、局所的なユニタリゲートの列を通して、単位超球面上の任意のリプシッツ連続経路をシミュレートする方法を示す。 このことは、量子エラー訂正符号が、進化が十分に遅い場合に、あるコードワードが誤って別のコードワードに進化するのを検出することができず、[ガリビアン、シコラ、ICALP 2015]の地上状態接続問題に関するオープンな質問に答えることを示している。 2つ目の主な結果は、任意のSQCMASPACE計算を「アンタングルメント」、すなわち、アンタングル付きプローバーを持つ量子制約満足度問題に埋め込むことができることである。 形式的には,SQCMASPACEを[Chailloux, Sattath, CCC 2012] (QMA(2)-complete for 1/poly promise gap) のスパース分離ハミルトン問題に組み込む方法を示す。 共役として、qma(2)promiseギャップが対話的証明における通信ビット数に指数関数的にスケールする任意の多因子対話的証明系において、qma(2)型上界を得るための最初の体系的構成を得る。

関連論文リスト

• Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians [0.0]
  非適応型量子PCPは、証明クエリ数が一定である場合に適応型量子PCPをシミュレートできることを示す。 また、ある量子PCPステートメントが偽であるような(量子)オラクルが存在することも示している。
  論文  参考訳（メタデータ） (2024-03-07T19:00:06Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。 特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。 QMA(2) が $textQMA+(2)$ に等しいことを示す。
  論文  参考訳（メタデータ） (2024-02-29T01:35:46Z)
• Quantum Signal Processing with the one-dimensional quantum Ising model [0.0]
  量子信号処理(QSP)は、量子システムの特性を操作および決定するための有望なフレームワークとして登場した。 我々は、時空双対量子回路や量子シミュレーションから量子制御まで、様々な分野における我々のアプローチの例と応用について述べる。
  論文  参考訳（メタデータ） (2023-09-08T18:01:37Z)
• Space-bounded quantum state testing via space-efficient quantum singular value transformation [2.647089498084052]
  空間有界量子計算のための新しい完全特徴付けを提案する。 片側エラー(単位coRQL)と片側エラー(BQL)の設定について検討する。 この結果から,空間境界状態試験問題はすべて同じクラスに対応することが明らかとなった。
  論文  参考訳（メタデータ） (2023-08-09T17:16:19Z)
• Quantum process tomography of continuous-variable gates using coherent states [49.299443295581064]
  ボソニックモード超伝導回路におけるコヒーレント状態量子プロセストモグラフィ(csQPT)の使用を実証する。 符号化量子ビット上の変位とSNAP演算を用いて構築した論理量子ゲートを特徴付けることにより,本手法の結果を示す。
  論文  参考訳（メタデータ） (2023-03-02T18:08:08Z)
• stateQIP = statePSPACE [0.15229257192293197]
  本研究では,SDPPSPACEと状態QIPの2つの状態クラスの関係について検討する。 私たちの主な結果は、リバースインクルージョン、stateQIP $subseteq$ statePSPACEです。 また、一般的な量子対話プロトコルの最適証明戦略を量子空間で実装できることも示している。
  論文  参考訳（メタデータ） (2023-01-18T19:00:17Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  浅量子回路の計算能力と古典計算の組合せを包括的に評価する。 いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
  論文  参考訳（メタデータ） (2022-10-12T17:54:02Z)
• Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
  量子計算の2つのモデル: CQ_dとQC_d。 CQ_dは、d-d-deepth量子コンピュータのシナリオを何度も捉え、QC_dは測定ベースの量子計算に類似している。 CQ_dとQC_dの類似性にもかかわらず、2つのモデルは本質的にはCQ_d $nsubseteq$QC_dとQC_d $nsubseteq$CQ_dである。
  論文  参考訳（メタデータ） (2022-01-06T03:10:53Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  本稿では,最適化問題における短期量子優位性の提案に着想を得た高忠実度ゲートセットを提案する。 3つのトランペット四重項のコヒーレントな多レベル制御を編成することにより、自然な3量子ビット計算ベースで作用する決定論的連続角量子位相ゲートの族を合成する。
  論文  参考訳（メタデータ） (2021-08-03T17:49:09Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。 本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
  論文  参考訳（メタデータ） (2021-07-05T17:45:41Z)

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

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