Gap Amplification for Local Hamiltonians with Combinatorial Soundness
summary
Gives a concrete template that turns a two-local input Hamiltonian into a two-local output Hamiltonian on local dimension 2^{polylog n} and proves combinatorial soundness amplification: zero-energy inputs stay zero and inputs with energy ≥ ε force any state to violate an ε·polylog n fraction of output terms. Construction uses high-dimensional expanders for fault-tolerant routing, a new quantum MPC with perfect security, an ABN circuit-to-Hamiltonian mapping, and noisy-reversal plus honest postselection to block adversarial postselection; it does not yet yield full promise-gap amplification.
AI-written summary · about
chapters (17)
- 0:00Quantum gap amplification intro
- 2:57Classical gap amplification
- 4:45Quantum obstructions
- 10:42Main result and soundness
- 16:46Key construction ideas
- 18:59Template as distributed computation
- 25:14Classical protocol template
- 34:52Quantum protocol template
- 37:38Protocol design and expanders
- 45:29Quantum multi-party scheme
- 46:13Local Hamiltonian conversion
- 51:20ABN mapping robustness
- 55:56Post-selection errors
- 59:36Construction summary
- 59:56Bypassing Brandão-Harrow
- 1:01:26Quantum PCP implications
- 1:03:37Q&A
related talks
48mThe Quantum Games PCP: Results and Confessions
36mCircuit-To-Hamiltonian From Tensor Networks and Fault Tolerance
48mIntroduction To Commuting Local Hamiltonian Problems
12mShort Proof of a Spectral Chernoff Bound for Local Hamiltonians
50mMaking the Leap to Quantum PCPs
43mStrongly Universal Hamiltonian Simulators
30mHow to fault-tolerantly realize any quantum circuit with local operations
39mExpansion of Higher-Dimensional Cubical Complexes With Application To Good ...