Low-Depth Quantum Metropolis Algorithm

We construct a simple quantum version of the classical Metropolis algorithm to prepare and observe quantum thermal states. It induces both a quantum Markov chain that mixes the quantum thermal state and a classical Markov chain that mixes its observable measurements and enables a low-depth quantum circuit implementation. A Gaussian-filtered variant of quantum phase estimation enables thermalization times proportional to the reciprocal of temperature and the logarithm of biasing error. This matches the thermalization time of imaginary-time evolution, against which our algorithm performs favorably.