A Caltech Library Service

Rigorous RG algorithms and area laws for low energy eigenstates in 1D

Arad, Itai and Landau, Zeph and Vazirani, Umesh and Vidick, Thomas (2017) Rigorous RG algorithms and area laws for low energy eigenstates in 1D. Communications in Mathematical Physics, 356 (1). pp. 65-105. ISSN 0010-3616. doi:10.1007/s00220-017-2973-z.

[img] PDF - Published Version
Creative Commons Attribution.

[img] PDF - Submitted Version
See Usage Policy.


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 (Landau et al. in Nat Phys, 2015) 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 unsolved, including whether there exist efficient algorithms when the ground space is degenerate (and of polynomial dimension in the system size), or for the polynomially many lowest energy states, or even whether such states admit succinct classical descriptions or area laws. In this paper we give a new algorithm, based on a rigorously justified RG type transformation, for finding low energy states for 1D Hamiltonians acting on a chain of nparticles. 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 (under a mild density condition). 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 Õ(nM(n)), where M(n) is the time required to multiply two n × n matrices.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper ItemBook Chapter
Vidick, Thomas0000-0002-6405-365X
Additional Information:© 2017 The Author(s). This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (, which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made. Received: 4 June 2016; Accepted: 10 June 2017; Published online: 2 August 2017. 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. We thank the anonymous referees for valuable comments that greatly helped improve the presentation of the paper. 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. Z. Landau and U. Vazirani acknowledge 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).
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
Issue or Number:1
Record Number:CaltechAUTHORS:20160321-072746620
Persistent URL:
Official Citation:Arad, I., Landau, Z., Vazirani, U. et al. Commun. Math. Phys. (2017) 356: 65.
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:65500
Deposited By: Ruth Sustaita
Deposited On:31 Mar 2016 00:51
Last Modified:10 Nov 2021 23:46

Repository Staff Only: item control page