Upcoming Events

Logic Colloquium

December 08, 2023, 4:10 PM

60 Evans Hall

John Wright
UC Berkeley

Nonlocal games, MIP* = RE, and the Connes Embedding Problem

A nonlocal game involves two players named Alice and Bob who want to work together to win as often as possible, but they are not allowed to communicate while the game is being played. Nonlocal games were introduced by John Bell in the 1960s in his classic resolution of the EPR paradox, where he showed that Alice and Bob can use quantum particles to “cheat” and outperform any classical strategy, and they have since become an important object of study in the field of quantum mechanics. Parallel to this, in the 1980s, nonlocal games were essentially rediscovered in a completely different context—theoretical computer science—where they play an important role in the study of interactive proof systems. The connection between these two areas was observed in a 2004 work of Cleve, Hoyer, Toner, and Watrous, who introduced a new complexity class named MIP*, corresponding to interactive proofs involving quantum provers. Since then, the study of MIP* has led to a fruitful exchange between the two fields, culminating in the 2020 proof that MIP* = RE by Ji, Natarajan, Vidick, Wright, and Yuen, a corollary of which was the resolution in the negative of both Connes’ embedding problem from operator algebras and Tsirelson’s problem from entanglement theory.

In this talk, I will survey the topics of nonlocal games and interactive proofs, and give a bird’s-eye view of the proof of MIP* = RE. No background in quantum mechanics, theoretical computer science, or operator algebras will be assumed.