論文の概要: Collapses in quantum-classical probabilistically checkable proofs and the quantum polynomial hierarchy
- arxiv url: http://arxiv.org/abs/2506.19792v1
- Date: Tue, 24 Jun 2025 16:59:50 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-25 19:48:23.735311
- Title: Collapses in quantum-classical probabilistically checkable proofs and the quantum polynomial hierarchy
- Title（参考訳）: 量子古典的確率論的チェック可能な証明における崩壊と量子多項式階層
- Authors: Kartik Anand, Kabgyun Jeong, Junseo Lee,
- Abstract要約: 本研究では, 量子証明システムの構造特性を, ランドスケープの複雑さを明らかにする崩壊結果の確立によって検討する。
主なコントリビューションは次の3つです。 $mathsfUniqueQP = MathsfQ CPCP$ under $mathsfBQ$-operators and randomized reductions。
- 参考スコア（独自算出の注目度）: 0.7321157455672144
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate structural properties of quantum proof systems by establishing collapse results that uncover simplifications in their complexity landscape. We extend classical results such as the Karp-Lipton theorem to quantum polynomial hierarchy with quantum proofs and establish uniqueness preservation for quantum-classical probabilistically checkable proof systems. Our main contributions are threefold. First, we prove that restricting quantum-classical PCP systems to uniqueness does not reduce computational power: $\mathsf{UniqueQCPCP} = \mathsf{QCPCP}$ under $\mathsf{BQ}$-operator and randomized reductions, demonstrating robustness similar to the $\mathsf{UniqueQCMA} = \mathsf{QCMA}$ result. Second, we establish a non-uniform quantum analogue of the Karp-Lipton theorem, showing that if $\mathsf{QMA} \subseteq \mathsf{BQP}/\mathsf{qpoly}$, then $\mathsf{QPH} \subseteq \mathsf{Q\Sigma}_2/\mathsf{qpoly}$, extending the classical collapse theorem to quantum complexity with quantum advice. Third, we introduce a consistent variant of the quantum polynomial hierarchy ($\mathsf{CQPH}$) with consistency constraints across interaction rounds while maintaining product-state proofs, proving its unconditional collapse $\mathsf{CQPH} = \mathsf{CQ\Sigma}_2$. This contrasts with prior work on quantum-entangled polynomial hierarchy, showing that consistency rather than entanglement drives the collapse. These results contribute to understanding structural boundaries in quantum complexity theory and the interplay between constraint types in quantum proof systems.
- Abstract（参考訳）: 本研究では, 量子証明系の構造特性について, 複雑化の背景を解明する崩壊結果を確立することによって検討する。
我々は、カルプ・リプトンの定理のような古典的な結果を量子証明で量子多項式階層に拡張し、量子古典的確率論的検証可能な証明系に対する一意性保存を確立する。
私たちの主な貢献は3倍です。
まず、量子古典的PCPシステムを一意性に制限することは、計算力を低下させるものではないことを証明する: $\mathsf{UniqueQCPCP} = \mathsf{QCPCP}$ under $\mathsf{BQ}$-operatorおよびランダム化還元、そして $\mathsf{UniqueQCMA} = \mathsf{QCMA}$ result。
第二に、カルプ・リプトンの定理の非一様量子アナログを確立し、もし$\mathsq \mathsf{BQP}/\mathsf{qpoly}$、$\mathsf{QPH} \subseteq \mathsf{Q\Sigma}_2/\mathsf{qpoly}$とすると、古典的な崩壊定理を量子アドバイスで量子複雑性に拡張する。
第三に、積状態の証明を維持しながら、相互作用ラウンド間の一貫性の制約を持つ量子多項式階層($\mathsf{CQPH}$)の一貫性のある変種($\mathsf{CQ\Sigma}_2$)を導入し、その非条件崩壊を証明した。
これは、量子交叉多項式階層に関する以前の研究とは対照的であり、絡み合いよりも一貫性が崩壊を引き起こすことを示している。
これらの結果は、量子複雑性理論における構造的境界と、量子証明系における制約型間の相互作用の理解に寄与する。
関連論文リスト
- Classical versus quantum queries in quantum PCPs with classical proofs [0.3004066195320147]
量子古典PCPを一般化し、古典的な証明に$q$の量子クエリを適用できるようにします。
驚くべきことに、このことは、定数量子古典量に対して逆から定数への約束のギャップを増幅できることを示している。
約束のギャップは達成できるが、我々の結果は、$mathsfQCMA$に対する定型クエリ量子古典的PCPが存在しないという強い証拠を与える。
論文 参考訳（メタデータ） (2024-11-01T18:00:56Z) - Improved separation between quantum and classical computers for sampling and functional tasks [3.618534280726541]
本稿では、量子コンピュータが古典的コンピュータを超えた計算が可能であるという既存の証拠をさらに強調する。
i)ポストセレクションを持つ量子コンピュータは、ポストセレクションを持つ古典的コンピュータと同じくらい強力である。
正確な数え上げオラクルで解ける問題と近似数え上げオラクルで解ける問題の間に同値性が存在すると証明すると、階層構造はその第2レベルに崩壊する。
論文 参考訳（メタデータ） (2024-10-28T11:30:10Z) - The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。
特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。
QMA(2) が $textQMA+(2)$ に等しいことを示す。
論文 参考訳（メタデータ） (2024-02-29T01:35:46Z) - Lower Bounds for Unitary Property Testing with Proofs and Advice [0.0]
ユニタリプロパティのテストでは、テスタとしても知られる量子アルゴリズムは、ブラックボックスのユニタリへのクエリアクセスが与えられる。
本稿では,一元性検定の量子クエリの下位境界を証明するための新しい手法を提案する。
論文 参考訳（メタデータ） (2024-01-15T19:00:36Z) - Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower
bounds [1.3927943269211591]
本研究は、$mathsfPH$の量子検証に基づく3つの一般化を研究する。
まず、[GSSSY22] から、崩壊定理と$mathsfQCPH$に対するカルプ・リプトンの定理を含むいくつかの開問題を解く。
我々は、$mathsfpureQPH$に対する一方の誤り低減と、これらの量子変量$mathsfPH$に関する最初の境界を示す。
論文 参考訳（メタデータ） (2024-01-03T09:12:25Z) - The Entangled Quantum Polynomial Hierarchy Collapses [0.0]
絡み合った量子量子階層$mathsfQEPH$が第2レベルに崩壊することを示す。
また、量子重ね合わせ(古典的確率ではない)だけがこれらの階層の計算力を増大させることを示す。
論文 参考訳（メタデータ） (2024-01-02T22:25:56Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - Succinct Classical Verification of Quantum Computation [30.91621630752802]
量子計算のための古典的簡潔な対話的引数(BQP)を構築する。
我々のプロトコルは、識別不能難読化(iO)と学習エラー(LWE)の事後セキュリティを前提として安全である。
論文 参考訳（メタデータ） (2022-06-29T22:19:12Z) - Speeding up Learning Quantum States through Group Equivariant
Convolutional Quantum Ans\"atze [13.651587339535961]
我々はSU$(d)$対称性を持つ畳み込み量子回路の枠組みを開発する。
我々は、$nameSU(d)$と$S_n$ irrepbasesの同値性に関するHarrowの主張を証明する。
論文 参考訳（メタデータ） (2021-12-14T18:03:43Z) - Depth-efficient proofs of quantumness [77.34726150561087]
量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。
本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
論文 参考訳（メタデータ） (2021-07-05T17:45:41Z) - Post-Quantum Multi-Party Computation [32.75732860329838]
我々は、悪質な時間量子敵に対するセキュリティを備えた古典的機能(平易なモデル)のマルチパーティ計算について研究する。
誤差付き学習における超ポリノミカル量子硬度(LWE)とLWEに基づく円形セキュリティ仮定の量子硬度を仮定する。
その過程で、私たちは独立した関心を持つ可能性のある暗号プリミティブを開発します。
論文 参考訳（メタデータ） (2020-05-23T00:42:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。