The importance of the spectral gap in estimating ground-state energies
summary
Shows that adding an inverse-polynomial spectral gap to the precise (inverse-exponential) ground-state energy problem drops complexity from PSPACE-complete to PP-complete, and that also promising a polynomial classical witness changes nothing further. Proof sketches prepare low-temperature thermal (Gibbs) states for a PP upper bound and use a small penalty clock spectral-gap-preserving reduction for hardness. Conjectures that the gap implies polynomial circuit witnesses, explaining VQE success.
AI-written summary · about
chapters (12)
- 0:00Intro
- 0:38Studying ground states
- 2:14Hamiltonian complexity
- 4:25Algorithms
- 5:50Bridging easiness/hardness results
- 7:49Structural property 1: spectral gap • Many interesting Hamiltonians have a spectral gap (difference between smallest eigenvalue and next-smallest eigenvalue)
- 9:25Main result 1 • Provable setting where the spectral gap affects the complexity
- 11:18Structural property 2: classical description of ground state
- 14:43Main result 2
- 15:44An interesting conjecture A candidate explanation for Result 2
- 17:35Proof ideas
- 19:18Outlook
related talks
01h 03mGround Energy estimation of Quantum Impurity model is in BQP
48mThe Quantum Games PCP: Results and Confessions
43mEfficient Quantum Algorithm for Heisenberg Spin Systems
50mClassification of 2D Gapped Ground States With Strict Area Law
01h 06mHow Hamiltonian complexity differs from quantum chemistry
37m(Sub)Exponential Advantage of Adiabatic Quantum Computation With No Sign Problem
01h 08mFast mixing of all-to-all quantum systems at high temperatures
22mQuantum space, ground space traversal, and how to embed multi-prover...