Learning quantum Hamiltonians at any temperature in polynomial time with Chebyshev and bit complexity
This provides an efficient algorithm for learning quantum Hamiltonians, which is important for quantum physics and quantum computing applications, though it builds incrementally on prior work.
The paper tackles the problem of learning local quantum Hamiltonians from Gibbs states at any temperature by developing a new flat polynomial approximation using Chebyshev expansion, which reduces the problem to polynomial optimization solvable with moment/SOS relaxations. The result shows that learning a k-local Hamiltonian with bounded-degree interaction graphs runs in polynomial time under mild assumptions.
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.