論文の概要: Classical versus quantum queries in quantum PCPs with classical proofs

• arxiv url: http://arxiv.org/abs/2411.00946v1
• Date: Fri, 01 Nov 2024 18:00:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-05 21:28:13.881015
• Title: Classical versus quantum queries in quantum PCPs with classical proofs
• Title（参考訳）: 古典的証明を伴う量子PCPにおける古典的対量子的クエリ
• Authors: Harry Buhrman, François Le Gall, Jordi Weggemans,
• Abstract要約: 量子古典PCPを一般化し、古典的な証明に$q$の量子クエリを適用できるようにします。 驚くべきことに、このことは、定数量子古典量に対して逆から定数への約束のギャップを増幅できることを示している。 約束のギャップは達成できるが、我々の結果は、$mathsfQCMA$に対する定型クエリ量子古典的PCPが存在しないという強い証拠を与える。
• 参考スコア（独自算出の注目度）: 0.3004066195320147
• License:
• Abstract: We generalize quantum-classical PCPs, first introduced by Weggemans, Folkertsma and Cade (TQC 2024), to allow for $q$ quantum queries to a polynomially-sized classical proof ($\mathsf{QCPCP}_{Q,c,s}[q]$). Exploiting a connection with the polynomial method, we prove that for any constant $q$, promise gap $c-s = \Omega(1/\text{poly}(n))$ and $\delta>0$, we have $\mathsf{QCPCP}_{Q,c,s}[q] \subseteq \mathsf{QCPCP}_{1-\delta,1/2+\delta}[3] \subseteq \mathsf{BQ} \cdot \mathsf{NP}$, where $\mathsf{BQ} \cdot \mathsf{NP}$ is the class of promise problems with quantum reductions to an $\mathsf{NP}$-complete problem. Surprisingly, this shows that we can amplify the promise gap from inverse polynomial to constant for constant query quantum-classical PCPs, and that any quantum-classical PCP making any constant number of quantum queries can be simulated by one that makes only three classical queries. Nevertheless, even though we can achieve promise gap amplification, our result also gives strong evidence that there exists no constant query quantum-classical PCP for $\mathsf{QCMA}$, as it is unlikely that $\mathsf{QCMA} \subseteq \mathsf{BQ} \cdot \mathsf{NP}$, which we support by giving oracular evidence. In the (poly-)logarithmic query regime, we show for any positive integer $c$, there exists an oracle relative to which $\mathsf{QCPCP}[\mathcal{O}(\log^c n)] \subsetneq \mathsf{QCPCP}_Q[\mathcal{O}(\log^c n)]$, contrasting the constant query case where the equivalence of both query models holds relative to any oracle. Finally, we connect our results to more general quantum-classical interactive proof systems.
• Abstract（参考訳）: Weggemans, Folkertsma and Cade (TQC 2024)によって最初に導入された量子古典的PCPを一般化し、多項式サイズの古典的証明(\mathsf{QCPCP}_{Q,c,s}[q]$)に$q$の量子クエリを可能にする。 q$, promise gap $c-s = \Omega(1/\text{poly}(n))$ and $\delta>0$, have $\mathsf{QCPCP}_{Q,s}[q] \subseteq \mathsf{QCPCP}_{1-\delta,1/2+\delta}[3] \subseteq \mathsf{BQ} \cdot \mathsf{NP}$, ここで$\mathsf{BQ} \cdot \mathsf{NP}$は$\mathsf{BQ}-完全問題への量子還元のクラスである。 驚くべきことに、これは逆多項式から定数の量子古典的PCPに対する定数への約束ギャップを増幅することができ、量子古典的PCPの定数数を構成する任意の量子古典的PCPは、古典的クエリを3つだけ作る1つでシミュレートできることを示している。 しかしながら、我々の結果は、約束ギャップの増幅を達成できたとしても、$\mathsf{QCMA}$に対して一定のクエリ量子古典的PCPが存在しないという強い証拠を与える。 任意の正の整数 $c$ に対して、あるオラクルに対して $\mathsf{QCPCP}[\mathcal{O}(\log^c n)] \subsetneq \mathsf{QCPCP}_Q[\mathcal{O}(\log^c n)]$ が存在することを示す。 最後に、我々の結果をより一般的な量子古典的対話型証明システムに接続する。

関連論文リスト

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• 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)
• Lower Bounds for Unitary Property Testing with Proofs and Advice [0.0]
  本稿では,一元性検定における量子クエリの下位境界を証明するための新しい手法を提案する。 すべての得られる下限は$mathsfC$-testerで$mathsfC subseteq mathsfQMA(2)/mathsfqpoly$である。 我々は、$mathsfQMA(2) notsupset mathsfSBQP$と$mathsfQMA/mathsfqpolyの量子オラクルが存在することを示した。
  論文  参考訳（メタデータ） (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)
• SQ Lower Bounds for Learning Bounded Covariance GMMs [46.289382906761304]
  P= sum_i=1k w_i MathcalN(boldsymbol mu_i,mathbf Sigma_i)$ という形で、分離されたガウスの混合を $mathbbRd$ で学習することに焦点を当てる。 この問題に対する統計的クエリ(SQ)アルゴリズムは、少なくともdOmega (1/epsilon)$の複雑さを必要とすることを証明している。
  論文  参考訳（メタデータ） (2023-06-22T17:23:36Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  浅量子回路の計算能力と古典計算の組合せを包括的に評価する。 いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
  論文  参考訳（メタデータ） (2022-10-12T17:54:02Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。 振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
  論文  参考訳（メタデータ） (2022-01-31T22:19:49Z)
• 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)

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

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