A Caltech Library Service

A Multi-prover Interactive Proof for NEXP Sound against Entangled Provers

Ito, Tsuyoshi and Vidick, Thomas (2012) A Multi-prover Interactive Proof for NEXP Sound against Entangled Provers. In: IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS). IEEE , Piscataway, NJ, pp. 243-252. ISBN 978-1-4673-4383-1.

PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Book Section
Related URLs:
URLURL TypeDescription DOIArticle Paper
Vidick, Thomas0000-0002-6405-365X
Additional Information:© 2012 IEEE. Tsuyoshi Ito is supported in part by ARO/NSA grant W911NF-09-1-0569. He was also supported by grants from NSERC, CIFAR, QuantumWorks, MITACS, CFI, and ORF received while he was a postdoctoral fellow at the Institute for Quantum Computing and David R. Cheriton School of Computer Science, University of Waterloo, Canada. Thomas Vidick is supported by the National Science Foundation under Grant No. 0844626. Part of this work was done while he was a graduate student in the Computer Science department at UC Berkeley, as well as during visits to the Perimeter Institute in Waterloo, Canada and NEC Labs America. Tsuyoshi Ito thanks John Watrous for helpful discussions. Thomas Vidick thanks Umesh Vazirani for many inspiring discussions throughout the time that this work was being carried out, and in particular for first suggesting to adapt Babai et al.’s multilinearity test to the entangled-prover setting. The authors also thank Scott Aaronson, Dmitry Gavinsky, Oded Regev, and an anonymous referee for helpful suggestions.
Funding AgencyGrant Number
Army Research Office (ARO)W911NF-09-1-0569
Natural Sciences and Engineering Research Council of Canada (NSERC)UNSPECIFIED
Canadian Institute for Advanced Research (CIFAR)UNSPECIFIED
Canada Foundation for InnovationUNSPECIFIED
Ontario Research FundUNSPECIFIED
Subject Keywords:quantum interactive proofs; multiple provers; entanglement
Record Number:CaltechAUTHORS:20140910-100733064
Persistent URL:
Official Citation:Ito, T.; Vidick, T., "A Multi-prover Interactive Proof for NEXP Sound against Entangled Provers," Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on , vol., no., pp.243,252, 20-23 Oct. 2012 doi: 10.1109/FOCS.2012.11 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:49530
Deposited By: Tony Diaz
Deposited On:10 Sep 2014 18:35
Last Modified:10 Nov 2021 18:45

Repository Staff Only: item control page