Solving Markov Chains with Analog Quantum Computing: The Fine Print

Abstract

With a growing interest in quantum computing, the number of proposed quantum algorithms grows as well. The practical applicability of these algorithms differs: Some can be applied out-of-the-box, while others require black box oracles, which can not always be easily implemented. One of the first works to explicitly discuss these practical applicability aspects is by Aaronson discussing the \textit{fine print} of the HHL quantum algorithm that solves linear systems of equations. We extend this line of research by providing a similar fine print for the first analog quantum algorithm that computes the stationary distribution of Markov chains. We conclude that more focus should be put on this practical applicability of quantum algorithms, either through a separate line of research, or through more attention when introducing the algorithm.

References in corpus (7)

• Quantum algorithm for solving linear systems of equations
• Quantum walks can find a marked element on any graph
• Almost uniform sampling via quantum walks
• The Dirichlet Markov Ensemble
• Faster quantum mixing for slowly evolving sequences of Markov chains
• Analog quantum algorithms for the mixing of Markov chains
• The ensemble of random Markov matrices