Faster quantum mixing for slowly evolving sequences of Markov chains

Abstract

Markov chain methods are remarkably successful in computational physics, machine learning, and combinatorial optimization. The cost of such methods often reduces to the mixing time, i.e., the time required to reach the steady state of the Markov chain, which scales as ${\delta }^{-1}$, the inverse of the spectral gap. It has long been conjectured that quantum computers offer nearly generic quadratic improvements for mixing problems. However, except in special cases, quantum algorithms achieve a run-time of $\mathcal{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 of Markov chains when these form a slowly evolving sequence. This setting is akin to the simulated annealing setting and is commonly encountered in physics, material sciences and machine learning. We provide a quantum memory-efficient algorithm with a run-time of $\mathcal{O}(\sqrt{{\delta }^{-1}}\sqrt[4]{N})$, neglecting logarithmic terms, which is an important improvement for large state spaces. Moreover, our algorithms output quantum encodings of distributions, which has advantages over classical outputs. Finally, we discuss the run-time bounds of mixing algorithms and show that, under certain assumptions, our algorithms are optimal.

20 pages, 2 figures

References in corpus (7)

• Quantum speedup of Monte Carlo methods
• Creating superpositions that correspond to efficiently integrable probability distributions
• Fixed-point quantum search with an optimal number of queries
• Efficient Bayesian Phase Estimation
• Quantum Simulations of Classical Annealing Processes
• Speed-up via Quantum Sampling
• Almost uniform sampling via quantum walks

Cited by in corpus (9)

• Quantum enhancements for deep reinforcement learning in large spaces
• Quantum walk approach to simulating parton showers
• How fast do quantum walks mix?
• Collider Events on a Quantum Computer
• Analog quantum algorithms for the mixing of Markov chains
• Quantum algorithm for estimating volumes of convex bodies
• Preparing Many Copies of a Quantum State in the Black-Box Model
• Faster quantum mixing of Markov chains in non-regular graph with fewer qubits
• Solving Markov Chains with Analog Quantum Computing: The Fine Print