A Caltech Library Service

Rigorous Rg Algorithms and Area Laws for Low Energy Eigenstates In 1D

Arad, Itai and Landau, Zeph and Vazirani, Umesh V. and Vidick, Thomas (2017) Rigorous Rg Algorithms and Area Laws for Low Energy Eigenstates In 1D. In: 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics. Schloss Dagstuhl – Leibniz-Zentrum für Informatik , Wadern, Germany, Art. No. 46.

[img] PDF - Published Version
Creative Commons Attribution.


Use this Persistent URL to link to this item:


One of the central challenges in the study of quantum many-body systems is the complexity of simulating them on a classical computer. A recent advance by Landau et al. gave a polynomial time algorithm to compute a succinct classical description for unique ground states of gapped 1D quantum systems. Despite this progress many questions remained unresolved, including whether there exist rigorous efficient algorithms when the ground space is degenerate (and poly(n) dimensional), or for the poly(n) lowest energy states for 1D systems, or even whether such states admit succinct classical descriptions or area laws. In this paper we give a new algorithm for finding low energy states for 1D systems, based on a rigorously justified renormalization group (RG)-type transformation. In the process we resolve some of the aforementioned open questions, including giving a polynomial time algorithm for poly(n) degenerate ground spaces and an n^(O(log n)) algorithm for the poly(n) lowest energy states for 1D systems (under a mild density condition). We note that for these classes of systems the existence of a succinct classical description and area laws were not rigorously proved before this work. The algorithms are natural and efficient, and for the case of finding unique ground states for frustration-free Hamiltonians the running time is O(nM(n)), where M(n) is the time required to multiply two n by n matrices.

Item Type:Book Section
Related URLs:
URLURL TypeDescription ItemJournal Article
Vidick, Thomas0000-0002-6405-365X
Additional Information:© 2017 Itai Arad, Zeph Landau, Umesh Vazirani, and Thomas Vidick; licensed under Creative Commons License CC-BY. Date of publication: 28.11.2017. I. Arad’s research was partially performed at the Centre for Quantum Technologies, funded by the Singapore Ministry of Education and the National Research Foundation, also through the Tier 3 Grant random numbers from quantum processes. The authors (Landau and Vazirani) acknowledges support by ARO Grant W911NF-12-1-0541, NSF Grant CCF-1410022 and Templeton Foundation Grant 52536. T. Vidick was partially supported by the IQIM, an NSF Physics Frontiers Center (NFS Grant PHY-1125565) with support of the Gordon and Betty Moore Foundation (GBMF-12500028). We thank Andras Molnar for comments on an earlier draft of this paper, and Christopher T. Chubb for comments and the permission to include the suggestive pictures representing the tensor network structure of the isometry produced by our algorithms.
Group:Institute for Quantum Information and Matter
Funding AgencyGrant Number
Ministry of Education (Singapore)UNSPECIFIED
National Research Foundation (Singapore)UNSPECIFIED
Army Research Office (ARO)W911NF-12-1-0541
John Templeton Foundation52536
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
Gordon and Betty Moore FoundationGBMF-12500028
Subject Keywords:Hamiltonian complexity, area law, gapped ground states, algorithm
Series Name:Leibniz International Proceedings in Informatics
Classification Code:1998 ACM Subject Classification: F.2.1 Numerical Algorithms and Problems, J.2 Physical Sciences and Engineering
Record Number:CaltechAUTHORS:20200804-100730896
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:104722
Deposited By: Tony Diaz
Deposited On:04 Aug 2020 19:02
Last Modified:16 Nov 2021 18:34

Repository Staff Only: item control page