Recent searches
Search options
A major breakthrough in quantum complexity and its applications in von Neumann algebra theory that I totally don't understand: MIP*=RE, or "two entangled provers could convince a polynomial-time verifier than an arbitrary Turing machine halts", https://arxiv.org/abs/2001.04383
Bloggers closer to this area don't have much to say, but I'll point to their posts anyway: https://windowsontheory.org/2020/01/14/mipre-connes-embedding-conjecture-disproved/ https://www.scottaaronson.com/blog/?p=4512
Background from an author: https://mycqstate.wordpress.com/2020/01/14/a-masters-project/
The algebra: https://en.wikipedia.org/wiki/Connes_embedding_problem
arxiv.orgMIP*=REWe show that the class MIP* of languages that can be decided by a classical
verifier interacting with multiple all-powerful quantum provers sharing
entanglement is equal to the class RE of recursively enumerable languages. Our
proof builds upon the quantum low-degree test of (Natarajan and Vidick, FOCS
2018) and the classical low-individual degree test of (Ji, et al., 2020) by
integrating recent developments from (Natarajan and Wright, FOCS 2019) and
combining them with the recursive compression framework of (Fitzsimons et al.,
STOC 2019).
An immediate byproduct of our result is that there is an efficient reduction
from the Halting Problem to the problem of deciding whether a two-player
nonlocal game has entangled value $1$ or at most $1/2$. Using a known
connection, undecidability of the entangled value implies a negative answer to
Tsirelson's problem: we show, by providing an explicit example, that the
closure $C_{qa}$ of the set of quantum tensor product correlations is strictly
included in the set $C_{qc}$ of quantum commuting correlations. Following work
of (Fritz, Rev. Math. Phys. 2012) and (Junge et al., J. Math. Phys. 2011) our
results provide a refutation of Connes' embedding conjecture from the theory of
von Neumann algebras.