Solving Markov Chains with Analog Quantum Computing: The Fine Print

• URL: http://arxiv.org/abs/2508.02199v1
• Date: Mon, 04 Aug 2025 08:52:37 GMT
• Title: Solving Markov Chains with Analog Quantum Computing: The Fine Print
• Authors: Ward van der Schoot, Niels M. P. Neumann,
• Abstract summary: Some quantum algorithms can be applied out-of-the-box, while others require black box oracles.<n>We provide a similar fine print for the first analog quantum algorithm that computes the stationary distribution of Markov chains.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• 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.

Related papers

• The Algorithm for Solving Quantum Linear Systems of Equations With Coherent Superposition and Its Extended Applications [8.8400072344375]
  We propose two quantum algorithms for solving quantum linear systems of equations with coherent superposition. The two quantum algorithms can both compute the rank and general solution by one measurement. Our analysis indicates that the proposed algorithms are mainly suitable for conducting attacks against lightweight symmetric ciphers.
  arXiv  Detail & Related papers  (2024-05-11T03:03:14Z)
• Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
  Quantum computing sets the foundation for new ways of designing algorithms. New challenges arise concerning which field quantum speedup can be achieved. Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
  arXiv  Detail & Related papers  (2024-02-26T09:32:07Z)
• Making the cut: two methods for breaking down a quantum algorithm [0.0]
  It remains a major challenge to find quantum algorithms that may reach computational advantage in the present era of noisy, small-scale quantum hardware. We identify and characterize two methods of breaking down'' quantum algorithms into rounds of lower (query) depth. We show that for the first problem parallelization offers the best performance, while for the second is the better choice.
  arXiv  Detail & Related papers  (2023-05-17T18:00:06Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem. The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
  arXiv  Detail & Related papers  (2023-04-18T11:57:15Z)
• An introduction to variational quantum algorithms for combinatorial optimization problems [0.0]
  This tutorial provides a mathematical description of the class of Variational Quantum Algorithms. We introduce precisely the key aspects of these hybrid algorithms on the quantum side and the classical side. We devote a particular attention to QAOA, detailing the quantum circuits involved in that algorithm, as well as the properties satisfied by its possible guiding functions.
  arXiv  Detail & Related papers  (2022-12-22T14:27:52Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Parametrized Complexity of Quantum Inspired Algorithms [0.0]
  Two promising areas of quantum algorithms are quantum machine learning and quantum optimization. Motivated by recent progress in quantum technologies and in particular quantum software, research and industrial communities have been trying to discover new applications of quantum algorithms.
  arXiv  Detail & Related papers  (2021-12-22T06:19:36Z)
• Benchmarking Small-Scale Quantum Devices on Computing Graph Edit Distance [52.77024349608834]
  Graph Edit Distance (GED) measures the degree of (dis)similarity between two graphs in terms of the operations needed to make them identical. In this paper we present a comparative study of two quantum approaches to computing GED.
  arXiv  Detail & Related papers  (2021-11-19T12:35:26Z)
• Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
  We create classical (non-quantum) dynamic data structures supporting queries for recommender systems and least-squares regression. We argue that the previous quantum-inspired algorithms for these problems are doing leverage or ridge-leverage score sampling in disguise.
  arXiv  Detail & Related papers  (2020-11-09T01:13:07Z)
• Quantum algorithmic differentiation [0.0]
  We present an algorithm to perform algorithmic differentiation in the context of quantum computing. We present two versions of the algorithm, one which is fully quantum and one which employees a classical step.
  arXiv  Detail & Related papers  (2020-06-23T22:52:22Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.