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

• URL: http://arxiv.org/abs/2404.17959v1
• Date: Sat, 27 Apr 2024 17:06:16 GMT
• Title: On Quantum Algorithms for Efficient Solutions of General Classes of Structured Markov Processes
• Authors: Vasileios Kalantzis, Mark S. Squillante, Shashanka Ubaru,
• Abstract summary: We devise the first quantum algorithms for computing the stationary distribution of structured Markov processes. Although motivated by structured Markov processes, our quantum algorithms have the potential for being exploited to address a much larger class of numerical computation problems.
• Score: 8.26313272946503
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We study 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 problem within the context of quantum computational environments from a mathematical perspective and devise the first quantum algorithms for computing the stationary distribution of 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 classical algorithms in various settings of both theoretical and practical importance. Although motivated by structured Markov processes, our quantum algorithms have the potential for being exploited to address a much larger class of numerical computation problems.

Related papers

• Performance Benchmarking of Quantum Algorithms for Hard Combinatorial Optimization Problems: A Comparative Study of non-FTQC Approaches [0.0]
  This study systematically benchmarks several non-fault-tolerant quantum computing algorithms across four distinct optimization problems. Our benchmark includes noisy intermediate-scale quantum (NISQ) algorithms, such as the variational quantum eigensolver. Our findings reveal that no single non-FTQC algorithm performs optimally across all problem types, underscoring the need for tailored algorithmic strategies.
  arXiv  Detail & Related papers  (2024-10-30T08:41:29Z)
• A typology of quantum algorithms [1.967426628955258]
  We draw the current landscape of quantum algorithms, by classifying about 130 quantum algorithms. The primary objectives include revealing trends of algorithms, identifying promising fields for implementations in the NISQ era, and identifying the key algorithmic primitives that power quantum advantage.
  arXiv  Detail & Related papers  (2024-07-06T20:41:05Z)
• 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)
• Improved Quantum Algorithms for Eigenvalues Finding and Gradient Descent [0.0]
  Block encoding is a key ingredient in the recently developed quantum signal processing that forms a unifying framework for quantum algorithms. In this article, we utilize block encoding to substantially enhance two previously proposed quantum algorithms. We show how to extend our proposed method to different contexts, including matrix inversion and multiple eigenvalues estimation.
  arXiv  Detail & Related papers  (2023-12-22T15:59:03Z)
• 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)
• 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)
• Quantum algorithms for group convolution, cross-correlation, and equivariant transformations [9.134244356393665]
  Group convolutions and cross-correlations are commonly used in mathematics to analyze or take advantage of symmetries inherent in a given problem setting. Here, we provide efficient quantum algorithms for performing linear group convolutions and cross-correlations on data stored as quantum states.
  arXiv  Detail & Related papers  (2021-09-23T12:21:31Z)
• Detailed Account of Complexity for Implementation of Some Gate-Based Quantum Algorithms [55.41644538483948]
  In particular, some steps of the implementation, as state preparation and readout processes, can surpass the complexity aspects of the algorithm itself. We present the complexity involved in the full implementation of quantum algorithms for solving linear systems of equations and linear system of differential equations.
  arXiv  Detail & Related papers  (2021-06-23T16:33:33Z)
• 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)
• An Application of Quantum Annealing Computing to Seismic Inversion [55.41644538483948]
  We apply a quantum algorithm to a D-Wave quantum annealer to solve a small scale seismic inversions problem. The accuracy achieved by the quantum computer is at least as good as that of the classical computer.
  arXiv  Detail & Related papers  (2020-05-06T14:18:44Z)
• Approximating the quantum approximate optimization algorithm with digital-analog interactions [0.0]
  We show that the digital-analog paradigm is suited to the variational quantum approximate optimisation algorithm. We observe regimes of single-qubit operation speed in which the considered variational algorithm provides a significant improvement over non-variational counterparts.
  arXiv  Detail & Related papers  (2020-02-27T16:01:40Z)

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.