In this work, we study the problems of certifying and learning quantum $k$-local Hamiltonians, for a constant $k$. Our main contributions are as follows:
- Certification of Hamiltonians. We show that certifying a local Hamiltonian in normalized Frobenius norm via access to its time-evolution operator can be achieved with only $O(1/\varepsilon)$ evolution time. This is optimal, as it matches the Heisenberg-scaling lower bound of $Ω(1/\varepsilon)$. To our knowledge, this is the first optimal algorithm for testing a Hamiltonian property. A key ingredient in our analysis is the Bonami Hypercontractivity Lemma from Fourier analysis.
- Learning Gibbs states. We design an algorithm for learning Gibbs states of local Hamiltonians in trace norm that is sample-efficient in all relevant parameters. In contrast, previous approaches learned the underlying Hamiltonian (which implies learning the Gibbs state), and thus inevitably suffered from exponential sample complexity scaling in the inverse temperature.
- Certification of Gibbs states. We give an algorithm for certifying Gibbs states of local Hamiltonians in trace norm that is both sample and time-efficient in all relevant parameters, thereby solving a question posed by Anshu (Harvard Data Science Review, 2022).
Comments
27 pages. This work subsumes prior works (arXiv:2509.10239, arXiv:2512.09778)
In this work, we study the problems of certifying and learning quantum k-local Hamiltonians, for a constant k. Our main contributions are as follows:
Certification of Hamiltonians. We show that certifying a local Hamiltonian in normalized Frobenius norm via access to its time-evolution operator can be achieved with only O(1/ε) evolution time. This is optimal, as it matches the Heisenberg-scaling lower bound of Ω(1/ε). To our knowledge, this is the first optimal algorithm for testing a Hamiltonian property. A key ingredient in our analysis is the Bonami Hypercontractivity Lemma from Fourier analysis.
Learning Gibbs states. We design an algorithm for learning Gibbs states of local Hamiltonians in trace norm that is sample-efficient in all relevant parameters. In contrast, previous approaches learned the underlying Hamiltonian (which implies learning the Gibbs state), and thus inevitably suffered from exponential sample complexity scaling in the inverse temperature.
Certification of Gibbs states. We give an algorithm for certifying Gibbs states of local Hamiltonians in trace norm that is both sample and time-efficient in all relevant parameters, thereby solving a question posed by Anshu (Harvard Data Science Review, 2022).
We study the problem of certifying local Hamiltonians from real-time access to their dynamics. Given oracle access to e−itH for an unknown k-local Hamiltonian H and a fully specified target Hamiltonian H0, the goal is to decide whether H is exactly equal to H0 or differs from H0 by at least ε in normalized Frobenius norm, while minimizing the total evolution time. We introduce the first intolerant Hamiltonian certification protocol that achieves optimal performance for all constant-locality Hamiltonians. For general n-qubit, k-local, traceless Hamiltonians, our procedure uses O(ck/ε) total evolution time for a universal constant c, and succeeds with high probability. In particular, for O(1)-local Hamiltonians, the total evolution time becomes Θ(1/ε), matching the known Ω(1/ε) lower bounds and achieving the gold-standard Heisenberg-limit scaling. Prior certification methods either relied on implementing inverse evolution of H, required controlled access to e−itH, or achieved near-optimal guarantees only in restricted settings such as the Ising case (k=2). In contrast, our algorithm requires neither inverse evolution nor controlled operations: it uses only forward real-time dynamics and achieves optimal intolerant certification for all constant-locality Hamiltonians.
In this work, we study the problems of certifying and learning quantum Ising Hamiltonians. Our main contributions are as follows: Certification of Ising Hamiltonians. We show that certifying an Ising Hamiltonian in normalized Frobenius norm via access to its time-evolution operator requires only O(1/ε) time evolution. This matches the Heisenberg-scaling lower bound of Ω(1/ε) up to logarithmic factors. To our knowledge, this is the first nearly-optimal algorithm for testing a Hamiltonian property. A key ingredient in our analysis is the Bonami Lemma from Fourier analysis. Learning Ising Gibbs states. We design an algorithm for learning Ising Gibbs states in trace norm that is sample-efficient in all parameters. In contrast, previous approaches learned the underlying Hamiltonian (which implies learning the Gibbs state) but suffered from exponential sample complexity in the inverse temperature. Certification of Ising Gibbs states. We give an algorithm for certifying Ising Gibbs states in trace norm that is both sample and time-efficient, thereby solving a question posed by Anshu (Harvard Data Science Review, 2022). Finally, we extend our results on learning and certification of Gibbs states to general k-local Hamiltonians for any constant k.
We establish lower bounds for Hamiltonian property testing with access to the time-evolution operator but not its inverse. Each experiment may query the time-evolution operator multiple times, and distances between Hamiltonians are measured in the normalized Frobenius norm.
In this model, we show that testing whether a Hamiltonian is k-local or ε-far from every k-local Hamiltonian requires Ω(1/ε2) total evolution time, matching the upper bound of Kallaugher and Liang (TQC'25). We also prove that testing whether an unknown Hamiltonian equals a target Hamiltonian or is ε-far from it requires Ω(1/ε2) total evolution time, matching the upper bound of Sinha and Tong (2025). These are the first lower bounds for natural problems in Hamiltonian learning and testing that rule out Heisenberg-limited scaling of 1/ε.
As a third result, we show that amplitude estimation to precision ε requires Ω(1/ε2) total time evolution, recovering the result of Tang and Wright (QIP'26) in the continuous-time query model. All three results follow from the hardness of distinguishing the zero Hamiltonian from a suitably chosen ensemble of random Hamiltonians. We establish this hardness by adapting the continuous-time adversary method to forward Hamiltonian evolution.
We study the problem of learning a Hamiltonian H to precision ε, supposing we are given copies of its Gibbs state ρ=exp(−βH)/Tr(exp(−βH)) at a known inverse temperature β. Anshu, Arunachalam, Kuwahara, and Soleimanifar [AAKS21] 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/ε) 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 ε with sample complexity S=O(logN/(βε)2) and time complexity linear in the sample size, O(SN). 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−itH in a small t regime with similar sample and time complexity.
Abstract. We study the problem of learning a local quantum Hamiltonian [Formula: see text] given copies of its Gibbs state [Formula: see text] at a known inverse temperature [Formula: see text]. Anshu et al. [2020 IEEE 61st Annual Symposium on Foundations of Computer Science, pp. 685–691] gave an algorithm to learn a Hamiltonian on [Formula: see text] qubits to precision [Formula: see text] 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, PRX Quantum, 4 (2023), 040201 ; Anshu and Arunachalam, Nature Rev. Phys., 6 (2023), pp. 59–69 ], with prior work only resolving this in the limited cases of high temperature [ Haah, Kothari, and Tang, Markov field on finite graphs and lattices, 1971 ] or commuting terms [ Anshu et al., Efficient learning of commuting Hamiltonians on lattices, 2021 ]. We fully resolve this problem, giving a polynomial time algorithm for learning [Formula: see text] to precision [Formula: see text] from polynomially many copies of the Gibbs state at any constant [Formula: see text]. Our main technical contribution is a new flat polynomial approximation to the exponential function, and a translation between multivariate 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.
Learning the Hamiltonian underlying a quantum many-body system in thermal equilibrium is a fundamental task in quantum learning theory and experimental sciences. To learn the Gibbs state of local Hamiltonians at any constant inverse temperature, the state-of-the-art provable algorithms fall short of the optimal sample and computational complexity, in sharp contrast with the locality and simplicity in the classical cases. In this work, we present a learning algorithm that learns each local term of a n-qubit Hamiltonian on any bounded-degree graph to a constant additive error with the optimal sample complexity O(logn). The protocol uses parallelizable local quantum measurements that act within bounded neighborhoods of the graph and near-linear-time classical post-processing. We also give a learning algorithm for lattice Hamiltonians with near-optimal scaling on the learning precision and the inverse temperature. At the heart of our algorithm is the interplay between locality, the Kubo-MartinSchwinger condition, and the operator Fourier transform at arbitrary temperatures.