Quantum speedup for mixing a Markov chain can be achieved based on the construction of slowly-varying
r Markov chains where the initial chain can be easily prepared and the spectral gaps have uniform lower bound. The overall complexity is proportional to
r. We present a multi-level approach to construct such a sequence of
r Markov chains by varying a resolution parameter
h. We show that the density function of a low-resolution Markov chain can be used to warm start the Markov chain with high resolution. We prove that in terms of the chain length the new algorithm has
O(1) complexity rather than
O(r).We present a novel approach to quantizing Markov chains. The approach is based on the Markov chain coupling method, which is frequently used to prove fast mixing. Given a particular coupling, e.g., a grand coupling, we construct a completely positive and trace preserving map. This quantum map has a unique fixed point, which corresponds to the quantum sample (qsample) of the classical Markov chain's stationary distribution. We show that the convergence time of the quantum map is directly related to the coupling time of the Markov chain coupling.