論文の概要: Achieving perfect completeness for one- and two-message quantum proof systems

• arxiv url: http://arxiv.org/abs/2609.15926v2
• Date: Thu, 17 Sep 2026 16:36:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-20 08:55:53.421256
• Title: Achieving perfect completeness for one- and two-message quantum proof systems
• Title（参考訳）: 1-および2-message量子証明系に対する完全性を達成する
• Abstract要約: 完全完全性は1-および2-message量子証明系において達成できるかどうかを考察する。 本研究では、$sf QIP(2)$, $rm qqtext-sf QAM$, $sf QAM$, $sf QMA$が完全性を達成できることを示す。
• 参考スコア（独自算出の注目度）: 1.919357970694788
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: While quantum interactive proof systems using at least three messages can achieve perfect completeness, as shown by Kitaev and Watrous (STOC 2000), whether perfect completeness is achievable for one- and two-message quantum proof systems has remained open. For the one-message case, whether $\sf QMA$ can achieve perfect completeness was posed as an open problem in Watrous (FOCS 2000) and Aharonov and Naveh (2002); for the two-message case, the corresponding problems were (implicitly) posed in Jain, Upadhyay, and Watrous~(FOCS 2009) and Kobayashi, Le Gall, and Nishimura (SICOMP, 2019). In this work, we establish that ${\sf QIP}(2)$, ${\rm qq}\text{-}{\sf QAM}$, $\sf QAM$, and $\sf QMA$ can achieve perfect completeness. Here ${\rm qq}\text{-}{\sf QAM}$ denotes the class of promise problems admitting two-message quantum-public-coin quantum interactive proof systems in which the verifier's only message consists of half-EPR pairs. Our main technical contributions are the follows: 1. For $\sf QMA$ (and directly for $\sf QAM$), an exactly constructible block-encoded matrix whose kernel certifies yes instances, constructed from the acceptance operator induced by the verification circuit. 2. For ${\sf QIP}(2)$ (and implicitly ${\rm qq}\text{-}{\sf QAM}$), a new turn-halving transformation that preserves completeness and ensures that the resulting proof system retains at least two messages, provided that the terminal state before the final measurement is efficiently preparable.
• Abstract（参考訳）: 少なくとも3つのメッセージを用いた量子インタラクティブな証明システムは完全な完全性を達成することができるが、K Kitaev と Watrous (STOC 2000) が示すように、完全性は1つのメッセージと2つのメッセージの量子証明システムに対して達成可能であるかは未解決のままである。 ワンメッセージの場合、$\sf QMA$が完全性を達成するか否かは、Watrous (FOCS 2000) と Aharonov and Naveh (2002) においてオープン問題として提起され、2メッセージの場合、対応する問題は Jain, Upadhyay, and Watrous~ (FOCS 2009) と Kobayashi, Le Gall, Nishimura (SICOMP, 2019) で(単純に)提示された。 本研究では、${\sf QIP}(2)$, ${\rm qq}\text{-}{\sf QAM}$, $\sf QAM$, $\sf QMA$が完全性を達成できることを示す。 ここで${\rm qq}\text{-}{\sf QAM}$は、検証者の唯一のメッセージが半分のEPRペアで構成されている2つのメッセージの量子公開結合量子インタラクティブ証明システムを認める約束問題のクラスを表す。 1.$\sf QMA$(および$\sf QAM$に直接)は、カーネルがイエスインスタンスを認証し、検証回路によって誘導される受け入れ演算子から構築される、正確に構成可能なブロック符号化行列である。 2)${\sf QIP}(2)$(および暗黙的に${\rm qq}\text{-}{\sf QAM}$)の場合、最終測定前の端末状態が効率的に準備可能であることを条件として、完全性を保持し、結果の証明システムが少なくとも2つのメッセージを保持することを保証する。

関連論文リスト

• PureSuperQMA(exp) = BellPureSymQMA(poly) = QMA via Dimension-Free Bosonic Argmax [36.23068106699028]
  純粋状態整合性問題は自然に量子証明システムにつながり、1人の証人が多くの受理制約を満たす必要がある。 $mathsfBellPureSymQMA(textpoly)$は、証明者が純粋状態の多くのコピーを検証しなければならない関連するモデルである。 k$-local pure-state consistency is $mathsfQMA$-complete for every fixed $kge2$, so is the exact bosonic and fermionic pure $N$-representability problem。
  論文  参考訳（メタデータ） (2026-09-10T17:37:22Z)
• An Optimal Analysis of the Product Test [42.29010058743949]
  製品テストは、純多部量子状態が特定のテンソル分解に完全に絡み合っているかどうかを決定する。 基本的なプロパティテストタスクであり、多くのアプリケーションがあるにもかかわらず、製品テストの正確な(最悪のケース)受け入れ確率曲線は、まだ完全には決定されていない。 複雑性理論の応用として,Harrow-Montanaro還元の1ショット音響パラメータを$mathsfQMA(k)$から$mathsfQMA(2)$に改善した。
  論文  参考訳（メタデータ） (2026-07-23T16:17:44Z)
• A Modular Approach to Succinct Arguments for QMA [17.20526790095253]
  我々は、QMAの簡潔な議論の暗号的基礎を広げる新しいフレームワークを開発する。 特に、LWEの硬さに依存しないQMAの最初の簡潔で古典的に検証可能な引数システムを得る。 我々のコンパイラはZhang(QCrypt 25)の量子剛性に基づく通信圧縮技術を拡張している
  論文  参考訳（メタデータ） (2026-06-03T21:38:23Z)
• Spectral Anatomy of Quantum Gaussian Process Kernels [38.264196157340216]
  我々は,Nystrm近似誤差に束縛されたコーシー=シュワルツテール,有限サンプル分散抽出等式,およびエンフターゲット依存の最適エントロピーのキャラクタリゼーションを証明した。 診断はカーネルに依存しない: ハードウェア効率、マッチゲート、IQPのインハンドRBF/Matérn/RFF/deep-カーネルファミリはすべて同一の$S/log n$曲線に崩壊する。
  論文  参考訳（メタデータ） (2026-05-29T07:41:14Z)
• Unentangled stoquastic Merlin-Arthur proof systems: the power of unentanglement without destructive interference [0.5586191108738564]
  Sf StoqMA(2)$ は非絡み合いのメルリン・アーサー証明系のクラスである。 $sf StoqMA(2)$は半量子であり、$sf MA$に崩壊することもあるが、$sf StoqMA(2)$は驚くほど強力である。
  論文  参考訳（メタデータ） (2026-04-30T14:04:22Z)
• A slightly improved upper bound for quantum statistical zero-knowledge [11.384500557173867]
  複雑性クラスであるQuantum Statistical Zero-Knowledge(mathsfQSZK$)は、最もよく知られた上限である$mathsfQIP(2) cap textco-mathsfQIP(2)$を持つ。 我々はこれを$mathsfQIP(2) cap textco-mathsfQIP(2)$に改善する。 我々の主な手法は、量子線型空間で実装可能なホレボ・ヘルストロム測度複雑性とウルマン変換のアルゴリズム版である。
  論文  参考訳（メタデータ） (2025-12-12T14:33:20Z)
• Uniqueness of purifications is equivalent to Haag duality [44.33169165028139]
  2つの系がフォン代数ノイマン$M_A$と$M_B$をヒルベルト空間$mathcal H$で交換することによってモデル化された場合、精製の特異性はハーグ双対性$M_A = M_B'$と等価であることを示す。
  論文  参考訳（メタデータ） (2025-09-16T10:05:17Z)
• Quantum Algorithms for Finite-horizon Markov Decision Processes [40.812944518646006]
  我々は、時間依存および有限水平マルコフ決定過程(MDP)を解くために、古典的アルゴリズムよりも効率的な量子アルゴリズムを設計する。 正確なダイナミックス設定において、我々の$textbfQVI-1$アルゴリズムがアクション空間$(A)$の2次スピードアップを達成することを証明している。 生成モデル設定において、我々のアルゴリズムである$textbfQVI-3$と$textbfQVI-4$が、最先端(SOTA)古典アルゴリズムよりも複雑なサンプルを実現することを証明している。
  論文  参考訳（メタデータ） (2025-08-07T09:00:23Z)
• Coherence in Property Testing: Quantum-Classical Collapses and Separations [42.44394412033434]
  テスタが2n/8$のサブセット状態と2-Theta(n)$の確率で2n/4$のサブセット状態とを区別できないことを示す。 また、アンタングルおよび量子-量子変換の下界への接続を示す。
  論文  参考訳（メタデータ） (2024-11-06T19:52:15Z)
• 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 Lower Bounds by Sample-to-Query Lifting [33.82353457014144]
  本稿では,量子サンプル対クエリリフト定理を用いて,量子クエリの下界を証明するための新しい手法を提案する。 位相/振幅推定やハミルトニアンシミュレーションなど,いくつかの既知の下界に対する統一的な証明を提供する。
  論文  参考訳（メタデータ） (2023-08-03T14:41:49Z)
• Quantum space, ground space traversal, and how to embed multi-prover interactive proofs into unentanglement [0.0]
  サビッチの定理は、NPSPACE計算はPSPACEでシミュレートできると述べている。 SQCMASPACE=NEXP のように、サビッチの定理の量子アナログが成り立たないことを示す。 SQCMASPACE を[Chailloux, Sattath, 2012] のスパース分離ハミルトン問題に組み込む方法を示す (QMA(2)-complete for 1/poly promise gap)。
  論文  参考訳（メタデータ） (2022-06-10T17:35:10Z)
• Reachable sets for two-level open quantum systems driven by coherent and incoherent controls [77.34726150561087]
  我々はコヒーレントかつ非コヒーレントな制御によって駆動される2レベル開量子系の全密度行列の集合における制御性について研究する。 2つのコヒーレント制御に対して、系は全密度行列の集合において完全に制御可能であることが示されている。
  論文  参考訳（メタデータ） (2021-09-09T16:14:23Z)
• Masking quantum information into a tripartite syste [1.343950231082215]
  量子多部マスク(QMM)と量子誤り訂正符号(QECC)の関係を考察する。 アイソメトリはシステムの全純状態のQMMであり、その範囲が任意の1つの消去チャネルのQECCである場合に限る。
  論文  参考訳（メタデータ） (2020-04-30T01:55:55Z)

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

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