Clear Arguments for QMA from Standard Assumptions Without Quantum PCPs 🧩

Anand Natarajan (MIT)
https://simons.berkeley.edu/talks/anand-natarajan-mit-2025-05-30
Quantum Algorithms, Complexity, and Fault Tolerance Reunion

In this talk, I will explain how to construct succinct classical interactive arguments for QMA, using only standard cryptographic assumptions (implied by LWE). Our approach builds on Kalai, Lombardi, Vaikuntanathan’s “compiler” to convert a two-prover interactive proof in the MIP* model into a one-prover interactive argument, and achieves succinctness by combining ideas from the MIP* literature with post-quantum succinct arguments of knowledge. Perhaps unexpectedly, our construction does not yield any form of quantum PCP—neither a “Hamiltonian” PCP nor a “games” PCP—in contrast to the situation in the classical world, where PCPs appear to be inherent to succinct arguments for NP.

Based on joint work with Tony Metger and Tina Zhang (2404.19754)