Learning quantum Hamiltonians at any temperature in polynomial time
Ainesh Bakshi Allen Liu Ankur Moitra Ewin Tang
We study the problem of learning a local quantum Hamiltonian $H$ given copies
of its Gibbs state $\rho = e^{-\beta H}/\textrm{tr}(e^{-\beta H})$ at a known
inverse temperature $\beta>0$. Anshu, Arunachalam, Kuwahara, and Soleimanifar
(arXiv:2004.07266) gave an algorithm to learn a Hamiltonian on $n$ qubits to
precision $\epsilon$ 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 $\epsilon$ from polynomially many copies of the Gibbs state at any
constant $\beta > 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.