License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2023.20
URN: urn:nbn:de:0030-drops-180722
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18072/
Go to the corresponding LIPIcs Volume Portal

Bergamaschi, Thiago

Improved Product-State Approximation Algorithms for Quantum Local Hamiltonians

pdf-format:
LIPIcs-ICALP-2023-20.pdf (0.7 MB)

Abstract

The ground state energy and the free energy of Quantum Local Hamiltonians are fundamental quantities in quantum many-body physics, however, it is QMA-Hard to estimate them in general. In this paper, we develop new techniques to find classical, additive error product-state approximations for these quantities on certain families of Quantum k-Local Hamiltonians. Namely, those which are either dense, have low threshold rank, or are defined on a sparse graph that excludes a fixed minor, building on the methods and the systems studied by Brandão and Harrow, Gharibian and Kempe, and Bansal, Bravyi and Terhal.
We present two main technical contributions. First, we discuss a connection between product-state approximations of local Hamiltonians and combinatorial graph property testing. We develop a series of weak Szemerédi regularity lemmas for k-local Hamiltonians, built on those of Frieze and Kannan and others. We use them to develop constant time sampling algorithms, and to characterize the "vertex sample complexity" of the Local Hamiltonian problem, in an analog to a classical result by Alon, de la Vega, Kannan and Karpinski. Second, we build on the information-theoretic product-state approximation techniques by Brandão and Harrow, extending their results to the free energy and to an asymmetric graph setting. We leverage this structure to define families of algorithms for the free energy at low temperatures, and new algorithms for certain sparse graph families.

BibTeX - Entry

@InProceedings{bergamaschi:LIPIcs.ICALP.2023.20,
  author =	{Bergamaschi, Thiago},
  title =	{{Improved Product-State Approximation Algorithms for Quantum Local Hamiltonians}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{20:1--20:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18072},
  URN =		{urn:nbn:de:0030-drops-180722},
  doi =		{10.4230/LIPIcs.ICALP.2023.20},
  annote =	{Keywords: Approximation Algorithms, Quantum Information}
}

Keywords: Approximation Algorithms, Quantum Information
Collection: 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Issue Date: 2023
Date of publication: 05.07.2023

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