Improved Product-state Approximation Algorithms for Quantum Local Hamiltonians -Bergamaschi|TQC 2023
Channel: Squid: Schools for Quantum Information Development
Date: 2023-08-24

Thiago Bergamaschi
Improved Product-state Approximation Algorithms for Quantum Local Hamiltonians 

https://arxiv.org/abs/2210.08680  
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 \textit{weak Szemer'edi regularity} lemmas for $k$-local Hamiltonians, built on those of Frieze and Kannan and others. We use them to develop \textit{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.

July 28, 2023
---------

TQC 2023 | 24-28 July 2023, University of Aveiro, Portugal
http://tqc-conference.org

18th Conference on the  Theory of Quantum Computation, Communication and Cryptography.

TQC is a leading annual international conference for students and researchers working in the theoretical aspects of quantum information science. The scientific objective is to bring together the theoretical quantum information science community to present and discuss the latest advances in the field.


Organisation:
Squids - Schools for Quantum Information Development  
Universidade de Aveiro: Departamento de Matemática, CIDMA & Fábrica


Sponsors:
Phasecraft, UK
Google Quantum AI, USA
QuSoft, The Netherlands
Quantum for Life Centre, Denmark
Technology Innovation Institute, UAE
ML4Q, Germany
Dulwich Quantum