MIP* = RE is not a typo. It is a groundbreaking discovery and the catchy title of a recent paper in the field of quantum complexity theory.
Complexity theory is a zoo of “complexity classes” of which MIP*and RE are but two. Complexity classes are collections of computational problems.
RE stands for problems that can be solved by a computer. It is the zoo. Let’s have a look at some subclasses.
The class P consists of problems which a known algorithm can solve quickly (technically, in polynomial time). For instance, multiplying two numbers belongs to P since long multiplication is an efficient algorithm to solve the problem. The problem of finding the prime factors of a number is not known to be in P. The problem can certainly be solved by a computer but no known algorithm can do so efficiently.
Another complexity class is NP.
P is contained in NP. Surprisingly, a million dollar question is whether P=NP. Nobody knows.
In complexity theory, the interrogator is the person, with limited computational power, trying to solve the problem. The prover is a new (quantum) computer, which is assumed to have immense computational power. An interactive proof system is a protocol that the interrogator can use in order to determine, at least with high probability, whether the prover should be believed. This is the class IP.
If multiple provers can be interrogated, and the provers are not allowed to coordinate their answers, then we get to the class MIP. Such interrogations, via cross examining the provers’ responses, provide the interrogator with greater power, so MIP contains IP.
Allowing the provers of MIP to share an entangled qubit leads to the class MIP*.
It seems obvious that communication between the provers can only serve to help the provers coordinate lies rather than assist the interrogator in discovering truth. For that reason, nobody expected that allowing more communication would make computational problems more reliable and solvable. Surprisingly, we now know that MIP* = RE. This means that quantum communication behaves wildly differently to normal communication. (Phys.org)
The paper can be read there.
