Is Connes' Embedding Problem akin the word problem for finitely presented groups?

Question

The complexity class $\mathrm{MIP^*}$ includes the set of languages that can be efficiently verified by a classical, polynomially-bounded verifier, engaging with two quantum provers that can share (potentially infinite) entanglement, but are otherwise forbidden to signal to each other. The complexity class $\mathrm{RE}$ includes recursively enumerable problems, the Halting Problem being a complete problem therein.

A recent breakthrough of Ji, Natarajan, Vidick, Wright, and Yuen in quantum complexity theory is $\mathrm{MIP^*=RE}$. This is, in a way, a quantum analog of the classical result that $\mathrm{MIP=NEXP}$, but shows that shared quantum entanglement in a potentially infinite-dimensional Hilbert space is much much more powerful than that allowed in the (unentangled) classical setting.

Rolling back the implications of Tsirelson and others, this implies a negative answer to Connes' Embedding Problem, which is a major problem in algebra theory.

I can get my head around the complexity class $\mathrm{MIP^*}$ and that of $\mathrm{RE}$. Thanks to Yuen's lecture at the IAS, I vaguely understand Tsirelson's problem in relation to CHSH games, etc., and how it could relate to $\mathrm{MIP^*}$. Also I was able to follow a lot of Slofstra's lecture, where he mentions that Tsirelson's problem is related to finding magic squares in $\mathbb{Z}_2$, and emphasizes the relation to solving a specific word problem for finitely presented groups. Famously such word problems can be algorithmically unsolvable.

However, I know very little of even the statement of Connes' embedding problem, and I don't know how to analogize the problem to something that I'm familiar with.

According to Wikipedia, "Connes' Embedding Problem asks whether every type II1 factor on a separable Hilbert space can be embedded into some $R^\omega$."

Is the CEP itself akin to an algorithmic problem as in the word problem for a finitely generated groups? Or is it much more subtle than that?

Basically I'm looking for a statement of Connes' embedding problem that is a bit more accessible than the Wikipedia article?

Answer 1

There are a number of equivalent formulations to CEP. One of them is Tsirelson's problem from quantum information theory, which asks whether the infinite dimensional commuting operator correlations can be approximated arbitrarily well by finite dimensional quantum correlations. This was shown in a combination of papers by Junge, et al (https://arxiv.org/pdf/1008.1142.pdf), Fritz (https://arxiv.org/pdf/1008.1168.pdf), and Ozawa (https://arxiv.org/pdf/1211.2712.pdf).

However, this equivalence takes a lot of work; in particular, it requires going through Kirchberg's QWEP problem, which is an equivalent problem to CEP but in the language of C* algebras.

If you're looking for a computability-theoretic formulation of Connes' Embedding Conjecture, then there is one due to Goldbring and Hart (https://arxiv.org/pdf/1308.2638.pdf), which says that if CEP has a positive answer, then the "universal theory of type II von Neumann algebras" is decidable. This essentially means that one can write a computer algorithm to decide whether logical sentences about type II von Neumann algebras are true (within a suitably defined logic system). I'm not sure if this can be phrased as an algorithmic word problem.

Here's yet another formulation of CEP that I like, which I find rather concrete:

The Connes Embedding Conjecture posits that for every tracial von Neumann algebra $(M,\tau)$, for every finite subset $\{x_1,\ldots,x_n\}$ of self-adjoint elements from $M$, one can approximate them using finite-dimensional matrices in the following way: for every $\epsilon > 0$ and every integer $N \geq 1$, there exists a dimension $d$ and $d \times d$ matrices $A_1,\ldots,A_n$ such that for every word $i \in \{1,\ldots,n\}^N$, we have the following approximation: $$ \Big | \tau(x_{i_1} x_{i_2} \cdots x_{i_N}) - \frac{1}{d} \mathrm{tr}(A_{i_1} \cdots A_{i_N})\Big|\leq \epsilon. $$

If you don't know what a von Neumann algebra is, don't worry -- me neither. But the point is that CEC is positing that these complicated infinite dimensional objects can always be modelled by finite dimensional matrices (so long as we're looking at finite subsets of the von Neumann algebra).

Hope this helps.