An Efficient Algorithm for approximating 1D Ground States

Abstract

The DMRG method is very effective at finding ground states of 1D quantum systems in practice, but it is a heuristic method, and there is no known proof for when it works. In this paper we describe an efficient classical algorithm which provably finds a good approximation of the ground state of 1D systems under well defined conditions. More precisely, our algorithm finds a Matrix Product State of bond dimension $D$ whose energy approximates the minimal energy such states can achieve. The running time is exponential in D, and so the algorithm can be considered tractable even for D which is logarithmic in the size of the chain. The result also implies trivially that the ground state of any local commuting Hamiltonian in 1D can be approximated efficiently; we improve this to an exact algorithm.

16 pages, 11 figures. Replaced with updated version + link to PRA journal

References in corpus (5)

• An Area Law for One Dimensional Quantum Systems
• The power of quantum systems on a line
• 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

Cited by in corpus (16)

• Efficient quantum state tomography
• Hamiltonian complexity
• Exponential Decay of Correlations Implies Area Law
• Quantum Hamiltonian Complexity
• Tensor product representation of topological ordered phase: necessary symmetry conditions
• Clifford Circuit Optimization with Templates and Symbolic Pauli Gates
• Matrix Product State and mean field solutions for one-dimensional systems can be found efficiently
• A polynomial-time algorithm for the ground state of 1D gapped local Hamiltonians
• Approximation algorithms for QMA-complete problems
• Computing the Degenerate Ground Space of Gapped Spin Chains in Polynomial Time
• Importance of the spectral gap in estimating ground-state energies
• Computing energy density in one dimension
• A polynomial-time algorithm for the ground state of one-dimensional gapped Hamiltonians
• Physical consequences of P$\ne$NP and the DMRG-annealing conjecture
• Approximation, Proof Systems, and Correlations in a Quantum World
• Effects of Topological Boundary Conditions on Bell Nonlocality