Learning Quantum Hamiltonians at Any Temperature in Polynomial Time

We study the problem of learning a local quantum Hamiltonian H given copies of its Gibbs state ρ = e -βH / tr(e -βH ) at a known inverse temperature β > 0. Anshu, Arunachalam, Kuwahara, and Soleimanifar [AAKS20] 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 [Alh23; AA23], with prior work only resolving this in the limited cases of high temperature [HKT22] or commuting terms [AAKS21]. 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.