Improved algorithms for learning quantum Hamiltonians, via flat polynomials
This is an incremental improvement for researchers in quantum machine learning, addressing a specific bottleneck in Hamiltonian learning.
The paper tackles the problem of learning quantum Hamiltonians from Gibbs states by improving the sample complexity and runtime to singly exponential in the inverse-temperature parameter, compared to prior doubly exponential results.
We give an improved algorithm for learning a quantum Hamiltonian given copies of its Gibbs state, that can succeed at any temperature. Specifically, we improve over the work of Bakshi, Liu, Moitra, and Tang [BLMT24], by reducing the sample complexity and runtime dependence to singly exponential in the inverse-temperature parameter, as opposed to doubly exponential. Our main technical contribution is a new flat polynomial approximation to the exponential function, with significantly lower degree than the flat polynomial approximation used in [BLMT24].