Abstract
The thermalization process refers to a quantum system converging to its Gibbs state when coupled to a bath at finite temperature. Whether quantum computational advantage can be achieved with this realistic physical setup has remained open, due to the difficulty of finding instances that thermalize quickly while being classically hard. Here we consider sampling from the measurement outcome distribution of quantum Gibbs states at constant temperature 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 the Davies generator is rapidly-mixing. This implies rapid thermalization, as well as efficient preparation of the Gibbs state on a quantum computer. 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 shallow quantum circuits. The key step in the reduction is constructing a fault-tolerance scheme for shallow IQP circuits.