A polynomial-time algorithm for the ground state of 1D gapped local Hamiltonians

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.

17 pages

References in corpus (4)

• Criticality, the area law, and the computational power of PEPS
• The power of quantum systems on a line
• Stochastic Error Cancellation in Analog Quantum Simulation
• The computational difficulty of finding MPS 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 $D$-dimensional quantum spin systems
• Tensor network states for the description of quantum many-body systems
• Markov chains for tensor network states