# Optimal learning of quantum Hamiltonians from high-temperature Gibbs states

arXiv: https://arxiv.org/abs/2108.04842 · HTML: https://mlsanity.com/paper/2108.04842/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 24 references that are in the map.
- First posted on arXiv 10 Aug 2021.

## Builds on (most cited first, 4 of 4)

- [Efficiently learning Ising models on arbitrary graphs](https://mlsanity.com/paper/1411.6156/) (2014)
- [Interaction Screening: Efficient and Sample-Optimal Learning of Ising Models](https://mlsanity.com/paper/1605.07252/) (2016)
- [Learning Graphical Models Using Multiplicative Weights](https://mlsanity.com/paper/1706.06274/) (2017)
- [Sample-efficient learning of quantum many-body systems](https://mlsanity.com/paper/2004.07266/) (2020)

## Built on by (most cited first, 8 of 8)

- [On the Sample Complexity of Quantum Boltzmann Machine Learning](https://mlsanity.com/paper/2306.14969/) (2023)
- [Foundations for learning from noisy quantum experiments](https://mlsanity.com/paper/2204.13691/) (2022)
- [Structure learning of Hamiltonians from real-time evolution](https://mlsanity.com/paper/2405.00082/) (2024)
- [Stabilizer bootstrapping: A recipe for efficient agnostic tomography and magic estimation](https://mlsanity.com/paper/2408.06967/) (2024)
- [Learning the structure of any Hamiltonian from minimal assumptions](https://mlsanity.com/paper/2410.21635/) (2024)
- [Provably efficient variational generative modeling of quantum many-body systems via quantum-probabilistic information geometry](https://mlsanity.com/paper/2206.04663/) (2022)
- [Learning Energy-Based Representations of Quantum Many-Body States](https://mlsanity.com/paper/2304.04058/) (2023)
- [Machine learning and optimization-based approaches to duality in statistical physics](https://mlsanity.com/paper/2411.04838/) (2024)

## Abstract (arXiv)

We study the problem of learning a Hamiltonian H to precision varepsilon, supposing we are given copies of its Gibbs state ρ=exp(-β H)/operatornameTr(exp(-β H)) at a known inverse temperature β. Anshu, Arunachalam, Kuwahara, and Soleimanifar (Nature Physics, 2021, arXiv:2004.07266) recently studied the sample complexity (number of copies of ρ needed) of this problem for geometrically local N-qubit Hamiltonians. In the high-temperature (low β) regime, their algorithm has sample complexity poly(N, 1/β,1/varepsilon) and can be implemented with polynomial, but suboptimal, time complexity. In this paper, we study the same question for a more general class of Hamiltonians. We show how to learn the coefficients of a Hamiltonian to error varepsilon with sample complexity S = O(log N/(βvarepsilon)2) and time complexity linear in the sample size, O(S N). Furthermore, we prove a matching lower bound showing that our algorithm's sample complexity is optimal, and hence our time complexity is also optimal. In the appendix, we show that virtually the same algorithm can be used to learn H from a real-time evolution unitary e-it H in a small t regime with similar sample and time complexity.