The Quantum Games PCP: Results and Confessions
0Anand Natarajan (MIT)
https://simons.berkeley.edu/talks/anand-natarajan-mit-2024-03-20
Quantum Complexity: Quantum PCP; Area Laws; and Quantum Gravity
In classical complexity theory, the PCP theorem arose directly from Babai, Fortnow, and Lund’s seminal result that multiprover interactive proof systems can decide NEXP. In the quantum case, the connection is less clear, but researchers have hoped that insights into the quantum PCP conjecture can arise from the study of succinct MIP* interactive proofs for QMA. In this talk, I will present the current state of knowledge regarding MIP* and QMA, and explain a mistake in the proof of the “quantum games PCP conjecture” claimed by myself and Thomas Vidick in 2018. I will discuss how these ideas may point the way towards interesting “baby versions” of the Hamiltonian quantum PCP conjecture. Based on joint work with Chinmay Nirkhe.