Quantum Speedup for Nonreversible Markov Chains

• URL: http://arxiv.org/abs/2501.05868v1
• Date: Fri, 10 Jan 2025 11:09:40 GMT
• Title: Quantum Speedup for Nonreversible Markov Chains
• Authors: Baptiste Claudon, Jean-Philip Piquemal, Pierre Monmarché,
• Abstract summary: It has been discussed that Markov chains problems could be solved significantly faster using quantum computing.<n>This study uses modern quantum algorithmic techniques and Markov chain theory to sample from the stationary distribution of nonreversible Markov chains.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 uses modern quantum algorithmic techniques and Markov chain theory to sample from the stationary distribution of nonreversible Markov chains with faster worst-case runtime and without requiring the stationary distribution to be computed up to a multiplicative constant. 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.

Related papers

• Evaluation of phase shifts for non-relativistic elastic scattering using quantum computers [39.58317527488534]
  This work reports the development of an algorithm that makes it possible to obtain phase shifts for generic non-relativistic elastic scattering processes on a quantum computer.
  arXiv  Detail & Related papers  (2024-07-04T21:11:05Z)
• Bounding speedup of quantum-enhanced Markov chain Monte Carlo [0.0]
  We show that there is no speedup over classical sampling on a worst-case unstructured sampling problem. We present an upper bound to the Markov gap that rules out a speedup for any unital quantum proposal.
  arXiv  Detail & Related papers  (2024-03-05T16:20:01Z)
• Stochastic Quantum Sampling for Non-Logconcave Distributions and Estimating Partition Functions [13.16814860487575]
  We present quantum algorithms for sampling from nonlogconcave probability distributions. $f$ can be written as a finite sum $f(x):= frac1Nsum_k=1N f_k(x)$.
  arXiv  Detail & Related papers  (2023-10-17T17:55:32Z)
• A hybrid quantum-classical algorithm for multichannel quantum scattering of atoms and molecules [62.997667081978825]
  We propose a hybrid quantum-classical algorithm for solving the Schr"odinger equation for atomic and molecular collisions. The algorithm is based on the $S$-matrix version of the Kohn variational principle, which computes the fundamental scattering $S$-matrix. We show how the algorithm could be scaled up to simulate collisions of large polyatomic molecules.
  arXiv  Detail & Related papers  (2023-04-12T18:10:47Z)
• Efficient estimation of trainability for variational quantum circuits [43.028111013960206]
  We find an efficient method to compute the cost function and its variance for a wide class of variational quantum circuits. This method can be used to certify trainability for variational quantum circuits and explore design strategies that can overcome the barren plateau problem.
  arXiv  Detail & Related papers  (2023-02-09T14:05:18Z)
• 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)
• A single $T$-gate makes distribution learning hard [56.045224655472865]
  This work provides an extensive characterization of the learnability of the output distributions of local quantum circuits. We show that for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth $d=omega(log(n))$ Clifford circuits is hard.
  arXiv  Detail & Related papers  (2022-07-07T08:04:15Z)
• Faster quantum mixing of Markov chains in non-regular graph with fewer qubits [0.0]
  In quantum cases, qsampling from Markov chains can be constructed as preparing quantum states with amplitudes arbitrarily close to the square root of a stationary distribution. In this paper, a new qsampling algorithm for all reversible Markov chains is constructed by discrete-time quantum walks. In non-regular graphs, the invocation of the quantum fast-forward algorithm accelerates existing state-of-the-art qsampling algorithms for both discrete-time and continuous-time cases.
  arXiv  Detail & Related papers  (2022-05-12T14:08:08Z)
• Quantum-enhanced Markov chain Monte Carlo [0.22166578153935784]
  We introduce a quantum algorithm to sample from distributions that pose a bottleneck in several applications. In each step, the quantum processor explores the model in superposition to propose a random move, which is then accepted or rejected by a classical computer. We find that this quantum algorithm converges in fewer iterations than common classical MCMC alternatives on relevant problem instances.
  arXiv  Detail & Related papers  (2022-03-23T15:50:12Z)
• An Algebraic Quantum Circuit Compression Algorithm for Hamiltonian Simulation [55.41644538483948]
  Current generation noisy intermediate-scale quantum (NISQ) computers are severely limited in chip size and error rates. We derive localized circuit transformations to efficiently compress quantum circuits for simulation of certain spin Hamiltonians known as free fermions. The proposed numerical circuit compression algorithm behaves backward stable and scales cubically in the number of spins enabling circuit synthesis beyond $mathcalO(103)$ spins.
  arXiv  Detail & Related papers  (2021-08-06T19:38:03Z)
• Quantum computing for classical problems: Variational Quantum Eigensolver for activated processes [0.0]
  This paper reports the development and implementation of a Variational Quantum Eigensolver procedure to solve the Fokker-Planck-Smoluchowski eigenvalue problem. We show that such an algorithm, typically adopted to address quantum chemistry problems, can be applied effectively to classical systems paving the way to new applications of quantum computers.
  arXiv  Detail & Related papers  (2021-07-27T18:16:16Z)
• Preserving quantum correlations and coherence with non-Markovianity [50.591267188664666]
  We demonstrate the usefulness of non-Markovianity for preserving correlations and coherence in quantum systems. For covariant qubit evolutions, we show that non-Markovianity can be used to preserve quantum coherence at all times.
  arXiv  Detail & Related papers  (2021-06-25T11:52:51Z)

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.