Making the Leap to Quantum PCPs
summary
Claim: there is an explicit stabilizer Hamiltonian built from high-rate high-distance codes whose low-energy states provably need large circuit depth, using hypergraph-product-like constructions and locality-vs-distance arguments. Tools: circuit-to-Hamiltonian mapping, well-spread distributions, Chebyshev-polynomial robustification and small-set expansion heuristics. It succeeds in proving NLTS (robust entanglement at low temperature) but relies on commuting stabilizer terms so it is not NP-hard; open work targets combining NLTS with NP/BQP hardness via hypergraph products of CSPs or nonstabilizer constructions.
AI-written summary · about
chapters (16)
- 0:00Intro
- 0:59Calculating ground-energy is a hard problem
- 2:47How hard is ground-energy approximation?
- 6:23State complexity classes
- 6:57The QPCP conjecture and state complexity
- 14:44The NLTS problem
- 17:36Proof sketch of the NLTS result
- 22:34Robust well-spread lower bounds
- 24:00Finding well-spread distributions
- 27:20Multiple bases to the rescue
- 30:29Proving NLTS via "well-spreadness" and codes
- 33:25Superpositions over NP solutions
- 37:57A surprising connection to quantum money/lightning
- 40:22An intermediate problem for both q. lightning and QPCP
- 42:19Proving stronger lower bounds than NLTS
- 44:55The trouble with quantum codes
related talks
49mCircuit lower bounds for low-energy states of quantum code Hamiltonians
45mOn the NLTS Conjecture
44mNLTS Hamiltonians (and Strongly-Explicit SoS Lower Bounds) from Low-Rate Quantum LDPC Codes
58mLimitations for Quantum PCPs
01h 07mIntroduction to qLDPC Codes
48mIntroduction To Commuting Local Hamiltonian Problems
18mAutomated distribution of quantum circuits via hypergraph partitioning
36mCircuit-To-Hamiltonian From Tensor Networks and Fault Tolerance