{"id":4512,"date":"2020-01-14T10:59:21","date_gmt":"2020-01-14T16:59:21","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=4512"},"modified":"2020-01-16T18:37:27","modified_gmt":"2020-01-17T00:37:27","slug":"mipre","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=4512","title":{"rendered":"MIP*=RE"},"content":{"rendered":"\n

Another Update (Jan. 16):<\/strong> Yet another reason to be excited about this result—one that somehow hadn’t occurred to me—is that, as far as I know, it’s the first-ever fully convincing example of a non-relativizing computability result<\/em>. See this comment<\/a> for more.<\/p>\n\n\n\n

Update:<\/strong> If you’re interested in the above topic, then you should probably stop reading this post right now, and switch to this better post<\/a> by Thomas Vidick, one of the authors of the new breakthrough. (Or this<\/a> by Boaz Barak or this<\/a> by Lance Fortnow or this<\/a> by Ken Regan.) (For background, also see Thomas Vidick\u2019s excellent piece<\/a> for the AMS Notices<\/em>.)<\/p>\n\n\n\n

Still here? Alright, alright…<\/p>\n\n\n\n

Here’s the paper<\/a>, which weighs in at 165 pages. The authors are Zhengfeng Ji<\/a>, Anand Natarajan<\/a>, my former postdoc Thomas Vidick<\/a>, John Wright<\/a> (who will be joining the CS faculty here at UT Austin this fall), and my wife Dana’s former student Henry Yuen<\/a>. Rather than pretending that I can provide intelligent commentary on this opus in the space of a day, I’ll basically just open my comment section to discussion and quote the abstract:<\/p>\n\n\n\n

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 Cqa<\/sub><\/em> of the set of quantum tensor product correlations is strictly included in the set Cqc<\/sub><\/em> 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. <\/p><\/blockquote>\n\n\n\n

To say it differently (in response to a commenter’s request), some of the major implications are as follows.<\/p>\n\n\n\n

(1) There is a protocol by which two entangled provers can convince a polynomial-time verifier of the answer to any computable problem whatsoever<\/em> (!!), or indeed that a given Turing machine halts.<\/p>\n\n\n\n

(2) There is a two-prover game, analogous to the Bell\/CHSH game, for which Alice and Bob can do markedly better with a literally infinite<\/em> amount of entanglement than they can with any finite amount of entanglement.<\/p>\n\n\n\n

(3) There is no algorithm even to approximate<\/em> the entangled value of a two-prover game (i.e., the probability that Alice and Bob win the game, if they use the best possible strategy and as much entanglement as they like). Instead, this problem is equivalent to the halting problem.<\/p>\n\n\n\n

(4) There are types of correlations between Alice and Bob that can be produced using infinite entanglement, but that can’t even be approximated using any finite amount of entanglement.<\/p>\n\n\n\n

(5) The Connes embedding conjecture, a central conjecture from the theory of operator algebras dating back to the 1970s, is false.<\/p>\n\n\n\n

Note that all of these implications—including the ones for pure math and the foundations of quantum physics—were obtained using tools that originated in theoretical computer science, specifically the study of interactive proof systems.<\/p>\n\n\n\n

I can remember when the class MIP* was first defined and studied, back around 2003, and people made the point that we didn’t know any reasonable upper bound on the class’s power—not NEXP, not NEEEEXP, not even the set of all computable languages. Back then, the joke was how far our proof techniques<\/em> were from what was self-evidently the truth. I don’t remember a single person who seriously contemplated that two entangled provers could convince a polynomial-time verifier than an arbitrary Turing machine halts.<\/p>\n\n\n\n

Still, ever since Natarajan and Wright’s NEEXP in MIP*<\/a> breakthrough last year, all of us in quantum computing theory knew that MIP*=RE was a live possibility—and all through the summer and fall, I heard many hints that such a breakthrough was imminent.<\/p>\n\n\n\n

It’s worth pointing out that, with only classical correlations between the provers, MIP gives “merely” the power of NEXP (Nondeterministic Exponential Time), while with arbitrary non-signalling correlations between the provers, the so-called MIPns<\/sub> gives the power of EXP (Deterministic Exponential Time). So it’s particularly striking that quantum entanglement, which is “intermediate” between classical correlations and arbitrary non-signalling correlations, yields such wildly greater computational power than either of those two.<\/p>\n\n\n\n

The usual proviso applies: when I’ve blogged excitedly about preprints with amazing new results, most have stood, but at least two ended up being retracted. Still, assuming this one stands (as I’m guessing it will), I regard it as easily<\/em> one of the biggest complexity-theoretic (and indeed computability-theoretic!) surprises so far in this century. Huge congratulations to the authors on what looks to be a historic achievement.<\/p>\n\n\n\n

In unrelated news, for anyone for whom the 165-page MIP* paper is too heavy going (really??), please enjoy this CNBC video on quantum computing<\/a>, which features several clips of yours truly speaking in front of a fake UT tower.<\/p>\n\n\n\n

In other unrelated news, I’m also excited about this preprint<\/a> by Avishay Tal, which sets a new record for the largest known separation between quantum query complexity and classical randomized query complexity, making substantial progress toward proving a conjecture by me and Andris Ambainis from 2015. (Not the<\/em> “Aaronson-Ambainis Conjecture,” a different conjecture.)<\/p>\n","protected":false},"excerpt":{"rendered":"

Another Update (Jan. 16): Yet another reason to be excited about this result—one that somehow hadn’t occurred to me—is that, as far as I know, it’s the first-ever fully convincing example of a non-relativizing computability result. See this comment for more. Update: If you’re interested in the above topic, then you should probably stop reading […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"_wpas_customize_per_network":false},"categories":[5,4],"tags":[],"class_list":["post-4512","post","type-post","status-publish","format-standard","hentry","category-complexity","category-quantum"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/4512","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=4512"}],"version-history":[{"count":5,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/4512\/revisions"}],"predecessor-version":[{"id":4535,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/4512\/revisions\/4535"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=4512"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=4512"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=4512"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}