  A quantum system coupled to a bath at some fixed, finite temperature
converges to its Gibbs state. This thermalization process defines a natural,
physically-motivated model of quantum computation. However, whether quantum
computational advantage can be achieved within this realistic physical setup
has remained open, due to the challenge of finding systems that thermalize
quickly, but are classically intractable. Here we consider sampling from the
measurement outcome distribution of quantum Gibbs states at constant
temperatures, and prove that this task demonstrates quantum computational
advantage. We design a family of commuting almost-local Hamiltonians (parent
Hamiltonians of shallow quantum circuits) and prove that they rapidly converge
to their Gibbs states under the standard physical model of thermalization (as a
continuous-time quantum Markov chain). On the other hand, we show that no
polynomial time classical algorithm can sample from the measurement outcome
distribution by reducing to the classical hardness of sampling from noiseless
shallow quantum circuits. The key step in the reduction is constructing a
fault-tolerance scheme for shallow IQP circuits against input noise.
