Quantum Speedup for Nonreversible Markov Chains

• URL: http://arxiv.org/abs/2501.05868v2
• Date: Wed, 03 Sep 2025 11:48:25 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 develops quantum algorithmic techniques to accelerate nonreversible processes.<n>Such an up-to-exponential quantum speedup is likely to have a decisive impact on many applications.
• 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 constructs Markov chain reversibilizations and develops quantum algorithmic techniques to accelerate nonreversible processes. 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

• Quasi-optimal quantum Markov chain spectral gap estimation [0.0]
  This paper proposes a quantum algorithm for Markov chain spectral gap estimation.<n>Knowing a Markov chain's spectral gap can speed-up sampling in Markov chain Monte Carlo.
  arXiv  Detail & Related papers  (2026-01-12T14:50:46Z)
• Quantum Circuits for the Metropolis-Hastings Algorithm [0.0]
  Quantum computers are expected to provide a speedup of Metropolis-Hastings (MH) simulations.<n>We present a quantum walk construction which follows the classical proposal-acceptance logic.<n>We expect the end-to-end quadratic speedup to hold for MH simulations.
  arXiv  Detail & Related papers  (2025-06-13T08:31:33Z)
• Provably Robust Training of Quantum Circuit Classifiers Against Parameter Noise [49.97673761305336]
  Noise remains a major obstacle to achieving reliable quantum algorithms.<n>We present a provably noise-resilient training theory and algorithm to enhance the robustness of parameterized quantum circuit classifiers.
  arXiv  Detail & Related papers  (2025-05-24T02:51:34Z)
• QAMA: Scalable Quantum Annealing Multi-Head Attention Operator for Deep Learning [48.12231190677108]
  Quantum Annealing Multi-Head Attention (QAMA) is proposed, a novel drop-in operator that reformulates attention as an energy-based Hamiltonian optimization problem.<n>In this framework, token interactions are encoded into binary quadratic terms, and quantum annealing is employed to search for low-energy configurations.<n> Empirically, evaluation on both natural language and vision benchmarks shows that, across tasks, accuracy deviates by at most 2.7 points from standard multi-head attention.
  arXiv  Detail & Related papers  (2025-04-15T11:29:09Z)
• 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)
• Quantum algorithms for quantum dynamics: A performance study on the spin-boson model [68.8204255655161]
  Quantum algorithms for quantum dynamics simulations are traditionally based on implementing a Trotter-approximation of the time-evolution operator. variational quantum algorithms have become an indispensable alternative, enabling small-scale simulations on present-day hardware. We show that, despite providing a clear reduction of quantum gate cost, the variational method in its current implementation is unlikely to lead to a quantum advantage.
  arXiv  Detail & Related papers  (2021-08-09T18:00:05Z)
• 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)
• Information Scrambling in Computationally Complex Quantum Circuits [56.22772134614514]
  We experimentally investigate the dynamics of quantum scrambling on a 53-qubit quantum processor. We show that while operator spreading is captured by an efficient classical model, operator entanglement requires exponentially scaled computational resources to simulate.
  arXiv  Detail & Related papers  (2021-01-21T22:18:49Z)

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.