Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians

Abstract

We define a general formulation of quantum PCPs, which captures adaptivity and multiple unentangled provers, and give a detailed construction of the quantum reduction to a local Hamiltonian with a constant promise gap. The reduction turns out to be a versatile subroutine to prove properties of quantum PCPs, allowing us to show: (i) Non-adaptive quantum PCPs can simulate adaptive quantum PCPs when the number of proof queries is constant. In fact, this can even be shown to hold when the non-adaptive quantum PCP picks the proof indices simply uniformly at random from a subset of all possible index combinations, answering an open question by Aharonov, Arad, Landau and Vazirani (STOC '09). (ii) If the $q$-local Hamiltonian problem with constant promise gap can be solved in $\mathsf{QCMA}$, then $\mathsf{QPCP}[q]\subseteq \mathsf{QCMA}$ for any $q\in O(1)$. (iii) If $\mathsf{QMA}(k)$ has a quantum PCP for any $k\le \text{poly}(n)$, then $\mathsf{QMA}(2)=\mathsf{QMA}$, connecting two of the longest-standing open problems in quantum complexity theory. Moreover, we also show that there exist (quantum) oracles relative to which certain quantum PCP statements are false. Hence, any attempt to prove the quantum PCP conjecture requires, just as was the case for the classical PCP theorem, (quantumly) non-relativizing techniques.

Published version. 53 pages, 1 figure

References in corpus (13)

• Strengths and Weaknesses of Quantum Computing
• User-friendly tail bounds for sums of random matrices
• Symmetry implies independence
• N-representability is QMA-complete
• One-and-a-half quantum de Finetti theorems
• Faithful Squashed Entanglement
• Simulation of Many-Body Hamiltonians using Perturbation Theory with Bounded-Strength Interactions
• NLTS Hamiltonians from good quantum codes
• Product-state Approximations to Quantum Ground States
• The Complexity of the Separable Hamiltonian Problem
• Improved Hardness Results for the Guided Local Hamiltonian Problem
• The 7 faces of quantum NP
• Combinatorial NLTS From the Overlap Gap Property