The central question in quantum multi-prover interactive proof systems is whether or not entanglement shared among provers affects the verification power of the proof system. We study for the first time positive aspects of prior entanglement and show how it can be used to parallelize any multi- prover quantum interactive proof system to a one-round system with perfect completeness, soundness bounded away from 1 by an inverse polynomial in the input size, and one extra proven Alternatively, we can also parallelize to a three-turn system with the same number of provers, where the verifier only broadcasts the outcome of a coin flip. This "public-coin" property is somewhat surprising, since in the classical case public-coin multi-prover interactive proofs are equivalent to single prover ones.
The central question in quantum multi-prover interactive proof systems is whether or not entanglement shared among provers affects the verification power of the proof system. We study for the first time positive aspects of prior entanglement and show how it can be used to parallelize any multi- prover quantum interactive proof system to a one-round system with perfect completeness, soundness bounded away from 1 by an inverse polynomial in the input size, and one extra proven Alternatively, we can also parallelize to a three-turn system with the same number of provers, where the verifier only broadcasts the outcome of a coin flip. This "public-coin" property is somewhat surprising, since in the classical case public-coin multi-prover interactive proofs are equivalent to single prover ones.
The central question in quantum multi-prover interactive proof systems is whether or not entanglement shared between provers affects the verification power of the proof system. We study for the first time positive aspects of prior entanglement and show that entanglement is useful even for honest provers. We show how to use shared entanglement to parallelize any multi-prover quantum interactive proof system to a one-round system with perfect completeness, with one extra prover. Alternatively, we can also parallelize to a three-turn system with the same number of provers, where the verifier only broadcasts the outcome of a coin flip. This "public-coin" property is somewhat surprising, since in the classical case public-coin multi-prover interactive proofs are equivalent to single prover ones.
Multi Prover Interactive Proof systems (MIPs)were first presented in a cryptographic context, but ever since they were used in various fields. Understanding the power of MIPs in the quantum context raises many open problems, as there are several interesting models to consider. For example, one can study the question when the provers share entanglement or not, and the communication between the verifier and the provers is quantum or classical. While there are several partial results on the subject, so far no one presented an efficient scheme for recognizing NEXP (or NP with logarithmic communication), except for [KM03], in the case there is no entanglement (and of course no communication between the provers). We introduce another variant of Quantum MIP, where the provers do not share entanglement, the communication between the verifier and the provers is quantum, but the provers are unlimited in the classical communication between them. At first, this model may seem very weak, as provers who exchange information seem to be equivalent in power to a simple prover. This in fact is not the case - we show that any language in NEXP can be recognized in this model efficiently, with just two provers and two rounds of communication, with a constant completeness-soundness gap.
It is known that there exist multi-prover interactive protocols (MIP protocols) for the complexity class NEXP, succinct MIP protocols for NP and multi-prover interactive protocols with shared entanglement (MIP∗ protocols) for RE. This extraordinary power of multi-prover interactive proof systems comes from the assumption that provers do not communicate with each other during the protocols. If they are allowed to communicate freely, the setting is the same as in the single-prover case, and the computational power of the system becomes significantly weaker.
In this paper, we investigate for the first time the setting where communication (i.e., leakage of information) between provers is allowed but bounded. We introduce two techniques to approach this question and show that multi-prover interactive proof systems are robust against some amount of leakage. Our first technique is based on parallel repetition theorems. We apply it to show that for any polynomial p, we can construct two-prover one-round MIP and MIP∗ protocols for NEXP and RE, respectively, that are robust against p(n) bits of leakage. We further derive our second technique to convert any low-soundness PCP construction to a two-prover one-round MIP protocol for NP robust against leakage. We also discuss the relation between robustness against leakage in multi-prover interactive proof systems and the Sliding Scale Conjecture in the PCP literature.
We show that any number of parties can coherently exchange any one pure quantum state for another, without communication, given prior shared entanglement. Two applications of this fact to the study of multi-prover quantum interactive proof systems are given. First, we prove that there exists a one-round two-prover quantum interactive proof system for which no finite amount of shared entanglement allows the provers to implement an optimal strategy. More specifically, for every fixed input string, there exists a sequence of strategies for the provers, with each strategy requiring more entanglement than the last, for which the probability for the provers to convince the verifier to accept approaches 1. It is not possible, however, for the provers to convince the verifier to accept with certainty with a finite amount of shared entanglement. The second application is a simple proof that multi-prover quantum interactive proofs can be transformed to have near-perfect completeness by the addition of one round of communication.
This paper presents three results on the power of two-prover one-round interactive proof systems based on oracularization under the existence of prior entanglement between dishonest provers. It is proved that the two-prover one-round interactive proof system for PSPACE by Cai, Condon, and Lipton [JCSS 48:183-193, 1994] still achieves exponentially small soundness error in the existence of prior entanglement between dishonest provers (and more strongly, even if dishonest provers are allowed to use arbitrary no-signaling strategies). It follows that, unless the polynomial-time hierarchy collapses to the second level, two-prover systems are still advantageous to single-prover systems even when only malicious provers can use quantum information. It is also shown that a "dummy" question may be helpful when constructing an entanglement-resistant multi-prover system via oracularization. This affirmatively settles a question posed by Kempe et al. [FOCS 2008, pp. 447-456] and every language in NEXP is proved to have a two-prover one-round interactive proof system even against entangled provers, albeit with exponentially small gap between completeness and soundness. In other words, it is NP-hard to approximate within an inverse-polynomial the value of a classical two-prover one-round game against entangled provers. Finally, both for the above proof system for NEXP and for the quantum two-prover one-round proof system for NEXP proposed by Kempe et al., it is proved that exponentially small completeness-soundness gaps are best achievable unless soundness analysis uses the structure of the underlying system with unentangled provers.
We introduce another variant of quantum MIP, where the provers do not share entanglement, the communication between the verifier and the provers is quantum, but the provers are unlimited in the classical communication between them. At first, this model may seem very weak, as provers who exchange information seem to be equivalent in power to a simple prover. This in fact is not the case-we show that any language in NEXP can be recognized in this model efficiently, with just two provers and two rounds of communication, with a constant completeness-soundness gap. Similar ideas and techniques may help help with other models of quantum MIP, including the dual question, of non communicating provers with unlimited entanglement.