Quantum computers promise to tackle quantum simulation problems that are classically intractable1. Although a lot of quantum algorithms2–4 have been developed for simulating quantum dynamics, a general-purpose method for simulating low-temperature quantum phenomena remains unknown. In classical settings, the analogous task of sampling from thermal distributions has been largely addressed by Markov Chain Monte Carlo (MCMC) methods5,6. Here we propose an efficient quantum algorithm for thermal simulation that—akin to MCMC methods—exhibits detailed balance, respects locality and serves as a toy model for thermalization in open quantum systems. The enduring impact of MCMC methods suggests that our new construction may play an equally important part in quantum computing and applications in the physical sciences and beyond.
