2024/04/27 by Vasileios Kalantzis, Kalantzis, Vasileios, Mark S. Squillante +3
Computer Science · Engineering · #Advanced Data Processing Techniques #Bayesian Modeling and Causal Inference #Cloud Computing and Resource Management #FOS: Mathematics #FOS: Physical sciences #Numerical Analysis (math.NA) #Probability (math.PR) #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.2404.17959
openalex publication_date 2024/04/27 · openalex created_date 2024/05/11 · openalex updated_date 2026/07/28
We study from a theoretical viewpoint the fundamental problem of efficiently computing the stationary distribution of general classes of structured Markov processes. In strong contrast with previous work, we consider this fundamental problem within the context of quantum computational environments from a mathematical perspective and devise the first quantum algorithms for computing the stationary distribution of general structured Markov processes. We derive a mathematical analysis of the computational properties of our quantum algorithms together with related theoretical results, establishing that our quantum algorithms provide the potential for significant computational improvements over that of the best-known and most-efficient classical algorithms in various 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 numerical computation problems, as well as to potentially play the role of a subroutine as part of solving larger computational problems involving the stationary distribution on a quantum computer.