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.