About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
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.