A Caltech Library Service

An efficient algorithm for finding the ground state of 1D gapped local hamiltonians

Landau, Zeph and Vazirani, Umesh and Vidick, Thomas (2014) An efficient algorithm for finding the ground state of 1D gapped local hamiltonians. In: Proceedings of the 5th conference on Innovations in theoretical computer science. Association for Computing Machinery , New York, p. 301. ISBN 978-1-4503-2698-8.

PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Computing ground states of local Hamiltonians is a fundamental problem in condensed matter physics. The problem is known to be QMA-complete, even for one-dimensional Hamiltonians. This means that we do not even expect that there is a sub-exponential size description of the ground state that allows efficient computation of local observables such as the energy. In sharp contrast, the heuristic density matrix renormalization group (DMRG) algorithm invented two decades ago has been remarkably successful in practice on one-dimensional problems. The situation is reminiscent of the unexplained success of the simplex algorithm before the advent of ellipsoid and interior-point methods. Is there a principled explanation for this, in the form of a large class of one-dimensional Hamiltonians whose ground states can be provably efficiently approximated? Here we give such an algorithm for gapped one-dimensional Hamiltonians: our algorithm outputs an (inverse-polynomial) approximation to the ground state, expressed as a matrix product state (MPS) of polynomial bond dimension. The running time of the algorithm is polynomial in the number of qudits n and the approximation quality δ, for a fixed local dimension d and gap Δ > 0. A key ingredient of our algorithm is a new construction of an operator called an approximate ground state projector (AGSP), a concept first introduced in to derive an improved area law for gapped one-dimensional systems. For this purpose the AGSP has to be efficiently constructed; the particular AGSP we construct relies on matrix-valued Chernoff bounds. Other ingredients of the algorithm include the use of convex programming, recently discovered structural features of gapped 1D quantum systems, and new techniques for manipulating and bounding the complexity of matrix product states.

Item Type:Book Section
Related URLs:
URLURL TypeDescription DOIArticle Paper
Vidick, Thomas0000-0002-6405-365X
Alternate Title:A polynomial-time algorithm for the ground state of 1D gapped local Hamiltonians
Additional Information:© 2014 ACM. Supported by ARO Grant W911NF-12-1-0541, NSF Grant CCF- 0905626 and Templeton Foundation Grant 21674. Part of this work was completed while the author was visiting UC Berkeley. Supported by the National Science Foundation under Grant No. 0844626 and by the Ministry of Education, Singapore under the Tier 3 grant MOE2012-T3-1-009.
Funding AgencyGrant Number
Army Research Office (ARO)W911NF-12-1-0541
Templeton Foundation21674
Ministry of Education (Singapore)MOE2012-T3-1-009
Subject Keywords:Local Hamiltonian; ground state; matrix product state; gapped Hamiltonian; 1d algorithm
Record Number:CaltechAUTHORS:20140909-142344205
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:49502
Deposited By: Tony Diaz
Deposited On:10 Sep 2014 20:16
Last Modified:10 Nov 2021 18:44

Repository Staff Only: item control page