arXiv:2404.17959 · ACM SIGMETRICS Performance Evaluation Review

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

Vasileios Kalantzis, Mark S. Squillante, Shashanka Ubaru

Published Mar 31, 2026• 0 citations

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.

DOI: 10.1145/3797823.3797840

Related papers

On Quantum Algorithms for Efficient Solutions of General Classes of Structured Markov Processes

Vasileios Kalantzis, Mark S. Squillante, Shashanka Ubaru

Multidimensional Markov processes arise in many aspects of the mathematical performance analysis, modeling and optimization of computer systems and networks. Within this context, general classes of structured Markov processes are of particular importance in both theory and practice.

ACM SIGMETRICS Performance Evaluation ReviewSep 5, 20241 citation

Quantum speedup for nonreversible Markov chains

Baptiste Claudon, Jean‐Philip Piquemal, Pierre Monmarché

Quantum algorithms can potentially solve a handful of problems more efficiently than their classical counterparts. In that context, it has been discussed that Markov chains problems could be solved significantly faster using quantum computing. Indeed, previous work suggests that quantum computers could accelerate sampling from the stationary distribution of reversible Markov chains. However, in practice, certain physical processes of interest are nonreversible in the probabilistic sense and reversible Markov chains can sometimes be replaced by more efficient nonreversible chains targeting the same stationary distribution. This study constructs Markov chain reversibilizations and develops quantum algorithmic techniques to accelerate nonreversible processes. Such an up-to-exponential quantum speedup goes beyond the predicted quadratic quantum acceleration for reversible chains and is likely to have a decisive impact on many applications ranging from statistics and machine learning to computational modeling in physics, chemistry, biology and finance.

arXiv:2501.05868Nature CommunicationsNov 28, 20251 citation

Quantum algorithm for metabolic network analysis

Ashish Joshi, Takahiko Koyama

Abstract Biological systems, such as cellular metabolism, involve thousands of reactions that together determine how cells grow, respond to their environment, and produce energy. Modeling and analyzing these systems require solving very large mathematical problems that can quickly become computationally prohibitive. To address this challenge, we present a quantum algorithm to analyze metabolic networks, focusing on flux balance analysis as a representative case. We use a quantum interior point method consisting of a quantum subroutine for matrix inversion. Specifically, we reformulate the metabolic optimization problem for efficient execution on a quantum computer using quantum singular value transformation, enabling a rapid solution of complex systems that arise in flux balance analysis. This quantum approach offers a potential computational advantage over classical interior point methods for large and well-conditioned networks. We demonstrate the practical applicability of our method with numerical simulations on the glycolysis and tricarboxylic acid (TCA) cycle network and show that the quantum solution converges to the correct biological objective. This work represents the first application of quantum algorithms to metabolic pathway analysis, establishing a new direction for quantum computational biology and paving the way for quantum approaches to large-scale biological optimization.

Machine Learning with ApplicationsMay 11, 20260 citations

Quantum algorithm for Markov random fields structure learning

Liming Zhao, Ming-Xing Luo, Lin‐Chun Wan

Abstract Probabilistic graphical models play a crucial role in machine learning and have wide applications across various fields. A pivotal subset within this realm is undirected graphical models, also known as Markov random fields. In this work, we explore the application of quantum computing to the field of machine learning, specifically focusing on the task of structure learning in Markov random fields. We propose a quantum algorithm for structure learning of an r-wise Markov Random Field with a bounded degree underlying graph, based on a nearly optimal classical greedy algorithm. Our quantum algorithm provides a polynomial speed-up over the classical counterpart, with a runtime of O ˜ 2 L M n r + 1 log ( 1 / w ) compared to the classical O ˜ M n r , where n is the number of variables. It is nearly a quadratic speedup in terms of n. Through this research, we aim to showcase the potential advantages of quantum computation in tackling complex machine-learning problems. Furthermore, the sample complexity O ˜ 2 2 L τ 2 δ 2 L ( log ( 1 / w ) + log n ) remains consistent between classical and quantum approaches, ensuring the efficiency and robustness of our method. By demonstrating the efficiency and scalability of our quantum algorithm for structure learning, we contribute to the growing body of work that highlights the role of quantum computing in advancing the field of machine learning and probabilistic graphical models.

Physica ScriptaJun 26, 20251 citation

Role of Quantum Computing in Solving Optimization Problems in Artificial Intelligence

Yuri Alexeev, Tanbir Hasan Taz, Mohammad Zobair Hossain

Quantum computing, leveraging quantum mechanics, promises to enhance optimization processes in artificial intelligence (AI) by addressing challenges faced by classical computing in solving complex problems. This study investigates the role of quantum computing in optimizing AI tasks, focusing on algorithms such as Quantum Approximate Optimization Algorithm (QAOA) and Quantum Annealing (QA) for improved efficiency in optimization. A hybrid quantum-classical approach was used to evaluate the performance of quantum algorithms in optimization tasks, including combinatorial optimization and machine learning model tuning. QAOA and QA were applied to benchmark problems, such as Max-Cut and Traveling Salesman Problem (TSP). The study involved a comparative analysis between quantum algorithms and classical optimization techniques using performance metrics like solution quality, computational time, and scalability. Data were gathered through simulation on a quantum computing platform, and results were analyzed using statistical methods to assess improvements. The results showed that quantum computing significantly outperformed classical methods in solving large-scale optimization problems. QAOA demonstrated a 30% improvement in solution quality for Max-Cut problems, and QA showed a 25% faster convergence in TSP compared to classical algorithms. Quantum algorithms demonstrated scalability advantages as the problem size increased, with quantum methods achieving up to a 40% reduction in computational time for large instances. Furthermore, 70% of the tested cases showed significant improvements in solution accuracy, confirming the potential of quantum computing in real-world AI applications. Quantum computing, through QAOA and QA, offers substantial improvements in solving complex optimization problems in AI, presenting a transformative opportunity for the future of optimization algorithms.

Pacific Journal of Advanced Engineering InnovationsDec 31, 20243 citations

Quantum Algorithms

A. O. Pittenger

We are now ready to assemble quantum subroutines into quantum algorithms. A reasonable first question is: Are there problems which can be solved efficiently on a quantum computer? In his analysis of a universal quantum computer [25], Deutsch illustrated quantum parallelism by constructing a procedure to compute the parity f (0) ⊕ f (1) of a function on one bit. In a generalization of this context, Deutsch and Jozsa [27] defined a quantum algorithm that could solve a problem more efficiently than is possible on a classical computer. This problem helped motivate the search for algorithms that could solve “real” problems, and Simon [67] provided an example that inspired Shor’s subsequent work on the factoring problem and on the discrete logarithm problem. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Birkhäuser Boston eBooksJan 1, 20010 citations