  Preparing ground states and thermal states is essential for simulating
quantum systems on quantum computers. Despite the hope for practical quantum
advantage in quantum simulation, popular state preparation approaches have been
challenged. Monte Carlo-style quantum Gibbs samplers have emerged as an
alternative, but prior proposals have been unsatisfactory due to technical
obstacles rooted in energy-time uncertainty. We introduce simple
continuous-time quantum Gibbs samplers that overcome these obstacles by
efficiently simulating Nature-inspired quantum master equations (Lindbladians).
In addition, we construct the first provably accurate and efficient algorithm
for preparing certain purified Gibbs states (called thermal field double states
in high-energy physics) of rapidly thermalizing systems; this algorithm also
benefits from a quantum walk speedup. Our algorithms' costs have a provable
dependence on temperature, accuracy, and the mixing time (or spectral gap) of
the relevant Lindbladian. We complete the first rigorous proof of finite-time
thermalization for physically derived Lindbladians by developing a general
analytic framework for nonasymptotic secular approximation and approximate
detailed balance. Given the success of classical Markov chain Monte Carlo
(MCMC) algorithms and the ubiquity of thermodynamics, we anticipate that
quantum Gibbs sampling will become indispensable in quantum computing.
