On the NLTS Conjecture
summary
Posits the NLTS conjecture and proves a first unconditional circuit-depth lower bound for all low-energy states of certain LDPC stabilizer Hamiltonians by constructing many approximate impostors that match small marginals and deriving an entropy contradiction. The quantitative claim gives circuit-depth ≥ min(log N, log 1/ε) for states with energy ≤ εN; applies to hypergraph‑product and punctured toric codes (distance ~√N or N^δ) and uses light‑cone/information‑propagation plus stabilizer local indistinguishability.
AI-written summary · about
chapters (10)
- 0:00Introduction
- 1:50The Problem
- 6:22The NLTS Conjecture
- 11:08Information Propagation
- 14:01Global Entangling
- 16:31Codes
- 25:01Low Energy States
- 34:30Quantum PCP
- 39:07Questions
- 43:44Conclusion
related talks
49mCircuit lower bounds for low-energy states of quantum code Hamiltonians
50mMaking the Leap to Quantum PCPs
44mNLTS Hamiltonians (and Strongly-Explicit SoS Lower Bounds) from Low-Rate Quantum LDPC Codes
01h 03mConstant depth pseudoentanglement - Shallow circuits, deep backstory
22mLower Bounds on Stabilizer Rank
01h 07mIntroduction to qLDPC Codes
42mLearning Shallow Quantum Circuits and Quantum States Prepared by Shallow Circuits in Polynomial Time
48mLayer Codes