A polynomial-time algorithm for the ground state of 1D gapped local Hamiltonians
arXiv:1307.5143
Abstract
Computing ground states of local Hamiltonians is a fundamental problem in condensed matter physics. We give the first randomized polynomial-time algorithm for finding ground states of gapped one-dimensional Hamiltonians: it outputs an (inverse-polynomial) approximation, expressed as a matrix product state (MPS) of polynomial bond dimension. The algorithm combines many ingredients, including recently discovered structural features of gapped 1D systems, convex programming, insights from classical algorithms for 1D satisfiability, and new techniques for manipulating and bounding the complexity of MPS. Our result provides one of the first major classes of Hamiltonians for which computing ground states is provably tractable despite the exponential nature of the objects involved.
arXiv comment17 pages
References in corpus (11)
- Efficient classical simulation of slightly entangled quantum computations
- An Area Law for One Dimensional Quantum Systems
- Criticality, the area law, and the computational power of PEPS
- Entanglement spectrum and boundary theories with projected entangled-pair states
- The power of quantum systems on a line
- Stochastic Error Cancellation in Analog Quantum Simulation
- An improved 1D area law for frustration-free systems
- The computational difficulty of finding MPS ground states
- Computational Difficulty of Global Variations in the Density Matrix Renormalization Group
- Matrix Product State and mean field solutions for one-dimensional systems can be found efficiently
- An Efficient Algorithm for approximating 1D Ground States
Cited by in corpus (13)
- Hand-waving and Interpretive Dance: An Introductory Course on Tensor Networks
- Undecidability of the Spectral Gap (short version)
- Quantum Information Meets Quantum Matter -- From Quantum Entanglement to Topological Phase in Many-Body Systems
- Spectral gaps of frustration-free spin systems with boundary
- Correlation length in random MPS and PEPS
- A class of two-dimensional AKLT models with a gap
- Computing the Degenerate Ground Space of Gapped Spin Chains in Polynomial Time
- Computing energy density in one dimension
- A polynomial-time algorithm for the ground state of one-dimensional gapped Hamiltonians
- Gaplessness is not generic for translation-invariant spin chains
- Finite-size criteria for spectral gaps in -dimensional quantum spin systems
- Tensor network states for the description of quantum many-body systems
- Markov chains for tensor network states