On Efficient Solutions of General Structured Markov Processes in Quantum Computational Environments

Abstract

The most-efficient algorithms for computing the stationary distribution π of such M/G/1-type processes on digital computers consist of cyclic reduction (CR) methods. Despite the computational benefits of CR, the time to compute π can still be prohibitive for large stochastic models. Quantum computers offer the potential of achieving significant performance advantages for certain computational problems. Our focus is therefore on devising, from a mathematical perspective, the first quantum algorithms for efficiently computing π for structured Markov processes. We derive a mathematical analysis that establishes theoretical properties of our quantum algorithms, including the potential for significant performance improvements over the most-efficient CR algorithms in settings of both theoretical and practical importance. Although motivated by general structured Markov processes, our quantum algorithms can be exploited to address a much larger class of computational problems, as well as a subroutine in solving larger problems involving the stationary distribution on a quantum computer. This short paper briefly summarizes our full paper (arXiv:2404.17959, 2025) to which we refer the reader for all details and references.