# Learning quantum Hamiltonians at any temperature in polynomial time

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 74 references that are in the map.
- First posted on arXiv 3 Oct 2023.

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

- [Predicting Many Properties of a Quantum System from Very Few Measurements](https://mlsanity.com/paper/2002.08953/) (2020)
- [Mixture Models, Robustness, and Sum of Squares Proofs](https://mlsanity.com/paper/1711.07454/) (2017)
- [Efficient Algorithms for Outlier-Robust Regression](https://mlsanity.com/paper/1803.03241/) (2018)
- [Efficiently learning Ising models on arbitrary graphs](https://mlsanity.com/paper/1411.6156/) (2014)
- [Learning Graphical Models Using Multiplicative Weights](https://mlsanity.com/paper/1706.06274/) (2017)
- [List-Decodable Linear Regression](https://mlsanity.com/paper/1905.05679/) (2019)
- [Robust Linear Regression: Optimal Rates in Polynomial Time](https://mlsanity.com/paper/2007.01394/) (2020)
- [List Decodable Learning via Sum of Squares](https://mlsanity.com/paper/1905.04660/) (2019)
- [Settling the Robust Learnability of Mixtures of Gaussians](https://mlsanity.com/paper/2011.03622/) (2020)
- [A survey on the complexity of learning quantum states](https://mlsanity.com/paper/2305.20069/) (2023)
- [Learning many-body Hamiltonians with Heisenberg-limited scaling](https://mlsanity.com/paper/2210.03030/) (2022)
- [Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method](https://mlsanity.com/paper/1407.1543/) (2014)
- [Information Theoretic Properties of Markov Random Fields, and their Algorithmic Applications](https://mlsanity.com/paper/1705.11107/) (2017)
- [Practical Black Box Hamiltonian Learning](https://mlsanity.com/paper/2206.15464/) (2022)
- [SoS Degree Reduction with Applications to Clustering and Robust Moment Estimation](https://mlsanity.com/paper/2101.01509/) (2021)
- [Computational Implications of Reducing Data to Sufficient Statistics](https://mlsanity.com/paper/1409.3821/) (2014)
- [Quantum entanglement, sum of squares, and the log rank conjecture](https://mlsanity.com/paper/1701.06321/) (2017)
- [A CS guide to the quantum singular value transformation](https://mlsanity.com/paper/2302.14324/) (2023)
- [Application of the Level-2 Quantum Lasserre Hierarchy in Quantum Approximation Algorithms](https://mlsanity.com/paper/2105.05698/) (2021)

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

- [A Primer on Quantum Machine Learning](https://mlsanity.com/paper/2511.15969/) (2025)
- [Structure learning of Hamiltonians from real-time evolution](https://mlsanity.com/paper/2405.00082/) (2024)
- [Natural gradient and parameter estimation for quantum Boltzmann machines](https://mlsanity.com/paper/2410.24058/) (2024)
- [Learning k-body Hamiltonians via compressed sensing](https://mlsanity.com/paper/2410.18928/) (2024)
- [Hamiltonian Property Testing](https://mlsanity.com/paper/2403.02968/) (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)
- [Learning finitely correlated states: stability of the spectral reconstruction](https://mlsanity.com/paper/2312.07516/) (2023)
- [Efficient Certificates of Anti-Concentration Beyond Gaussians](https://mlsanity.com/paper/2405.15084/) (2024)
- [Ansatz-free Hamiltonian learning with Heisenberg-limited scaling](https://mlsanity.com/paper/2502.11900/) (2025)
- [Improved algorithms for learning quantum Hamiltonians, via flat polynomials](https://mlsanity.com/paper/2407.04540/) (2024)
- [TCS-BENCH: Benchmarking State-of-the-Art Generative AI Theoretical Computer Science Research Ability](https://mlsanity.com/paper/2608.09538/) (2026)
- [Efficient Hamiltonian, structure and trace distance learning of Gaussian states](https://mlsanity.com/paper/2411.03163/) (2024)
- [Optimal certification of constant-local Hamiltonians](https://mlsanity.com/paper/2512.09778/) (2025)
- [Provable learning separation for predicting time-evolution of quantum many-body systems](https://mlsanity.com/paper/2607.06472/) (2026)
- [Characterizing Arbitrary Lindbladian Dynamics with a Few Pauli Measurements](https://mlsanity.com/paper/2607.23044/) (2026)
- [Learning quantum Hamiltonians at any temperature in polynomial time with Chebyshev and bit complexity](https://mlsanity.com/paper/2402.05552/) (2024)
- [Quantum Maximum Entropy Inference and Hamiltonian Learning](https://mlsanity.com/paper/2407.11473/) (2024)
- [Learning to erase quantum states: thermodynamic implications of quantum learning theory](https://mlsanity.com/paper/2504.07341/) (2025)
- [Efficient Learning of Lattice Gauge Theories with Fermions](https://mlsanity.com/paper/2512.19891/) (2025)
- [Computationally sufficient statistics for Ising models](https://mlsanity.com/paper/2602.12449/) (2026)
- [Quantum score matching with applications to learning thermal states](https://mlsanity.com/paper/2609.28391/) (2026)
- [Hamiltonian locality testing and certification do not achieve the Heisenberg limit](https://mlsanity.com/paper/2610.03205/) (2026)

## Abstract (arXiv)

We study the problem of learning a local quantum Hamiltonian H given copies of its Gibbs state ρ = e-β H/textrmtr(e-β H) at a known inverse temperature β>0. Anshu, Arunachalam, Kuwahara, and Soleimanifar (arXiv:2004.07266) gave an algorithm to learn a Hamiltonian on n qubits to precision ε with only polynomially many copies of the Gibbs state, but which takes exponential time. Obtaining a computationally efficient algorithm has been a major open problem [Alhambra'22 (arXiv:2204.08349)], [Anshu, Arunachalam'22 (arXiv:2204.08349)], with prior work only resolving this in the limited cases of high temperature [Haah, Kothari, Tang'21 (arXiv:2108.04842)] or commuting terms [Anshu, Arunachalam, Kuwahara, Soleimanifar'21]. We fully resolve this problem, giving a polynomial time algorithm for learning H to precision ε from polynomially many copies of the Gibbs state at any constant β > 0. Our main technical contribution is a new flat polynomial approximation to the exponential function, and a translation between multi-variate scalar polynomials and nested commutators. This enables us to formulate Hamiltonian learning as a polynomial system. We then show that solving a low-degree sum-of-squares relaxation of this polynomial system suffices to accurately learn the Hamiltonian.