  The computational complexity of simulating quantum many-body systems
generally scales exponentially with the number of particles. This enormous
computational cost prohibits first principles simulations of many important
problems throughout science, ranging from simulating quantum chemistry to
discovering the thermodynamic phase diagram of quantum materials or
high-density neutron stars. We present a classical algorithm that samples from
a high-temperature quantum Gibbs state in a computational (product state)
basis. The runtime grows polynomially with the number of particles, while error
vanishes polynomially. This algorithm provides an alternative strategy to
existing quantum Monte Carlo methods for overcoming the sign problem. Our
result implies that measurement-based quantum computation on a Gibbs state can
provide exponential speed up only at sufficiently low temperature, and further
constrains what tasks can be exponentially faster on quantum computers.
