The quantum PCP (QPCP) conjecture states that all problems in QMA, the quantum analogue of NP, admit quantum verifiers that only act on a constant number of qubits of a polynomial size quantum proof and have a constant gap between completeness and soundness. Despite an impressive body of work trying to prove or disprove the quantum PCP conjecture, it still remains widely open. The above-mentioned proof verification statement has also been shown equivalent to the QMA-completeness of the Local Hamiltonian problem with constant relative gap. Nevertheless, unlike in the classical case, no equivalent formulation in the language of multi-prover games is known. In this work, we propose a new type of quantum proof systems, the Pointer QPCP, where a verifier first accesses a classical proof that he can use as a pointer to which qubits from the quantum part of the proof to access. We define the Pointer QPCP conjecture, that states that all problems in QMA admit quantum verifiers that first access a logarithmic number of bits from the classical part of a polynomial size proof, then act on a constant number of qubits from the quantum part of the proof, and have a constant gap between completeness and soundness. We define a new QMA-complete problem, the Set Local Hamiltonian problem, and a new restricted class of quantum multi-prover games, called CRESP games. We use them to provide two other equivalent statements to the Pointer QPCP conjecture: the Set Local Hamiltonian problem with constant relative gap is QMA-complete; and the approximation of the maximum acceptance probability of CRESP games up to a constant additive factor is as hard as QMA. This is the first equivalence between a quantum PCP statement and the inapproximability of quantum multi-prover games.
The quantum PCP (QPCP) conjecture states that all problems in QMA, the quantum analogue of NP, admit quantum verifiers that only act on a constant number of qubits of a polynomial size quantum proof and have a constant gap between completeness and soundness. Despite an impressive body of work trying to prove or disprove the quantum PCP conjecture, it still remains widely open. The above-mentioned proof verification statement has also been shown equivalent to the QMA-completeness of the Local Hamiltonian problem with constant relative gap. Nevertheless, unlike in the classical case, no equivalent formulation in the language of multi-prover games is known. In this work, we propose a new type of quantum proof systems, the Pointer QPCP, where a verifier first accesses a classical proof that he can use as a pointer to which qubits from the quantum part of the proof to access. We define the Pointer QPCP conjecture, that states that all problems in QMA admit quantum verifiers that first access a logarithmic number of bits from the classical part of a polynomial size proof, then act on a constant number of qubits from the quantum part of the proof, and have a constant gap between completeness and soundness. We define a new QMA-complete problem, the Set Local Hamiltonian problem, and a new restricted class of quantum multi-prover games, called CRESP games. We use them to provide two other equivalent statements to the Pointer QPCP conjecture: the Set Local Hamiltonian problem with constant relative gap is QMA-complete; and the approximation of the maximum acceptance probability of CRESP games up to a constant additive factor is as hard as QMA. This is the first equivalence between a quantum PCP statement and the inapproximability of quantum multi-prover games.
The quantum PCP (QPCP) conjecture states that all problems in QMA, the quantum analogue of NP, admit quantum verifiers that only act on a constant number of qubits of a polynomial size quantum proof and have a constant gap between completeness and soundness. Despite an impressive body of work trying to prove or disprove the quantum PCP conjecture, it still remains widely open. The above-mentioned proof verification statement has also been shown equivalent to the QMA-completeness of the Local Hamiltonian problem with constant relative gap. Nevertheless, unlike in the classical case, no equivalent formulation in the language of multi-prover games is known. In this work, we propose a new type of quantum proof systems, the Pointer QPCP, where a verifier first accesses a classical proof that he can use as a pointer to which qubits from the quantum part of the proof to access. We define the Pointer QPCP conjecture, that states that all problems in QMA admit quantum verifiers that first access a logarithmic number of bits from the classical part of a polynomial size proof, then act on a constant number of qubits from the quantum part of the proof, and have a constant gap between completeness and soundness. We define a new QMA-complete problem, the Set Local Hamiltonian problem, and a new restricted class of quantum multi-prover games, called CRESP games. We use them to provide two other equivalent statements to the Pointer QPCP conjecture: the Set Local Hamiltonian problem with constant relative gap is QMA-complete; and the approximation of the maximum acceptance probability of CRESP games up to a constant additive factor is as hard as QMA. Our new conjecture is weaker than the original QPCP conjecture and hence provides a natural intermediate step towards proving the quantum PCP theorem. Furthermore, this is the first equivalence between a quantum PCP statement and the inapproximability of quantum multi-prover games.
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 QCMA , then QPCP[q]⊆QCMA for any q∈O(1) . (iii) If QMA(k) has a quantum PCP for any k≤poly(n) , then QMA(2)=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.
We give a quantum interactive proof system for the local Hamiltonian problem on n qubits in which (i) the verifier has a single round of interaction with five entangled provers, (ii) the verifier sends a classical message on O(log n) bits to each prover, who reply with a constant number of qubits, and (iii) completeness and soundness are separated by an inverse polynomial in n. As the same class of proof systems, without entanglement between the provers, is included in QCMA, our result provides the first indication that quantum multiprover interactive proof systems with entangled provers may be strictly more powerful than unentangled-prover interactive proof systems. A distinguishing feature of our protocol is that the completeness property requires honest provers to share a large entangled state, obtained as the encoding of the ground state of the local Hamiltonian via an error-correcting code. Our result can be interpreted as a first step towards a multiprover variant of the quantum PCP conjecture.
The model of interactive oracle proofs (IOP) generalizes the notion of probabilistically checkable proof (PCP), in which a static proof is verified probabilistically by querying a small number of bits, to the interactive setting: a polynomial-time verifier interacts with an unbounded prover, but is restricted to only reading a small number of bits, in total, from the messages sent by the prover. IOPs provide a relaxed setting in which to study local probabilistic verification. They have proved instrumental in devising efficient methods for verification through subsequent compilation into non-interactive or succinct protocols.
We study a quantum analogue of interactive oracle proofs (qIOP) in which the verifier and communication are both allowed to be quantum; yet the verifier is restricted to perform measurements only on a small number of qubits received from the prover. Our main result is a qIOP for any language in QMA, in which the total communication is polynomial but the verifier only reads a polylogarithmic number of qubits in total. The protocol has completeness parameter exponentially close to 1 and soundness bounded away from 1 by a constant. In the absence of a quantum PCP theorem, this provides the first information-theoretically sound local and robust characterization of QMA, albeit interactive.
Our protocol combines the use of a quantum locally testable code (LTC) with classical techniques, notably probabilistically checkable proofs of proximity (PCPP). We avoid the necessity for complex multi-qubit tests employed in other settings by leveraging the local indistinguishability property of the quantum LTC.
We give a quantum interactive proof system for the local Hamiltonian problem on n qubits in which (i) the verifier has a single round of interaction with five entangled provers, (ii) the verifier sends a classical message on O(log n) bits to each prover, who replies with a constant number of qubits, and (iii) completeness and soundness are separated by an inverse polynomial in n. As the same class of proof systems, without entanglement between the provers, is included in QCMA, our result provides the first indication that quantum multiprover interactive proof systems with entangled provers may be strictly more powerful than unentangled-prover interactive proof systems. A distinguishing feature of our protocol is that the completeness property requires honest provers to share a large entangled state, obtained as the encoding of the ground state of the local Hamiltonian via an error-correcting code. Our result can be interpreted as a first step towards a multiprover variant of the quantum PCP conjecture.
We initiate the study of quantum Interactive Oracle Proofs (qIOPs), a generalization of both quantum Probabilistically Checkable Proofs and quantum Interactive Proofs, as well as a quantum analogue of classical Interactive Oracle Proofs.
In the model of quantum Interactive Oracle Proofs, we allow multiple rounds of quantum interaction between the quantum prover and the quantum verifier, but the verifier has limited access to quantum resources. This includes both queries to the prover's messages and the complexity of the quantum circuits applied by the verifier. The question of whether QMA admits a quantum interactive oracle proof system is a relaxation of the quantum PCP Conjecture.
We show the following two main constructions of qIOPs, both of which are unconditional:
- We construct a qIOP for QMA in which the verifier shares polynomially many EPR pairs with the prover at the start of the protocol and reads only a constant number of qubits from the prover's messages.
- We provide a stronger construction of qIOP for QMA in which the verifier not only reads a constant number of qubits but also operates on a constant number of qubits overall, including those in their private registers. However, in this stronger setting, the communication complexity becomes exponential. This leaves open the question of whether strong qIOPs for QMA, with polynomial communication complexity, exist.
As a key component of our construction, we introduce a novel single prover many-qubits test, which may be of independent interest.