  We study the problem of learning the Hamiltonian of a quantum many-body
system given samples from its Gibbs (thermal) state. The classical analog of
this problem, known as learning graphical models or Boltzmann machines, is a
well-studied question in machine learning and statistics. In this work, we give
the first sample-efficient algorithm for the quantum Hamiltonian learning
problem. In particular, we prove that polynomially many samples in the number
of particles (qudits) are necessary and sufficient for learning the parameters
of a spatially local Hamiltonian in l_2-norm.
  Our main contribution is in establishing the strong convexity of the
log-partition function of quantum many-body systems, which along with the
maximum entropy estimation yields our sample-efficient algorithm. Classically,
the strong convexity for partition functions follows from the Markov property
of Gibbs distributions. This is, however, known to be violated in its exact
form in the quantum case. We introduce several new ideas to obtain an
unconditional result that avoids relying on the Markov property of quantum
systems, at the cost of a slightly weaker bound. In particular, we prove a
lower bound on the variance of quasi-local operators with respect to the Gibbs
state, which might be of independent interest. Our work paves the way toward a
more rigorous application of machine learning techniques to quantum many-body
problems.
