CaltechAUTHORS
  A Caltech Library Service

A polynomial time algorithm for the ground state of one-dimensional gapped local Hamiltonians

Landau, Zeph and Vazirani, Umesh and Vidick, Thomas (2015) A polynomial time algorithm for the ground state of one-dimensional gapped local Hamiltonians. Nature Physics, 11 (7). pp. 566-569. ISSN 1745-2473. doi:10.1038/nphys3345. https://resolver.caltech.edu/CaltechAUTHORS:20150422-093309397

[img] PDF - Submitted Version
See Usage Policy.

171kB
[img] PDF - Supplemental Material
See Usage Policy.

312kB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20150422-093309397

Abstract

The density matrix renormalization group method has been extensively used to study the ground state of 1D many-body systems since its introduction two decades ago. In spite of its wide use, this heuristic method is known to fail in certain cases and no certifiably correct implementation is known, leaving researchers faced with an ever-growing toolbox of heuristics, none of which is guaranteed to succeed. Here we develop a polynomial time algorithm that provably finds the ground state of any 1D quantum system described by a gapped local Hamiltonian with constant ground-state energy. The algorithm is based on a framework that combines recently discovered structural features of gapped 1D systems with an efficient construction of a class of operators called approximate ground-state projections (AGSPs). The combination of these tools yields a method that is guaranteed to succeed in all 1D gapped systems. An AGSP-centric approach may help guide the search for algorithms for more general quantum systems, including for the central challenge of 2D systems, where even heuristic methods have had more limited success.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.1038/nphys3345 DOIArticle
https://rdcu.be/brYOsPublisherFree ReadCube access
https://arxiv.org/abs/1307.5143arXivDiscussion Paper
ORCID:
AuthorORCID
Vidick, Thomas0000-0002-6405-365X
Alternate Title:A polynomial time algorithm for the ground state of 1D gapped local Hamiltonians
Additional Information:© 2015 Macmillan Publishers Limited. Received 28 October 2014; Accepted 23 April 2015; Published online 01 June 2015. The first two authors acknowledge support by ARO Grant W911NF-12-1-0541, NSF Grant CCF-0905626 and Templeton Foundation Grant 21674. The third author was 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. Author contributions: All authors contributed equally to this work. The authors declare no competing financial interests.
Group:Institute for Quantum Information and Matter
Funders:
Funding AgencyGrant Number
Army Research Office (ARO)W911NF-12-1-0541
NSFCCF-0905626
John Templeton Foundation21674
NSFCCF-0844626
Ministry of Education (Singapore)MOE2012-T3-1-009
Issue or Number:7
DOI:10.1038/nphys3345
Record Number:CaltechAUTHORS:20150422-093309397
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20150422-093309397
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:56857
Collection:CaltechAUTHORS
Deposited By: Joy Painter
Deposited On:12 May 2015 18:54
Last Modified:10 Nov 2021 21:04

Repository Staff Only: item control page