On Quantum Algorithms for Random Walks in the Nonnegative Quarter Plane

Abstract

We consider the problem of computing the stationary distribution of a general class of random walks in the nonnegative quarter plane, with a focus on efficient quantum computing solutions. We devise quantum algorithms for computing the stationary distribution and establish significant speedups under different conditions, including quadratic speedup over the classical cyclic reduction algorithm, exponential improvement over so-called quantum walk algorithms, and addressing for the first time a well-known computational bottleneck of quantum walk algorithms.