Revolutionary Quantum Gap Amplification: A New Streaming Quantum PCP Approach 🚀

Yantian (Tina) Zhang (MIT)
https://simons.berkeley.edu/talks/yantian-tina-zhang-mit-2025-05-30
Quantum Algorithms, Complexity, and Fault Tolerance Reunion

The quantum PCP conjecture asks whether it is QMA-hard to distinguish between high- and low-energy Hamiltonians even when the gap between 'high' and 'low' energy is large (constant). A natural proof strategy is gap amplification: start from the fact that high- and low-energy Hamiltonians are hard to distinguish if the gap is small (inverse polynomial) [KSV02] and amplify the Hamiltonians to increase the energy gap while preserving hardness. Such a gap amplification procedure is at the heart of Dinur's proof of the classical PCP theorem [Din07]. In this work, following Dinur's model, we introduce a new quantum gap amplification procedure for Hamiltonians which uses random walks on expander graphs to derandomise (subsample the terms of) the tensor product amplification of a Hamiltonian. Curiously, our analysis relies on a new technique inspired by quantum de Finetti theorems, which have previously been used to rule out certain approaches to the quantum PCP conjecture [BH13]. Iterating our amplification procedure yields a streaming quantum PCP theorem, i.e., a quantum-PCP like statement for Hamiltonians with terms that are not necessarily local, but are very simple and can be measured in blocks of five qubits at a time.