Connes' Embedding Problem (CEP) is a long-standing question in the field of operator algebras, and is known to be equivalent to a number of other conjectures across mathematics. Remarkably, CEP is also connected to fundamental questions in quantum information theory: in particular, a positive resolution to CEP implies the existence of an algorithm to approximately compute the so-called "entangled value" (i.e. optimal winning probability) of nonlocal games.

We rule out the possibility of such an algorithm, thus providing a negative answer to CEP. In this talk, I will first explain the connection between Connes' Embedding Problem, quantum information theory, and computational complexity. I will then give an overview of our approach, which involves reducing the Halting Problem to the problem of approximating the entangled value of nonlocal games.

Joint work with Zhengfeng Ji, Anand Natarajan, Thomas Vidick, and John Wright.