The class MIP* of quantum multiprover interactive proof systems with entanglement is much more powerful than its classical counterpart MIP [ 8 , 31 , 32 ]: while MIP = NEXP, the quantum class MIP * is equal to RE, a class including the halting problem. This is because the provers in MIP * can share unbounded quantum entanglement. However, recent works [ 53 , 54 ] have shown that this advantage is significantly reduced if the provers’ shared state contains noise. This article attempts to exactly characterize the effect of noise on the computational power of quantum multiprover interactive proof systems. We investigate the quantum two-prover one-round interactive system MIP * [poly, O (1)], where the verifier sends polynomially many bits to the provers and the provers send back constantly many bits. We show that noise completely destroys the computational advantage given by shared entanglement in this model. Specifically, we show that if the provers are allowed to share arbitrarily many EPR states, where each EPR state is affected by an arbitrarily small constant amount of noise, the resulting complexity class is equivalent to NEXP = MIP. This improves significantly on the previous best-known bound of NEEEXP (nondeterministic triply exponential time) [ 53 ]. We also show that this collapse in power is due to noise, rather than the O (1) answer size, by showing that allowing for noiseless EPR states gives the class the full power of RE = MIP * [poly, poly]. Along the way, we develop two technical tools of independent interest. First, we give a new, deterministic tester for the positivity of an exponentially large matrix, provided that it has a low-degree Fourier decomposition in terms of Pauli matrices. Secondly, we develop a new invariance principle for smooth matrix functions having bounded third-order Fréchet derivatives or which are Lipschitz continuous.
The class MIP* of quantum multiprover interactive proof systems with entanglement is much more powerful than its classical counterpart MIP [ 8 , 31 , 32 ]: while MIP = NEXP, the quantum class MIP * is equal to RE, a class including the halting problem. This is because the provers in MIP * can share unbounded quantum entanglement. However, recent works [ 53 , 54 ] have shown that this advantage is significantly reduced if the provers’ shared state contains noise. This article attempts to exactly characterize the effect of noise on the computational power of quantum multiprover interactive proof systems. We investigate the quantum two-prover one-round interactive system MIP * [poly, O (1)], where the verifier sends polynomially many bits to the provers and the provers send back constantly many bits. We show that noise completely destroys the computational advantage given by shared entanglement in this model. Specifically, we show that if the provers are allowed to share arbitrarily many EPR states, where each EPR state is affected by an arbitrarily small constant amount of noise, the resulting complexity class is equivalent to NEXP = MIP. This improves significantly on the previous best-known bound of NEEEXP (nondeterministic triply exponential time) [ 53 ]. We also show that this collapse in power is due to noise, rather than the O (1) answer size, by showing that allowing for noiseless EPR states gives the class the full power of RE = MIP * [poly, poly]. Along the way, we develop two technical tools of independent interest. First, we give a new, deterministic tester for the positivity of an exponentially large matrix, provided that it has a low-degree Fourier decomposition in terms of Pauli matrices. Secondly, we develop a new invariance principle for smooth matrix functions having bounded third-order Fréchet derivatives or which are Lipschitz continuous.
We study multiprover interactive proof systems. The power of classical multiprover interactive proof systems, in which the provers do not share entanglement, was characterized in a famous work by Babai, Fortnow, and Lund (Computational Complexity 1991), whose main result was the equality MIP = NEXP. The power of quantum multiprover interactive proof systems, in which the provers are allowed to share entanglement, has proven to be much more difficult to characterize. The best known lower-bound on MIP* is NEXP ⊆ MIP* due to Ito and Vidick (FOCS 2012). As for upper bounds, MIP* could be as large as RE, the class of recursively enumerable languages. The main result of this work is the inclusion NEEXP = NTIME[22poly(n)] ⊆ MIP*. This is an exponential improvement over the prior lower bound and shows that proof systems with entangled provers are at least exponentially more powerful than classical provers. In our protocol the verifier delegates a classical, exponentially large MIP protocol for NEEXP to two entangled provers: the provers obtain their exponentially large questions by measuring their shared state, and use a classical PCP to certify the correctness of their exponentially-long answers. For the soundness of our protocol, it is crucial that each player should not only sample its own question correctly but also avoid performing measurements that would reveal the other player's sampled question. We ensure this by commanding the players to perform a complementary measurement, relying on the Heisenberg uncertainty principle to prevent the forbidden measurements from being performed.
A recent work studied quantum two-prover one-round proof systems MIPψ[poly,O(1)]. It showed that when ψ is a noisy EPR state with quantum maximal correlation ρmax(ψ)<1, the resulting complexity class is equivalent to NEXP=MIP. In contrast, MIPEPR[poly,O(1)]=RE. Not all noise, however, decreases quantum maximal correlation. A basic example is dephasing noise: a dephased EPR pair retain quantum maximal correlation 1. In this work, we remove the constant-answer restriction and establish a complete dichotomy for MIPψ[poly,poly], where the provers share arbitrarily many copies of EPR pairs subject to unital noise. Equivalently, let ψ be a fixed two-qubit state with maximally mixed marginals. We prove that MIPψ[poly,poly]=MIP=NEXP,if ψ is separable or ρmax(ψ)<1;MIPψ[poly,poly]=MIPψ[poly,O(1)]=RE,if ψ is entangled and ρmax(ψ)=1. Beyond the complexity classification, our proof develops two techniques that may be useful more broadly in quantum information and quantum complexity. First, we introduce a positivity-preserving low-degree approximation framework for quantum measurements: instead of truncating positive operators directly in the Pauli basis, we approximate suitable square-root factorizations, simultaneously achieving low Pauli degree, positivity, and global control over an entire POVM. Second, we develop a new dimension-reduction method, called Pauli folding, for low-degree positive operators. Its key ingredient is an almost-multiplicativity theorem for randomized Pauli hashing, which allows noncommutative products, positivity, and normalization to survive compression with controlled error.
We study multiprover interactive proof systems. The power of classical multiprover interactive proof systems, in which the provers do not share entanglement, was characterized in a famous work by Babai, Fortnow, and Lund (Computational Complexity 1991), whose main result was the equality MIP = NEXP. The power of quantum multiprover interactive proof systems, in which the provers are allowed to share entanglement, has proven to be much more difficult to characterize. The best known lower-bound on MIP* is NEXP, due to Ito and Vidick (FOCS 2012). As for upper bounds, MIP* could be as large as RE, the class of recursively enumerable languages. The main result of this work is the inclusion of NEEXP (nondeterministic doubly exponential time) in MIP*. This is an exponential improvement over the prior lower bound and shows that proof systems with entangled provers are at least exponentially more powerful than classical provers. In our protocol the verifier delegates a classical, exponentially large MIP protocol for NEEXP to two entangled provers: the provers obtain their exponentially large questions by measuring their shared state, and use a classical PCP to certify the correctness of their exponentially-long answers. For the soundness of our protocol, it is crucial that each player should not only sample its own question correctly but also avoid performing measurements that would reveal the other player's sampled question. We ensure this by commanding the players to perform a complementary measurement, relying on the Heisenberg uncertainty principle to prevent the forbidden measurements from being performed.
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.
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.
In 2020, a landmark result by Ji, Natarajan, Vidick, Wright, and Yuen showed that MIP*, the class of languages that can be decided by a classical verifier interacting with multiple computationally unbounded provers sharing entanglement in the tensor product model, is equal to RE. We show that the class MIPco, a complexity class defined similarly to MIP* except with provers sharing the commuting operator model of entanglement, is equal to the class coRE. This shows that giving the provers two different models of entanglement leads to two completely different computational powers for interactive proof systems. Our proof builds upon the compression theorem used in the proof of MIP*=RE, and we use the tracially embeddable strategies framework to show that the same compression procedure in MIP* =RE also has the same desired property in the commuting operator setting. We also give a more streamlined proof of the compression theorem for non-local games by incorporating the synchronous framework used by Mousavi et al. [STOC 2022], as well as the improved Pauli basis test introduced by de la Salle [ArXiv:2204.07084]. We introduce a new equivalence condition for RE/coRE-complete problems, which we call the weakly compressible condition. We show that both MIP* and MIPco satisfy this condition through the compression theorem, and thereby establish that the uncomputability for MIP* and MIPco can be proved under a unified framework (despite these two complexity classes being different). Notably, this approach also gives an alternative proof of the MIP*=RE theorem, which does not rely on the preservation of the entanglement bound. In addition to non-local games, this new condition could also potentially be applicable to other decision problems.