# Learning k-body Hamiltonians via compressed sensing

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 101 references that are in the map.
- First posted on arXiv 24 Oct 2024.

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

- [Predicting Many Properties of a Quantum System from Very Few Measurements](https://mlsanity.com/paper/2002.08953/) (2020)
- [Quantum advantage in learning from experiments](https://mlsanity.com/paper/2112.00778/) (2021)
- [Exponential separations between learning with and without quantum memory](https://mlsanity.com/paper/2111.05881/) (2021)
- [Sample-efficient learning of quantum many-body systems](https://mlsanity.com/paper/2004.07266/) (2020)
- [Learning many-body Hamiltonians with Heisenberg-limited scaling](https://mlsanity.com/paper/2210.03030/) (2022)
- [Learning Quantum Processes and Hamiltonians via the Pauli Transfer Matrix](https://mlsanity.com/paper/2212.04471/) (2022)
- [Learning quantum Hamiltonians at any temperature in polynomial time](https://mlsanity.com/paper/2310.02243/) (2023)
- [Practical Black Box Hamiltonian Learning](https://mlsanity.com/paper/2206.15464/) (2022)
- [Foundations for learning from noisy quantum experiments](https://mlsanity.com/paper/2204.13691/) (2022)
- [A Fast Hadamard Transform for Signals with Sub-linear Sparsity in the Transform Domain](https://mlsanity.com/paper/1310.1803/) (2013)
- [Structure learning of Hamiltonians from real-time evolution](https://mlsanity.com/paper/2405.00082/) (2024)
- [Time-dependent Hamiltonian simulation with L1-norm scaling](https://mlsanity.com/paper/1906.07115/) (2019)
- [SPRIGHT: A Fast and Robust Framework for Sparse Walsh-Hadamard Transform](https://mlsanity.com/paper/1508.06336/) (2015)
- [Hamiltonian Property Testing](https://mlsanity.com/paper/2403.02968/) (2024)
- [Nearly tight Trotterization of interacting electrons](https://mlsanity.com/paper/2012.09194/) (2020)
- [Provably accurate simulation of gauge theories and bosonic systems](https://mlsanity.com/paper/2110.06942/) (2021)

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

- [Learning the structure of any Hamiltonian from minimal assumptions](https://mlsanity.com/paper/2410.21635/) (2024)
- [Ansatz-free Hamiltonian learning with Heisenberg-limited scaling](https://mlsanity.com/paper/2502.11900/) (2025)
- [Optimal Ansatz-free Hamiltonian Learning In Situ](https://mlsanity.com/paper/2606.19486/) (2026)
- [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)
- [Hamiltonian locality testing and certification do not achieve the Heisenberg limit](https://mlsanity.com/paper/2610.03205/) (2026)
- [Out-of-control Hamiltonian Learning](https://mlsanity.com/paper/2610.06709/) (2026)

## Abstract (arXiv)

We study the problem of learning a k-body Hamiltonian with M unknown Pauli terms that are not necessarily geometrically local. We propose a protocol that learns the Hamiltonian to precision ε with total evolution time O(M1/2+1/p/ε) up to logarithmic factors, where the error is quantified by the ℓp-distance between Pauli coefficients. Our learning protocol uses only single-qubit control operations and a GHZ state initial state, is non-adaptive, is robust against SPAM errors, and performs well even if M and k are not precisely known in advance or if the Hamiltonian is not exactly M-sparse. Methods from the classical theory of compressed sensing are used for efficiently identifying the M terms in the Hamiltonian from among all possible k-body Pauli operators. We also provide a lower bound on the total evolution time needed in this learning task, and we discuss the operational interpretations of the ℓ1 and ℓ2 error metrics. In contrast to most previous works, our learning protocol requires neither geometric locality nor any other relaxed locality conditions.