Succinct arguments for QMA from standard assumptions, without quantum PCPs

Channel:

Simons Institute for the Theory of Computing

Subscribers:

68,600

Published on June 18, 2025 6:12:00 PM ● Video Link: https://www.youtube.com/watch?v=u2FUOYTD_6E

Duration: 0:00

174 views

2

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)