A Caltech Library Service


Ji, Zhengfeng and Natarajan, Anand and Vidick, Thomas and Wright, John and Yuen, Henry (2021) MIP* = RE. Communications of the ACM, 64 (11). pp. 131-138. ISSN 0001-0782. doi:10.1145/3485628.

[img] PDF - Published Version
See Usage Policy.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


The complexity class NP characterizes the collection of computational problems that have efficiently verifiable solutions. With the goal of classifying computational problems that seem to lie beyond NP, starting in the 1980s complexity theorists have considered extensions of the notion of efficient verification that allow for the use of randomness (the class MA), interaction (the class IP), and the possibility to interact with multiple proofs, or provers (the class MIP). The study of these extensions led to the celebrated PCP theorem and its applications to hardness of approximation and the design of cryptographic protocols. In this work, we study a fourth modification to the notion of efficient verification that originates in the study of quantum entanglement. We prove the surprising result that every problem that is recursively enumerable, including the Halting problem, can be efficiently verified by a classical probabilistic polynomial-time verifier interacting with two all-powerful but noncommunicating provers sharing entanglement. The result resolves long-standing open problems in the foundations of quantum mechanics (Tsirelson's problem) and operator algebras (Connes' embedding problem).

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Ji, Zhengfeng0000-0002-7659-3178
Natarajan, Anand0000-0003-3648-3844
Vidick, Thomas0000-0002-6405-365X
Additional Information:© 2021 Association for Computing Machinery. Published: 25 October 2021. We thank Matthew Coudron, William Slofstra and Jalex Stark for enlightening discussions regarding possible consequences of our work. We thank William Slofstra and Jalex Stark for suggestions regarding explicit separations between C_(qa) and C_(qc). We thank Peter Burton, William Slofstra and Jalex Stark for comments on a previous version. Zhengfeng Ji is supported by Australian Research Council (DP200100950). Anand Natarajan is supported by IQIM, an NSF Physics Frontiers Center (NSF Grant PHY-1733907). Thomas Vidick is supported by NSF CAREER Grant CCF-1553477, AFOSR YIP award number FA9550-16-1-0495, a CIFAR Azrieli Global Scholar award, MURI Grant FA9550-18-1-0161 and the IQIM, an NSF Physics Frontiers Center (NSF Grant PHY-1125565) with support of the Gordon and Betty Moore Foundation (GBMF-12500028). Henry Yuen is supported by NSERC Discovery Grant 2019-06636. Part of this work was done while John Wright was at the Massachusetts Institute of Technology. He is supported by IQIM, an NSF Physics Frontiers Center (NSF Grant PHY-1733907), and by ARO contract W911NF-17-1-0433.
Group:Institute for Quantum Information and Matter
Funding AgencyGrant Number
Australian Research CouncilDP200100950
Air Force Office of Scientific Research (AFOSR)FA9550-16-1-0495
Canadian Institute for Advanced Research (CIFAR)UNSPECIFIED
Air Force Office of Scientific Research (AFOSR)FA9550-18-1-0161
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
Gordon and Betty Moore FoundationGBMF-12500028
Natural Sciences and Engineering Research Council of Canada (NSERC)2019-06636
Army Research Office (ARO)W911NF-17-1-0433
Issue or Number:11
Record Number:CaltechAUTHORS:20200417-131646685
Persistent URL:
Official Citation:Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. 2021. MIP* = RE. Commun. ACM 64, 11 (November 2021), 131–138. DOI:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:102605
Deposited By: George Porter
Deposited On:17 Apr 2020 20:30
Last Modified:29 Oct 2021 20:08

Repository Staff Only: item control page