In this paper we introduce a quantum analogue of multi-prover interactive proof systems by naturally extending the model of single-prover quantum interactive proof systems defined by Watrous. It is proved that the class of languages having quantum multi-prover interactive proof systems is equal to NEXP. It implies that the quantum analogue has no gain to the classical counterpart in the setting of multi-prover interactive proof systems. Another interesting result shown in this paper is that, in case the prover does not have his private qubits, the class of languages having single-prover quantum interactive proof systems is also equal to NEXP. To our knowledge, our results give the first exact characterizations of a classical time complexity class in quantum computational terms.
In this paper we introduce a quantum analogue of multi-prover interactive proof systems by naturally extending the model of single-prover quantum interactive proof systems defined by Watrous. It is proved that the class of languages having quantum multi-prover interactive proof systems is equal to NEXP. It implies that the quantum analogue has no gain to the classical counterpart in the setting of multi-prover interactive proof systems. Another interesting result shown in this paper is that, in case the prover does not have his private qubits, the class of languages having single-prover quantum interactive proof systems is also equal to NEXP. To our knowledge, our results give the first exact characterizations of a classical time complexity class in quantum computational terms.
This paper gives the first formal treatment of a quantum analogue of multi-prover interactive proof systems. It is proved that the class of languages having quantum multi-prover interactive proof systems is necessarily contained in NEXP, under the assumption that provers are allowed to share at most polynomially many prior-entangled qubits. This implies that, in particular, if provers do not share any prior entanglement with each other, the class of languages having quantum multi-prover interactive proof systems is equal to NEXP. Related to these, it is shown that, in the case a prover does not have his private qubits, the class of languages having quantum single-prover interactive proof systems is also equal to NEXP.
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.
The way entanglement influences the power of quantum and classical multi-prover interactive proof systems is a long-standing open question. We show that the class of languages recognized by quantum multi-prover interactive proof systems, QMIP, is equal to MIP*, the class of languages recognized by classical multi-prover interactive proof systems where the provers share entanglement. After the recent result by Jain, Ji, Upadhyay and Watrous showing that QIP=IP, our work completes the picture from the verifier's perspective by showing that also in the setting of multiple provers with shared entanglement, a quantum verifier is no more powerful than a classical one: QMIP=MIP*. Our techniques are based on the adaptation of universal blind quantum computation (a protocol recently introduced by us) to the context of interactive proof systems. We show that in the multi-prover scenario, shared entanglement has a positive effect in removing the need for a quantum verifier. As a consequence, our results show that the entire power of quantum information in multi-prover interactive proof systems is captured by the shared entanglement and not by the quantum communication.
Quantum information and computation provide a fascinating twist on the notion of proofs in computational complexity theory. For instance, one may consider a quantum computational analogue of the complexity class NP, known as QMA, in which a quantum state plays the role of a proof (also called a certificate or witness), and is checked by a polynomial-time quantum computation. For some problems, the fact that a quantum proof state could be a superposition over exponentially many classical states appears to offer computational advantages over classical proof strings. In the interactive proof system setting, one may consider a verifier and one or more provers that exchange and process quantum information rather than classical information during an interaction for a given input string, giving rise to quantum complexity classes such as QIP, QSZK, and QMIP* that represent natural quantum analogues of IP, SZK, and MIP. While quantum interactive proof systems inherit some properties from their classical counterparts, they also possess distinct and uniquely quantum features that lead to an interesting landscape of complexity classes based on variants of this model. In this survey we provide an overview of many of the known results concerning quantum proofs, computational models based on this concept, and properties of the complexity classes they define. In particular, we discuss non-interactive proofs and the complexity class QMA, single-prover quantum interactive proof systems and the complexity class QIP, statistical zero-knowledge quantum interactive proof systems and the complexity class QSZK, and multiprover interactive proof systems and the complexity classes QMIP, QMIP*, and MIP*.
We prove a strong limitation on the ability of entangled provers to collude in a multiplayer game. Our main result is the first nontrivial lower bound on the class MIP* of languages having multi-prover interactive proofs with entangled provers, namely MIP* contains NEXP, the class of languages decidable in non-deterministic exponential time. While Babai, Fort now, and Lund (Computational Complexity 1991) proved the celebrated equality MIP = NEXP in the absence of entanglement, ever since the introduction of the class MIP* it was open whether shared entanglement between the provers could weaken or strengthen the computational power of multi-prover interactive proofs. Our result shows that it does not weaken their computational power: MIP* contains MIP. At the heart of our result is a proof that Babai, Fort now, and Lund's multilinearity test is sound even in the presence of entanglement between the provers, and our analysis of this test could be of independent interest. As a byproduct we show that the correlations produced by any entangled strategy which succeeds in the multilinearity test with high probability can always be closely approximated using shared randomness alone.
We introduce a new variant of quantum multiprover interactive proofs (QMIP) where the provers and the verifier are quantum. The verifier can exchange quantum messages with the provers. The provers cannot communicate quantumly between themselves and do not share entanglement, but are unlimited in the classical communication between them, even after receiving messages from the verifier. We show that any language in nondeterministic exponential time (NEXP) can be recognized in this model efficiently, with just two provers and two rounds of communication, and with a constant completeness/soundness gap. This is in contrast to the result of [R. Jain et al., Comm. ACM, 53 (2010), pp. 102--109], which shows that QIP = PSPACE, or equivalently that the set of languages that can be recognized by a quantum verifier communicating with a single quantum prover is equal to PSPACE. To analyze the cheating power of the provers, we give them more power and allow them to perform any separable operation. We then show a unique two-phase protocol in which the provers first commit to a superposition of correct answers to all possible questions, and then in the second phase the verifier opens up the committed answer and checks for correctness and consistency.