A Caltech Library Service

NEEXP is Contained in MIP*

Natarajan, Anand and Wright, John (2019) NEEXP is Contained in MIP*. In: 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS). IEEE , Piscataway, NJ, pp. 510-518. ISBN 9781728149523.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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 of NEEXP = NTIME[2^(2poly(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.

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper
Natarajan, Anand0000-0003-3648-3844
Alternate Title:NEEXP ⊆ MIP*
Additional Information:© 2019 IEEE. AN was partially supported by NSF grant CCF-1452616. JW was partially supported by ARO contract W911NF-17-1-0433. Both authors acknowledge funding provided by the Institute for Quantum Information and Matter, an NSF Physics Frontiers Center (NSF Grant PHY-1733907).
Group:Institute for Quantum Information and Matter
Funding AgencyGrant Number
Army Research Office (ARO)W911NF-17-1-0433
Record Number:CaltechAUTHORS:20200109-143243997
Persistent URL:
Official Citation:A. Natarajan and J. Wright, "NEEXP is Contained in MIP*," 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), Baltimore, MD, USA, 2019, pp. 510-518. doi: 10.1109/FOCS.2019.00039
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:100610
Deposited By: George Porter
Deposited On:10 Jan 2020 16:20
Last Modified:16 Nov 2021 17:55

Repository Staff Only: item control page