Video URL http://pirsa.org/21060002
We study the problem of learning a Hamiltonian given copies of its Gibbs state at a known inverse temperature. Anshu et al. recently studied the sample complexity (number of copies of the Gibbs state needed) of this problem for geometrically local Hamiltonians. In the high-temperature regime, their algorithm has sample complexity polynomial in the system size, temperature, and accuracy. Their algorithm can also be implemented with polynomial, but suboptimal, time complexity. Here, we study the same question for a more general class of Hamiltonians and present an algorithm that solves this problem with improved sample complexity and time complexity linear in the sample size. Furthermore, we prove a matching lower bound showing that our algorithm's sample complexity is optimal, and hence our time complexity is also optimal. Joint work with Robin Kothari and Ewin Tang.