Abstract
Markov chain methods are remarkably successful in computational physics,machine learning, and combinatorial optimization. The cost of such methodsoften reduces to the mixing time, i.e. \ the time required to reach the steadystate of the Markov chain, which scales as $\delta^{-1}$, the inverse of thespectral gap. It has long been conjectured that quantum computers offer nearlygeneric quadratic improvements for mixing problems. However, except in specialcases, quantum algorithms achieve a run-time of $\O(\sqrt{\delta^{-1}}\sqrt{N})$, which introduces a costly dependence on the Markov chain size $N,$not present in the classical case. Here, we re-address the problem of mixing ofMarkov chains when these form a slowly evolving sequence. This setting is akinto the simulated annealing setting, and is commonly encountered in physics,material sciences and machine learning. We provide a quantum memory-efficientalgorithm with a run-time of $\O(\sqrt{\delta^{-1}} \sqrt[4]{N})$, neglectinglogarithmic terms, which is an important improvement for large state spaces.Further our algorithms output quantum encodings of distributions, which hasadvantages over classical outputs. Finally, we discuss the run-time bounds ofmixing algorithms and show that, under certain assumptions, our algorithms areoptimal.