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 9781450326988. https://resolver.caltech.edu/CaltechAUTHORS:20140909142344205

PDF
 Submitted Version
See Usage Policy. 171kB 
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20140909142344205
Abstract
Computing ground states of local Hamiltonians is a fundamental problem in condensed matter physics. The problem is known to be QMAcomplete, even for onedimensional Hamiltonians. This means that we do not even expect that there is a subexponential 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 onedimensional problems. The situation is reminiscent of the unexplained success of the simplex algorithm before the advent of ellipsoid and interiorpoint methods. Is there a principled explanation for this, in the form of a large class of onedimensional Hamiltonians whose ground states can be provably efficiently approximated? Here we give such an algorithm for gapped onedimensional Hamiltonians: our algorithm outputs an (inversepolynomial) 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 onedimensional systems. For this purpose the AGSP has to be efficiently constructed; the particular AGSP we construct relies on matrixvalued 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: 
 
ORCID: 
 
Alternate Title:  A polynomialtime algorithm for the ground state of 1D gapped local Hamiltonians  
Additional Information:  © 2014 ACM. Supported by ARO Grant W911NF1210541, 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 MOE2012T31009.  
Funders: 
 
Subject Keywords:  Local Hamiltonian; ground state; matrix product state; gapped Hamiltonian; 1d algorithm  
DOI:  10.1145/2554797.2554825  
Record Number:  CaltechAUTHORS:20140909142344205  
Persistent URL:  https://resolver.caltech.edu/CaltechAUTHORS:20140909142344205  
Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided.  
ID Code:  49502  
Collection:  CaltechAUTHORS  
Deposited By:  Tony Diaz  
Deposited On:  10 Sep 2014 20:16  
Last Modified:  10 Nov 2021 18:44 
Repository Staff Only: item control page