A Caltech Library Service


Ji, Zhengfeng and Natarajan, Anand and Vidick, Thomas and Wright, John and Yuen, Henry (2020) MIP*=RE. . (Unpublished)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


We show that the class MIP* of languages that can be decided by a classical verifier interacting with multiple all-powerful quantum provers sharing entanglement is equal to the class RE of recursively enumerable languages. Our proof builds upon the quantum low-degree test of (Natarajan and Vidick, FOCS 2018) by integrating recent developments from (Natarajan and Wright, FOCS 2019) and combining them with the recursive compression framework of (Fitzsimons et al., STOC 2019). An immediate byproduct of our result is that there is an efficient reduction from the Halting Problem to the problem of deciding whether a two-player nonlocal game has entangled value 1 or at most 1/2. Using a known connection, undecidability of the entangled value implies a negative answer to Tsirelson's problem: we show, by providing an explicit example, that the closure C_(qa) of the set of quantum tensor product correlations is strictly included in the set C_(qc) of quantum commuting correlations. Following work of (Fritz, Rev. Math. Phys. 2012) and (Junge et al., J. Math. Phys. 2011) our results provide a refutation of Connes' embedding conjecture from the theory of von Neumann algebras.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Natarajan, Anand0000-0003-3648-3844
Vidick, Thomas0000-0002-6405-365X
Additional Information: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
Record Number:CaltechAUTHORS:20200417-131646685
Persistent URL:
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:04 Jun 2020 10:14

Repository Staff Only: item control page