General classes of structured Markov processes are of great importance in both theory and practice, arising in many fields of science, engineering, and business. Of particular interest are M/G/1-type processes, G/M/1-type processes, and quasi-birth-and-death (QBD) processes whose transitions on a two-dimensional lattice are respectively skip-free to the left, skip-free to the right, and skip-free to the left and to the right, with no restrictions upward or downward. Matrix-analytic methods have played a fundamental role in the study of such structured Markov processes, including analytical approaches based in part on exploiting probabilistic interpretations and computational approaches based in part on numerical analysis and numerical methods. With respect to this second approach, the best-known and most-efficient algorithms for computing the stationary distribution of structured Markov processes primarily consist of different variants of cyclic reduction methods.

Despite the great strides and computational benefits of these numerical cyclic reduction methods, the time required to compute the stationary distribution can still be prohibitively expensive for very large structured Markov processes, for supporting online or real-time applications of such stochastic processes, and/or as a component of broader computational problems. Quantum computers offer the potential of achieving significant performance advantages for certain computational problems, with the possibility of delivering polynomial-to-exponential speedups over the best-known and most-efficient solutions on classical computers. Despite this great potential, however, a number of important cases have been identified where quantum algorithms provide modest or no benefits over the most-efficient classical algorithms.

In this talk, we will consider methodological solutions of the general classes of structured Markov processes within the context of quantum computational environments from a mathematical perspective. A high-level overview of some of the basics of quantum computing, with roots in quantum mechanical probability theory and linear algebra, will be provided to introduce a number of the key aspects of a foundational background. Next, we will present the first quantum algorithms for computing the stationary distribution of structured Markov processes. We then will present a mathematical analysis of the computational errors and computational complexity of our quantum algorithms together with related theoretical results.

This includes: establishing the potential exponential speedup over the best-known and most-efficient classical algorithms for the computation phase in the decision-space of quantum computers, which is of specific interest from a mathematical perspective; establishing the potential polynomial-to-exponential speedup over the best-known and most-efficient classical algorithms when the properties of the input matrices together with block encoding allow efficient data loading; and establishing the potential polynomial-to-exponential speedup over the best-known and most-efficient classical algorithms when the properties of the output matrix together with sampling-based methods allow efficient result readout. This also expands the limited set of quantum algorithms that provably achieve significant computational improvements in various settings of both theoretical and practical importance, while further making significant algorithmic and theoretical contributions. It is additionally important to note that the computation of the stationary distribution of structured Markov processes may play the role of a subroutine within the context of solving larger computational problems on the quantum computer, such as stochastic optimization problems involving the stationary distribution of the associated structured Markov process, in which cases the computation phase would be more critical than the input and output phases to the overall computational complexity.