License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2017.46
URN: urn:nbn:de:0030-drops-81920
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8192/
Go to the corresponding LIPIcs Volume Portal

Arad, Itai ; Landau, Zeph ; Vazirani, Umesh V. ; Vidick, Thomas

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

pdf-format:
LIPIcs-ITCS-2017-46.pdf (0.6 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{arad_et_al:LIPIcs:2017:8192,
  author =	{Itai Arad and Zeph Landau and Umesh V. Vazirani and Thomas Vidick},
  title =	{{Rigorous Rg Algorithms and Area Laws for Low Energy Eigenstates In 1D}},
  booktitle =	{8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  pages =	{46:1--46:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Christos H. Papadimitriou},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8192},
  URN =		{urn:nbn:de:0030-drops-81920},
  doi =		{10.4230/LIPIcs.ITCS.2017.46},
  annote =	{Keywords: Hamiltonian complexity, area law, gapped ground states, algorithm}
}

Keywords: Hamiltonian complexity, area law, gapped ground states, algorithm
Collection: 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Issue Date: 2017
Date of publication: 28.11.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI