The Role of Proofs in MIP* = RE | Quantum Colloquium

Henry Yuen (Columbia University)
Quantum Colloquium, May. 4th, 2021

MIP* = RE has the startling consequence that, in the entangled provers model, there is an interactive proof for the Halting problem. In other words, for all Turing machines M that halt, two separated but quantum entangled provers can convince a classical verifier that M eventually terminates --- and furthermore the complexity of the verifier does not depend on the running time of M!

What does it mean to have an interactive proof for an undecidable problem, and how does quantum entanglement enable this mind-boggling leap in complexity for multiprover interactive proofs? In this talk, I will try to shed light on these questions by highlighting the central role of proofs in MIP* = RE: at its core, the MIP* protocol for the Halting problem recursively combines proofs of both classical and quantum properties. Time permitting, I will also discuss how the techniques in MIP* = RE point to a broader set of questions about "noncommutative property testing."

Based on joint work with Zhengfeng Ji, Anand Natarajan, Thomas Vidick, and John Wright.

[AkashMishra]

Insightful, We're doing the impossible everyday

[DelandaBaudLacanian]

so computer science geeks proved something that is going to take math and physics geeks time to digest? this is incredible, thank you Dr. Yuen for explaining something is probablyl going to take me at least 20 years to even begin to understand lol