Optimal quantum mixing for slowly evolving sequences of Markov chains

Quantum walks are the quantum counterpart of classical random walks and, correspondingly, many classical algorithms which are based upon classical random walks naturally lend themselves to be quantized. This quantization, either in the form of coined quantum walks [1-4] or using the so called Szegedy walk operator [5], allows to exploit coherence and entanglement to speedup many computational tasks, with improvements with respect to classical algorithms that are typically quadratic or, in some special circumstances, exponential [6, 7]. Henceforth quantum walks have been employed in a variety of quantum algorithms with applications ranging from statistical physics [8, 9], to combinatorial optimization problems [10], to machine learning [11]. The primary motivation for the quesiton we study in this work is the theory of quantum walks originated from their applicability to quantum machine learning, as demonstrated by the results of [11]. Therein it was shown that it is possible to achieve quadratic speedups in the deliberation time of a learning agent by exploitation of Szegedy quantum walks in conjunction with amplitude amplification. However, together with the certifiable speedups, quantum algorithms usually come together with a plethora of caveats and constraints that can impair their general applicability. In particular, the problem that spurred the present investigation is the following: the algorithm presented in [11] required that a quantum state encoding the stationary distribution is provided at the beginning of the algorithm. While the original paper showed how this assumption can be justified under certain assumptions on the nature of the learning algorithm, the question of other scenarios which provide means to generate such initial states efficiently remained open.