Quantum Speedup for Nonreversible Markov Chains

Abstract

Quantum algorithms can potentially solve a handful of problems more efficiently than their classical counterparts. In that context, it has been discussed that Markov chains problems could be solved significantly faster using quantum computing. Indeed, previous work suggests that quantum computers could accelerate sampling from the stationary distribution of reversible Markov chains. However, in practice, certain physical processes of interest are nonreversible in the probabilistic sense and reversible Markov chains can sometimes be replaced by more efficient nonreversible chains targeting the same stationary distribution. This study constructs Markov chain reversibilizations and develops quantum algorithmic techniques to accelerate nonreversible processes. Such an up-to-exponential quantum speedup goes beyond the predicted quadratic quantum acceleration for reversible chains and is likely to have a decisive impact on many applications ranging from statistics and machine learning to computational modeling in physics, chemistry, biology and finance.

References in corpus (11)

• Quantum Amplitude Amplification and Estimation
• Fixed-point quantum search with an optimal number of queries
• Iterative Quantum Amplitude Estimation
• QFold: Quantum Walks and Deep Learning to Solve Protein Folding
• Efficient Quantum Walk Circuits for Metropolis-Hastings Algorithm
• Quantum computing for chemistry and physics applications from a Monte Carlo perspective
• Efficient quantum circuits for Szegedy quantum walks
• Quantum rejection sampling
• Molecular simulation from modern statistics: Continuous-time, continuous-space, exact
• Non-reversible lifts of reversible diffusion processes and relaxation times
• Generalized Quantum Singular Value Transformation