The Fine Print of Solving Markov Chains with Analog Quantum Computing
article
With a growing interest in quantum computing, the number of proposed quantum algorithms grows as well. The practical epplicability 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 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.
TNO Identifier
1002789
Source
Arxiv