Learning quantum Hamiltonians at any temperature in polynomial time with
  Chebyshev and bit complexity
Ales Wodecki Jakub Marecek
We consider the problem of learning local quantum Hamiltonians given copies
of their Gibbs state at a known inverse temperature, following Haah et al.
[2108.04842] and Bakshi et al. [arXiv:2310.02243]. Our main technical
contribution is a new flat polynomial approximation of the exponential function
based on the Chebyshev expansion, which enables the formulation of learning
quantum Hamiltonians as a polynomial optimization problem. This, in turn, can
benefit from the use of moment/SOS relaxations, whose polynomial bit complexity
requires careful analysis [O'Donnell, ITCS 2017]. Finally, we show that
learning a $k$-local Hamiltonian, whose dual interaction graph is of bounded
degree, runs in polynomial time under mild assumptions.