Earlier this month (Jan 2020) a pre-print was posted to the arXiv claiming to have proved the equivalence of the complexity classes $\mathrm{MIP}^{*}$ and $\mathrm{RE}$ (see below for definitions). The paper has not yet passed peer-review at the time of this question, but there seems to be reasonable confidence that the result is correct (see e.g. Scott Aaronson's blog post about it), so for the rest of this post I will assume this is the case.

It turns out that this result is equivalent to a negative answer to Tsirelson's problem from quantum information. As I understand it, this is a question about the equivalence of two ways of defining entanglement, one in the Hilbert space formalism of quantum mechanics, the other in the operator algebraic formalism (so we don't necessarily have a natural tensor product structure). Naturally these approaches are equivalent for finite-dimensional systems, but $\mathrm{MIP}^{*} = \mathrm{RE}$ implies that, surprisingly, for infinite-dimensional systems this is not always the case. It also implies a negative answer to the Connes embedding problem from the theory of von Neumann algebras, but I do not know enough to say more than this.


$\mathrm{MIP}^{*}$ : the class of languages that can be decided by a classical verifier interacting with multiple all-powerful quantum provers sharing entanglement.

$\mathrm{RE}$ : the class of recursively enumerable languages.


At a discussion group I attended about this paper, we hit upon the question of whether this has any implications for physics "in practice", or whether the systems for which the Tsirelson bound is inequivalent between the two approaches are somehow "edge cases". Certainly infinite-dimensional systems frequently pop up in physics. Prosaically, a bosonic system has an infinite-dimensional Hilbert space. As a more non-trivial example, in quantum field theory one often approximates a continuum theory with a lattice theory, and then eventually takes the lattice spacing to zero. Does $\mathrm{MIP}^{*} = \mathrm{RE}$ imply that this approach is not always possible? I am not necessarily interested in an answer to that specific question, but more generally whether the counterexamples to the Tsirelson problem in this paper should be considered "physical" (for a suitable definition of "physical").


2 Answers 2


At first sight the consequences for physics would be earth-shattering: they have showed that there exists a Bell inequality for which the commuting Tsirelson bound is strictly larger than the tensor-product Tsirelson bound, so the commuting bound cannot even be approximated by finite-dimensional systems. If we could reach the commuting Tsirelson bound experimentally, this would be proof that Nature is actually infinite-dimensional! This would contradict the widespread idea that infinite-dimensional Hilbert spaces are just very convenient approximations to the actual, finite-dimensional ones, and might even disprove Bekenstein's bound, if the relevant systems have finite size and energy.

The problem is that we have no idea how to realize this experiment, and it is probably even physically impossible.

  1. The first difficulty is finding a Bell inequality with the commuting bound larger than the tensor-product bound. The author's methods are constructive, so this is not a problem in principle, just in practice: following their instructions is not at all easy, the authors didn't manage to do it themselves, and if anybody else did they kept silence about it.
  2. One needs to find also the infinite-dimensional algebra with the appropriate commutation relations that reaches the commuting Tsirelson bound. The paper only proves that one must exist, it doesn't show how to find one.
  3. The real problem, though, is finding a QFT that actually realises this infinite-dimensional algebra. Not a single example is known of a physical QFT that doesn't have a tensor-product separation between space-like separated regions, and it is widely believed that none exists.

The conclusion, as Tsirelson himself believed, is that the "physical" Tsirelson bound should be considered the tensor-product one, not the commuting one.

The consequence for physics is much more prosaic: it implies that the Tsirelson bound is undecidable, so we will never get an algorithm to approximate it. Even worse: we do have an infinite sequence of algorithms, the NPA hierarchy, that converges to the commuting Tsirelson from above. The hierarchy itself is not an algorithm, but it works very well in practice for physically interesting cases. This result implies that it doesn't converge to the tensor-product Tsirelson bound, though, so we are left without any reasonable method for calculating it (in principle we can construct a sequence of approximations from below by considering quantum systems of higher and higher dimension, but this is horrifying).


Informally, Connes's conjecture was that all forms of entanglement that can be produced by commuting operators, can be approximated by entanglement produced by tensor products. The theorem falsifying the conjecture implies an additional kind of "infinite entanglement" transcending what can be done with any amount of entangled qubits. (From a quantum-computational perspective, this infinite entanglement is the quantum resource which allows the entangled provers to prove, in polynomial time, a solution to a decision problem of arbitrarily high classical time complexity.)

In his answer, Mateus Araújo mentions that this seems to imply a highly non-standard entanglement structure, in which entanglement between spacelike-separated regions can't be expressed in terms of tensor products. Ordinary quantum field theories aren't like this, but it increasingly looks like holographic theories of quantum gravity might have the required non-standard structure. The Type II1 operator algebra that is the subject of Connes's conjecture has recently turned up in de Sitter space, and the holographic structure of entanglement has been proposed as the essence of how to resolve the black hole information paradox.

The provers in a MIP* scenario cannot communicate, but they share entanglement. This is reminiscent of certain scenarios recently explored by Susskind and others, in which two observers jump into opposite ends of a non-traversable wormhole. They cannot pass through the wormhole, but they can briefly meet in the middle. The similarity is that, according to the ER=EPR hypothesis, a non-traversable wormhole is equivalent to two entangled black holes.

So one might speculate that there is a kind of "computational censorship hypothesis" waiting to be formulated: e.g. that you can do any task in RE in polynomial time, but at the price of never being able to share the result. (Current theory does allow the description of traversable wormholes as well, but the time required to pass through them is longer than the time one would spend traveling from one entrance to the other, via ordinary space. This theorem might be a hint as to exactly how much longer the internal travel time must be.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.