NLTS Hamiltonians (and Strongly-Explicit SoS Lower Bounds) from Low-Rate Quantum LDPC Codes
summary
Proves two concrete improvements: NLTS Hamiltonians arise from linear-distance qLDPC codes even when dimension is arbitrarily small, down to one logical qubit, so NLTS from tiny-rate qLDPC; and gives a constructive planting method that puts a strongly explicit nontrivial codeword (explicit all-X/all-Z logicals) into linear-distance qLDPC codes, removing the Hopkins–Lin Gaussian elimination step and yielding strongly explicit SoS lower bounds for Max-3-LIN style instances. The planted qLDPCs are LDPC, linear distance, and provably positive dimension.
AI-written summary · about
chapters (9)
- 0:00NLTS Hamiltonians overview
- 1:17Quantum LDPC codes background
- 6:18Motivation for NLTS
- 12:10NLTS Hamiltonians definition
- 22:09NLTS properties from QLDPC
- 26:18Clustering property role
- 34:59Relaxing dimension requirement
- 38:30Planted quantum Tanner codes
- 41:01Fault tolerance and SoS bounds
related talks
01h 07mIntroduction to qLDPC Codes
50mMaking the Leap to Quantum PCPs
45mOn the NLTS Conjecture
01h 03mQuantum LDPC Codes with Transversal CCZ Gates
49mCircuit lower bounds for low-energy states of quantum code Hamiltonians
34mExplicit Abelian Lifts and Quantum LDPC Codes
32mTowards local testability for quantum coding
50mDecoding Quantum Low Density Parity Check Codes