Learning Quantum Hamiltonians at Any Temperature in Polynomial Time

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.