Amazing: Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen proved that MIP* = RE and thus disproved Connes 1976 Embedding Conjecture, and provided a negative answer to Tsirelson’s problem.

A few days ago an historic 160-page paper with a very short title MIP*=RE was uploaded to the arXive by Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen.  I am thankful to Dorit Aharonov and Alon Rosen for telling me about it. The paper simultaneously settles several major open problems in quantum computational complexity, mathematical foundations of quantum physics, and mathematics. Congratulations to Zhengfeng, Anand, Thomas, John, and Henry!

MIP* = RE, by Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen: https://t.co/2Mu8JwmEXj . There is a multiple-entagled-quantum-provers proof system for the Halting Problem, and Connes' Embedding Conjecture is false.

— Ryan O'Donnell (@BooleanAnalysis) January 14, 2020

A tweet by Ryan

The new paper dramatically improved the 2019 result by Anand Natarajan, and John Wright asserting that  “NEEXP in MIP*”.

In this post I will talk a little about two corners of this work and neglect many others:  I will describe a few conjectures about infinite groups related to the new result, and I will give a very gentle beginning-of-an-introduction to interactive proofs.  I will also give some useful links to papers, presentations and blog posts.

Boris Tsirelson is one of my mathematical heroes. The new paper gives a negative answer to an important problem posed by Tsirelson. (Here is a great interview with Boris.)

Resources

My Qstate: a master project (Vidick’s memories of the road since Julia Kempe offered him the problem 14 years ago; with a lot of scientific content). Older related posts on My Qstate  I, II, III.

A Notices AMS article by Vidick: From Operator Algebras to Complexity Theory and Back.

Shtetl Optimized: MIP*=RE;  GLL (Ken Regan) Halting Is Poly-Time Quantum Provable ; Other posts on blogs: WIT (Boaz Barak); CC (Lance Fortnow); WN; Posts on an earlier 2019 result  MIP* contains NEEXP. Updates: A post on GLL on halting, two excellent posts in Hebrew I, II; Post on Quantum Frontiers by Henry Yuen: The shape of MIP* = RE.

Quanta Magazine: An article by Kevin Hartnett about an earlier result MIP*=NEEXP; (March, 2020) An article by Kevin about the new result.

Older posts here:  about Vidick- 2012 paper (among various updates); a 2008 post mentioning sofic groups (among various updates);

Videotaped lectures: from our recent winter school Thomas Vidick on quantum protocols Video 1, Video 2, Video3.

A mathematical context (of one corner of the work) and wish list: stability theory for groups.

(I am thankful to Alex Lubotzky for telling me about the algebra background.)

Links: Finitary approximations of groups and their applications, by Andreas Thom, Andreas’ ICM 2018 videotaped lecture. And a great video: Best of Andreas Thom. See also this paper Stability, cohomology vanishing, and non-approximable groups by Marcus De Chiffre, Lev Glebsky, Alex Lubotzky, and Andreas Thom.

And (thanks Mikael de la Salle!) a recent Book by Gilles Pisier:
Tensor products of C*-algebras and operator spaces; The Connes-Kirchberg problem

The assertion of Connes’ embedding conjecture refuted in the MIP*=RE paper would imply several (outrageous :)) stronger conjectures that are still open. One is the conjecture of Connes that every group is “hyperlinear.” Another famous conjecture (an affirmative answer to a question posed by Gromov) is  that every group is sofic. As sofic groups are hyperlinear we can now expect (ever more than before) that non-sofic and even non hyperlinear groups will be found. Here is a rough short explanation what these conjectures are about. (Kirchberg’s conjecture, is another group theoretic question of this nature.)

Every finite group is a permutation group and is a linear group. This is not the case for infinite groups and there are various interesting notions of “approximately-permutation-group” (this is “sofic”) and “approximately linear” (this is called “hyperlinear”).

Given a group Γ we want to find a sequence of functions

1. From Γ to symmetric groups ,
2. or from Γ to the unitary groups U(n).

Such that asymptotically as n grows these functions are “almost homomorphisms” with respect to certain metrics DIST on or respectively. This means that for every two elements

,

tends to zero when n tends to infinity.

Now,

1. Sofic group refers to the normalized Hamming metric for symmetric groups.
2. Hyperlinear group refers to metrics given by the normalized Hilbert-Schmidt norm on the unitary groups
3. MF-groups, Again the unitary group but the operator norm this time.

And there are various other metrics that were also considered. The assertion of the famous embedding conjecture by Connes on von-Neumann algebras (now refuted by the new result) implies that every group is hyperlinear.

A remaining wish list: Find a non sofic group; find a non-hyperlinear group; refute  Kirchberg’s conjecture (if it was not already refuted).

Interactive proofs and some computational complexity background.

P, NP, IP, MIP

Links: here are slides of  a great talk by Yael Kalai: The evolution of proof in computer science; an a blog post on this topic by Yael Kalai, and a post here about Yael’s 2018 ICM paper and lecture.

A decision problem is in P if there is a polynomial time algorithm (in terms of the input size) to test if the answer is yes or no.  A decision problem is in NP if there is a proof for a YES answer that can be verified in a polynomial time.

Here are two examples: The question if  graph has a perfect matching is in P. The question if  graph has an Hamiltonian cycle  is in NP. If the answer is yes a prover can give a proof that requires the verifier a polynomial number of steps to verify.

IP is a complexity class based on a notion of interactive proof where, based on a protocol for questions and answers,  the prover can convince the verifier (with arbitrary high probability) that the answer is yes. Following a sequence of startling developments Adi Shamir proved that IP is quite a large complexity space P-space.  When we consider several non-interacting provers (two provers suffice) the computational power denoted by MIP is even larger: László Babai, Lance Fortnow, and Cartsen Lund proved that MIP=NEXP!  NEXP is the class of decision problems where if the answer is yes a prover can give a proof that requires the verifier (at most) an exponential number of steps to verify.

Enters quantum computation and entanglement

We replace the model of classical computation with quantum computation. Each of the two provers, Prover1 and Prover2, have access to separate sets of m qubits but they  can prepare in advance a complicated quantum state on those 2m qubits. When we run the verification protocol each prover has access only to its m qubits and, like in the classical case,  the two provers cannot communicate. These types of verification protocols represent the complexity class MIP*.  In 2012 and Tsuyoshi Ito and Thomas Vidick proved that MIP* contains NEXP. In this 2012 post I reported an unusual seminar we ran on the problem.

Interactive quantum lecture: We had an unususal quantum seminar presentation by Michael Ben-Or on the work A multi-prover interactive proof for NEXP sound against entangled provers by Tsuyoshi Ito and Thomas Vidick. Michael ran Vidick’s videotaped recent talk on the matter and from time to time he and Dorit acted as a pair of prover and the other audience as verifier. (Michael was one of the authors of the very first paper introducing multi-prover interactive proofs.)

Let me mention also a related 2014 paper by Yael Kalai, Ran Raz, and Ron Rothblum: How to delegate computations: the power of no-signaling proofs. They considered two provers that are limited by the “non-signaling principle” and showed that the power of interactive proofs is exactly EXP . (Here is a videotaped lecture by Ran Raz.)

In April 2019, Anand Natarajan and John Wright uploaded a paper with a proof that MIP* contain NEEXP. (NEEXP is the class of decision problems where if the answer is yes a prover can give a proof that requires the verifier (at most) doubly exponential number of steps to verify.)

Here is a nice quote from the Harnett’s  quanta paper regarding the Natarajan-Wright breakthrough:

Some problems are too hard to solve in any reasonable amount of time. But their solutions are easy to check. Given that, computer scientists want to know: How complicated can a problem be while still having a solution that can be verified?

Turns out, the answer is: Almost unimaginably complicated.

In a paper released in April, two computer scientists dramatically increased the number of problems that fall into the hard-to-solve-but-easy-to-verify category. They describe a method that makes it possible to check answers to problems of almost incomprehensible complexity. “It seems insane,” said Thomas Vidick, a computer scientist at the California Institute of Technology who wasn’t involved in the new work.

Now with the new result, I wonder if this bold  philosophical interpretation is sensible:  There is a shared quantum state that will allow two non-interacting provers (with unlimited computational power) to convince  a mathematician if a given mathematical statement has a proof, and also to convince a historian or a futurist about any question regarding the past or future evolution of the universe.

What is RE?

(I forgot to explain what RE is. Here is the description from the paper itself.)

RE is the class of recursively enumerable languages, i.e. languages L such that there
exists a Turing machine M such that x ∈ L if and only if M halts and accepts on input x. Note that, in addition to containing all decidable languages, this class also contains undecidable problems such as the Halting problem, which is to decide whether a given Turing machine eventually halts

A little more information and links

The negative answer to Tsirelson problem asserts roughly that there are types of correlations  that can be produced by an infinite quantum systems, but that can’t even be approximated by a finite system. Connes’ 1976 embedding conjecture (now refuted) from the theory of von Neumann algebras asserts that “Every  type von Neumann factor embeds in an ultrapower of a hyperfinite factor.”

The abstract of the new paper mentions a few other works that are important for the new proof.

Anand Natarajan and Thomas Vidick. Low-degree testing for quantum states, and a quantum entangled games PCP for QMA. (FOCS, 2018.)

Anand Natarajan and John Wright. NEEXP ⊆ MIP∗ (FOCS 2019) (We mentioned it above.)

Joe Fitzsimons, Zhengfeng Ji, Thomas Vidick, and Henry Yuen. Quantum proof systems
for iterated exponential time, and beyond.

The abstract also mentions two papers about the connections with Tsirelson problem and Connes embedding conjecture

Tobias Fritz. Tsirelson’s problem and Kirchberg’s conjecture. Reviews in Mathematical
Physics, 24(05):1250012, 2012. (A few enlightening comments by Fritz on SO: I, II)

Marius Junge, Miguel Navascues, Carlos Palazuelos, David Perez-Garcia, Volkher B Scholz, and Reinhard F Werner. Connes’ embedding problem and Tsirelson’s problem. Journal of Mathematical Physics, 52(1):012102, 2011.

Let me also mention

Narutaka Ozawa. About the Connes embedding conjecture. Japanese Journal of Mathematics, 8(1):147–183, 2013.