Document Open Access Logo

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

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

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2017.46.pdf
  • Filesize: 0.57 MB
  • 14 pages

Document Identifiers

Author Details

Itai Arad
Zeph Landau
Umesh V. Vazirani
Thomas Vidick

Cite As Get BibTex

Itai Arad, Zeph Landau, Umesh V. Vazirani, and Thomas Vidick. 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 (LIPIcs), Volume 67, pp. 46:1-46:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ITCS.2017.46

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.

Subject Classification

Keywords
  • Hamiltonian complexity
  • area law
  • gapped ground states
  • algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Dorit Aharonov, Daniel Gottesman, Sandy Irani, and Julia Kempe. The power of quantum systems on a line. Communications in Mathematical Physics, 287(1):41-65, 2009. URL: http://dx.doi.org/10.1007/s00220-008-0710-3.
  2. Itai Arad, Zeph Landau, Umesh Vazirani, and Thomas Vidick. Rigorous RG algorithms and area laws for low energy eigenstates in 1D. arXiv preprint arXiv:1602.08828, 2016. URL: https://arxiv.org/abs/1602.08828.
  3. Christopher T. Chubb and Steven T. Flammia. Computing the Degenerate Ground Space of Gapped Spin Chains in Polynomial Time. ArXiv e-prints, February 2015. URL: http://arxiv.org/abs/1502.06967.
  4. J. Eisert, M. Cramer, and M. B. Plenio. Colloquium: Area laws for the entanglement entropy. Rev. Mod. Phys., 82(1):277-306, Feb 2010. URL: http://dx.doi.org/10.1103/RevModPhys.82.277.
  5. Matthew B. Hastings. An area law for one-dimensional quantum systems. Journal of Statistical Mechanics: Theory and Experiment, 2007(08):P08024, 2007. URL: http://stacks.iop.org/1742-5468/2007/i=08/a=P08024.
  6. Yichen Huang. A polynomial-time algorithm for the ground state of one-dimensional gapped Hamiltonians. ArXiv e-prints, June 2014. URL: http://arxiv.org/abs/1406.6355.
  7. Yichen Huang. A simple efficient algorithm in frustration-free one-dimensional gapped systems. ArXiv e-prints, October 2015. URL: http://arxiv.org/abs/1510.01303.
  8. Zeph Landau, Umesh Vazirani, and Thomas Vidick. A polynomial time algorithm for the ground state of one-dimensional gapped local hamiltonians. Nature Physics, 2015. URL: http://arxiv.org/abs/1307.5143.
  9. Lluís Masanes. Area law for the entropy of low-energy states. Physical Review A, 80(5):052104, 2009. Google Scholar
  10. Pankaj Mehta and David Schwab. An exact mapping between the variational renormalization group and deep learning. Technical report, arXiv preprint arXiv:1410.3831, 2014. URL: http://arxiv.org/abs/1410.3831.
  11. Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv:1011.3027, 2010. URL: http://arxiv.org/abs/1011.3027.
  12. G. Vidal. Class of quantum many-body states that can be efficiently simulated. Phys. Rev. Lett., 101:110501, Sep 2008. URL: http://dx.doi.org/10.1103/PhysRevLett.101.110501.
  13. Guifre Vidal. Entanglement renormalization: an introduction. arXiv preprint arXiv:0912.1651, 2009. Google Scholar
  14. Steven R. White. Density matrix formulation for quantum renormalization groups. Phys. Rev. Lett., 69:2863-2866, Nov 1992. URL: http://dx.doi.org/10.1103/PhysRevLett.69.2863.
  15. Kenneth G Wilson. The renormalization group: Critical phenomena and the kondo problem. Reviews of Modern Physics, 47(4):773, 1975. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact