  The Markov Chain Monte Carlo method is at the heart of efficient
approximation schemes for a wide range of problems in combinatorial enumeration
and statistical physics. It is therefore very natural and important to
determine whether quantum computers can speed-up classical mixing processes
based on Markov chains. To this end, we present a new quantum algorithm, making
it possible to prepare a quantum sample, i.e., a coherent version of the
stationary distribution of a reversible Markov chain. Our algorithm has a
significantly better running time than that of a previous algorithm based on
adiabatic state generation. We also show that our methods provide a speed-up
over a recently proposed method for obtaining ground states of (classical)
Hamiltonians.
