論文の概要: Collapses in quantum-classical probabilistically checkable proofs and the quantum polynomial hierarchy
- arxiv url: http://arxiv.org/abs/2506.19792v2
- Date: Sun, 06 Jul 2025 16:26:26 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-07-08 17:51:40.00295
- Title: Collapses in quantum-classical probabilistically checkable proofs and the quantum polynomial hierarchy
- Title（参考訳）: 量子古典的確率論的チェック可能な証明における崩壊と量子多項式階層
- Authors: Kartik Anand, Kabgyun Jeong, Junseo Lee,
- Abstract要約: 証明に特有の量子古典的PCPの制限は、そのパワーを低下させるものではないことを示す。
また、カルプ・リプトンの定理の非一様量子類似性も証明する。
これらの結果は、量子証明システムの構造に関する新たな洞察を与える。
- 参考スコア（独自算出の注目度）: 0.7321157455672144
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate the structure of quantum proof systems by establishing collapse results that reveal simplifications in their complexity landscape. By extending classical theorems such as the Karp-Lipton theorem to quantum settings and analyzing uniqueness in quantum-classical PCPs, we clarify how various constraints influence computational power. Our main contributions are: (1) We show that restricting quantum-classical PCPs to unique proofs does not reduce their power: $\mathsf{UniqueQCPCP} = \mathsf{QCPCP}$ under $\mathsf{BQ}$-operator and randomized reductions. This parallels the known $\mathsf{UniqueQCMA} = \mathsf{QCMA}$ result, indicating robustness of uniqueness even in quantum PCP-type systems. (2) We prove a non-uniform quantum analogue of the Karp-Lipton theorem: if $\mathsf{QMA} \subseteq \mathsf{BQP}/\mathsf{qpoly}$, then $\mathsf{QPH} \subseteq \mathsf{Q\Sigma}_2/\mathsf{qpoly}$. This conditional collapse suggests limits on quantum advice for $\mathsf{QMA}$-complete problems. (3) We define a bounded-entanglement version of the quantum polynomial hierarchy, $\mathsf{BEQPH}$, and prove that it collapses above the fourth level. We also introduce the separable hierarchy $\mathsf{SepQPH}$ (zero entanglement), for which the same collapse result holds. These collapses stem not from entanglement, as in prior work, but from the convex structure of the protocols, which renders higher levels tractable. Collectively, these results offer new insights into the structure of quantum proof systems and the role of entanglement, uniqueness, and advice in defining their complexity.
- Abstract（参考訳）: 本稿では, 量子証明システムの構造を, 複雑性の状況における単純化を明らかにする崩壊結果の確立によって検討する。
カルプ・リプトンの定理のような古典的定理を量子的設定に拡張し、量子古典的PCPの特異性を解析することにより、様々な制約が計算力にどのように影響するかを明らかにする。
1) 量子古典的PCPを一意の証明に制限することは、そのパワーを低下させるものではないことを示す: $\mathsf{UniqueQCPCP} = \mathsf{QCPCP}$ under $\mathsf{BQ}$-operatorized reductions。
これは既知の $\mathsf{UniqueQCMA} = \mathsf{QCMA}$の結果と平行であり、量子PCP型システムにおいても一意性の堅牢性を示す。
2) カープ・リプトンの定理の非一様量子アナログを証明している: if $\mathsf{QMA} \subseteq \mathsf{BQP}/\mathsf{qpoly}$, then $\mathsf{QPH} \subseteq \mathsf{Q\Sigma}_2/\mathsf{qpoly}$。
この条件の崩壊は、$\mathsf{QMA}$-complete問題に対する量子アドバイスの制限を示唆している。
(3) 量子多項式階層の有界絡み合いバージョン、$\mathsf{BEQPH}$を定義し、それが第4レベル以上で崩壊することを証明する。
また、分離可能な階層 $\mathsf{SepQPH}$ (ゼロエンタングルメント) を導入する。
これらの崩壊は、以前の研究のように絡み合いではなく、プロトコルの凸構造によるもので、より高いレベルの引き込みが可能である。
これらの結果は、量子証明システムの構造と、その複雑性を定義する上での絡み合い、一意性、アドバイスの役割に関する新たな洞察を提供する。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。