STOC 2021 workshop: MIP* = RE

General Information

Organizers: Anand Natarajan and John Wright
Time: Thursday, June 24, 9:00 AM to 12:00 noon, US Eastern time
Location: on Zoom


A multiprover interactive proof (MIP) is a scenario in which a polynomial-time verifier is allowed to interact with two or more noncommunicating provers in order to solve a computational problem. In 2004, Cleve, Høyer, Toner, and Watrous introduced a quantum variant of MIP, known as MIP*, in which the verifier remains classical but the provers are allowed to share the resource of quantum entanglement. Since then, determining the power of MIP* has remained an important open problem in the field of quantum complexity theory. This culminated in the recent proof that MIP* = RE, the class of recursively enumerable languages, which contains the halting problem, showing that MIP* is a class of almost unimaginable power.

The purpose of this workshop is to give a didactic overview of the proof that MIP* = RE. We will assume no prior knowledge of quantum computing, and will introduce any necessary quantum background ourselves. We will begin with a general overview of the area, and then we will introduce two of the key ingredients in the proof: the magic square game and the quantum low degree test. Finally, we will conclude with a talk which shows how to combine these ingredients to prove MIP* = RE.


9:00-9:45 Thomas Vidick Introduction to MIP*
9:45-10:30 John Wright The magic square game
10:30-11:15 Anand Natarajan The quantum low-degree test
11:15-12:00 Henry Yuen MIP* = RE