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 (2016) Rigorous RG algorithms and area laws for low energy eigenstates in 1D. . (Submitted)

[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 [LVV15] gave a polynomial time algorithm to actually 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 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 x n matrices.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Vidick, Thomas0000-0002-6405-365X
Additional Information:Submitted on 29 Feb 2016. 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. 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, IQIM
Funding AgencyGrant Number
Ministry of Education (Singapore)UNSPECIFIED
National Research Foundation (Singapore)UNSPECIFIED
Army Research Office (ARO)W911NF-12-1-0541
Templeton Foundation52536
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
NSF Physics Frontiers CenterPHY-1125565
Gordon and Betty Moore FoundationGBMF-12500028
Record Number:CaltechAUTHORS:20160321-072746620
Persistent URL:
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:31 Mar 2016 00:51

Repository Staff Only: item control page