A Polynomial-time Algorithm for Finding Ground States of Gapped Local Hamiltonians in 1D
summary
Proves a concrete algorithm that outputs a matrix product state approximating the unique gapped 1D ground state to overlap ≥1−δ in time polynomial in n and 1/δ when gap and local dimension are fixed, but with a very bad dependence on the gap (runtime exponent grows exponentially as the gap shrinks). It proceeds left-to-right maintaining polynomial-size viable sets of partial MPS, repeatedly applies an AGSP built from (1−H/n)^m approximated by sampling, and uses matrix Chernoff sampling plus a decoupling pruning step to control bond and set sizes.
AI-written summary · about
chapters (11)
- 0:00Intro
- 14:10Ideas
- 14:45Tools
- 16:42Metaphor
- 19:30Two Procedures
- 23:52Parameters
- 27:06Construction
- 31:16Algorithm
- 35:26iterative step
- 45:01Claim
- 48:46Operator
related talks
01h 15mImproved Machine Learning Algorithm for Predicting Ground State Properties
55mFinding Eigenvalues in Exponential Size Space:...
26mTight Algorithmic Thresholds for Spin Glass Hamiltonians
24mRandom Max-CSPs Inherit Algorithmic Hardness from Spin Glasses
11mUnderstanding Statistical-to-Computational Gaps via Low-Degree Polynomials
49mAnalysis of Algorithms on Dense Matrices using Approximate Message Passing
38mSome Easy Optimization Problems Have the Overlap-Gap Property
31mThe Convergence of Hamiltonian Monte Carlo