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").


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).

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.