Classical versus quantum queries in quantum PCPs with classical proofs

• URL: http://arxiv.org/abs/2411.00946v1
• Date: Fri, 01 Nov 2024 18:00:56 GMT
• Title: Classical versus quantum queries in quantum PCPs with classical proofs
• Authors: Harry Buhrman, François Le Gall, Jordi Weggemans,
• Abstract summary: We generalize quantum-classical PCPs to allow for $q$ quantum queries to a classical proof. Surprisingly, this shows that we can amplify the promise gap from inverse to constant for constant query quantum-classicals. Even though we can achieve promise gap, our result also gives strong evidence that there exists no constant query quantum-classical PCP for $mathsfQCMA$.
• Score: 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.

Related papers

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians [0.0]
  We show that non-adaptive quantum PCPs can simulate adaptive quantum PCPs when the number of proof queries is constant. We also show that there exists (quantum) oracles relative to which certain quantum PCP statements are false.
  arXiv  Detail & Related papers  (2024-03-07T19:00:06Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• Lower Bounds for Unitary Property Testing with Proofs and Advice [0.0]
  We propose a new technique for proving lower bounds on the quantum query of unitary property testing. All obtained lower bounds hold for any $mathsfC$-tester with $mathsfC subseteq mathsfQMA(2)/mathsfqpoly$. We show that there exist quantum oracles relative to which $mathsfQMA(2) notsupset mathsfSBQP$ and $mathsfQMA/mathsfqpoly
  arXiv  Detail & Related papers  (2024-01-15T19:00:36Z)
• Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds [1.3927943269211591]
  This work studies three quantum-verifier based generalizations of $mathsfPH$. We first resolve several open problems from [GSSSY22], including a collapse theorem and a Karp-Lipton theorem for $mathsfQCPH$. We show one-sided error reduction for $mathsfpureQPH$, as well as the first bounds relating these quantum variants of $mathsfPH$.
  arXiv  Detail & Related papers  (2024-01-03T09:12:25Z)
• The Entangled Quantum Polynomial Hierarchy Collapses [0.0]
  We show that the entangled quantum quantum hierarchy $mathsfQEPH$ collapses to its second level. We also show that only quantum superposition (not classical probability) increases the computational power of these hierarchies.
  arXiv  Detail & Related papers  (2024-01-02T22:25:56Z)
• SQ Lower Bounds for Learning Bounded Covariance GMMs [46.289382906761304]
  We focus on learning mixtures of separated Gaussians on $mathbbRd$ of the form $P= sum_i=1k w_i mathcalN(boldsymbol mu_i,mathbf Sigma_i)$. We prove that any Statistical Query (SQ) algorithm for this problem requires complexity at least $dOmega (1/epsilon)$.
  arXiv  Detail & Related papers  (2023-06-22T17:23:36Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
  arXiv  Detail & Related papers  (2022-10-12T17:54:02Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
  arXiv  Detail & Related papers  (2022-01-31T22:19:49Z)
• Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
  Two models of quantum computation: CQ_d and QC_d. CQ_d captures the scenario of a d-depth quantum computer many times; QC_d is more analogous to measurement-based quantum computation. We show that, despite the similarities between CQ_d and QC_d, the two models are intrinsically, i.e. CQ_d $nsubseteq$ QC_d and QC_d $nsubseteq$ CQ_d relative to an oracle.
  arXiv  Detail & Related papers  (2022-01-06T03:10:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.