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.## Schedule

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.

| Thomas Vidick | Introduction to MIP* |

| John Wright | The magic square game |

| Anand Natarajan | The quantum low-degree test |

| Henry Yuen | MIP* = RE |