Publication
INFORMS 2022
Short paper

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.

Date

16 Oct 2022

Publication

INFORMS 2022