https://science.slashdot.org/story/20/01/18/0554240/major-breakthrough-in-qu... Posted by EditorDavid on Saturday January 18, 2020 @03:34PM from the problem-sets dept. Slashdot reader JoshuaZ <https://slashdot.org/~JoshuaZ> writes: /In a major breakthrough in quantum computing it was shown that MIP* equals RE <https://arxiv.org/abs/2001.04383>. MIP* is the set of problems that can be efficiently demonstrated to a classical computer interacting with multiple quantum computers with any amount of shared entanglement between the quantum computers. RE is the set of problems which are recursive; this is essentially all problems which can be computed. This result comes through years of deep development of understanding interactive protocols, where one entity, a verifier, has much less computing power than another set of entities, provers, who wish to convince the verifier of the truth of a claim. In 1990, a major result was that a classical computer with a polynomial amount of time could be convince of any claim in PSPACE <https://en.wikipedia.org/wiki/PSPACE> by interacting with an arbitrarily powerful <https://en.wikipedia.org/wiki/IP_(complexity)> classical computer. Here PSPACE is the set of problems solvable by a classical computer with a polynomial amount of space. Subsequent results showed that if one allowed a verifier able to interact with multiple provers, the verifier could be convinced of a solution of any problem in NEXPTIME, a class conjectured to be much larger than PSPACE. For a while, it was believed that in the quantum case, the set of problems might actually be smaller, since multiple quantum computers might be able to use their shared entangled qubits to "cheat" the verifier. However, this has turned out not just to not be the case, but the exact opposite: MIP* is not only large, it is about as large as a computable class can naturally be. This result while a very big deal from a theoretical standpoint is unlikely to have any immediate applications since it supposes quantum computers with arbitrarily large amounts of computational power and infinite amounts of entanglement. The paper in question is a 165 tour de force which includes incidentally showing that the The Connes embedding conjecture, a 50 year old major conjecture from the theory of operator algebras, is false./ -- Honesty is a very expensive gift. So, don't expect it from cheap people - Warren Buffett http://tayek.com/