Explore a 48-minute lecture on quantum complexity theory, focusing on the quantum PCP conjecture and its relationship to multiprover interactive proof systems. Delve into the current state of knowledge regarding MIP* and QMA, and learn about a correction to the "quantum games PCP conjecture" previously claimed by the speaker and Thomas Vidick. Discover potential implications for "baby versions" of the Hamiltonian quantum PCP conjecture, based on joint work with Chinmay Nirkhe. Gain insights into the challenges and progress in quantum complexity theory, presented by Anand Natarajan from MIT at the Simons Institute.
The Quantum Games PCP - Results and Confessions
Overview
Syllabus
The Quantum Games PCP: Results and Confessions
Taught by
Simons Institute
Related Courses
-
MIP* = RE Part 1 - The Quantum Low-Degree Test
-
Making the Leap to Quantum PCPs - IPAM at UCLA
-
Quantum PCPs: On Adaptivity, Multiple Provers and Reductions to Local Hamiltonians
-
NEXP is Contained in MIP* - Complexity Theory Breakthrough
-
Subgroup Tests and Tailored Non-local Games - Lecture on Interactive Proof Systems
-
Discussion on MIP* = RE
