Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2403.03087 · Physical Review A

Bounding the speedup of the quantum-enhanced Markov-chain Monte Carlo algorithm

Alev Orfi, Dries Sels

Published Nov 12, 2024• 17 citations
arXivHTMLPDF

Abstract

Sampling tasks are a natural class of problems for quantum computers due to the probabilistic nature of the Born rule. Sampling from useful distributions on noisy quantum hardware remains a challenging problem. A recent paper [D. Layden et al., Nature (London) 619, 282 (2023).] proposed a quantum-enhanced Markov-chain Monte Carlo algorithm where moves are generated by a quantum device and accepted or rejected by a classical algorithm. While this procedure is robust to noise and control imperfections, its potential for quantum advantage is unclear. Here 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.

DOI
10.1103/physreva.110.052414

Related papers

Barriers to efficient mixing of quantum-enhanced Markov chains

Alev Orfi, Dries Sels

Quantum-enhanced Markov chain Monte Carlo, an algorithm in which configurations are proposed through a measured quantum quench and accepted or rejected by a classical algorithm, has been proposed as a possible method for robust quantum speedup on imperfect quantum devices. While this procedure is resilient to noise and control imperfections, the potential for quantum advantage is unclear. By upper-bounding the gap of the Markov chain, we identify competing factors that limit the algorithm's performance. One needs the quantum dynamics to efficiently delocalize the system over a range of classical states, but it is also detrimental to introduce too much entropy through the quench. Specifically, we show that in the long-time limit, the gap of the Markov chain is bounded by the inverse participation ratio of the classical states in the eigenstate basis, showing there is no advantage when quenching to an ergodic system. For the paradigmatic Sherrington-Kirkpatrick and three-spin model, we identify the regime of optimal spectral gap scaling and link it to the system's eigenstate properties.

arXiv:2408.07881•Physical Review A•Nov 25, 2024•5 citations

Neural-Network-Assisted Monte Carlo Sampling Trained by Quantum Approximate Optimization Algorithm

Yuichiro Nakano, Ken N. Okada, Keisuke Fujii

Sampling problems are widely regarded as the task for which quantum computers can most readily provide a quantum advantage. Leveraging this feature, the quantum-enhanced Markov chain Monte Carlo [Layden , Nature 619, 282–287 (2023)] has been proposed recently, where sampling from a quantum computer is used as a proposal distribution and convergence to a target distribution is accelerated. However, guaranteeing convergence to the target distribution typically forces one to impose restrictive symmetry constraints on the quantum circuit, which makes it hard to design good proposal distributions and prevents making full use of the advantage of a quantum computer. We explore a hybrid quantum-classical Markov chain Monte Carlo framework that combines a quantum circuit with a generative neural sampler (GNS). The GNS is trained on quantum samples and acts as a classical surrogate to efficiently emulate quantum outputs, thereby lifting circuit constraints. We apply this method to Boltzmann sampling of spin glasses using proposals trained with a quantum approximate optimization algorithm circuit. This approach outperforms conventional methods, showing a polynomial speedup (over cubic) in spectral gap compared with uniform proposals. Notably, it maintains similar acceleration even without parameter optimization. These results establish the method as a viable sampling-based quantum algorithm for noisy intermediate-scale quantum devices and highlight its potential for solving practical problems with quantum computation.

arXiv:2506.01335•PRX Quantum•Jan 6, 2026•6 citations

Quantum-enhanced Markov chain Monte Carlo for systems larger than a quantum computer

Stuart Ferguson, Petros Wallden

Quantum computers theoretically promise computational advantages in many tasks, but it is much less clear how such advantages can be maintained when using existing and near-term hardware that has limitations in the number and quality of its qubits. Layden [] proposed a promising application by introducing a quantum-enhanced Markov chain Monte Carlo (QeMCMC) approach to reduce the thermalization time required when sampling from hard probability distributions. In QeMCMC, the size of the required quantum computer scales linearly with the problem, placing limitations on the sizes of systems that can be considered. In this paper we introduce a framework to coarse grain the algorithm in such a way that the quantum computation can be performed using considerably smaller quantum computers and we term the method the coarse grained quantum-enhanced Markov chain Monte Carlo (CGQeMCMC). Example strategies within this framework are put to the test, with the quantum speedup persisting while using only n simulated qubits where n is the number of qubits required in the original QeMCMC—a quadratic reduction in resources. The coarse graining framework has the potential to be practically applicable in the near term as it requires very few qubits to approach classically intractable problem instances; in this case, only six simulated qubits suffice to gain an advantage compared with standard classical approaches when investigating the magnetization of a 36-spin system. Our method can be easily combined with other classical and quantum techniques and is adaptable to various quantum hardware specifications—in particular those with limited connectivity.

arXiv:2405.04247•Physical Review Research•Mar 3, 2025•10 citations

Speedup via quantum sampling

Paweł Wocjan, Anura Abeyesinghe

The Markov-chain Monte Carlo method is at the heart of efficient approximation schemes for a wide range of problems in combinatorial enumeration and statistical physics. It is therefore very natural and important to determine whether quantum computers can speed up classical mixing processes based on Markov chains. To this end, we present a quantum algorithm, making it possible to prepare a quantum sample---i.e., a coherent version of the stationary distribution of a reversible Markov chain. Our algorithm has a significantly better running time than that of a previous algorithm based on adiabatic-state generation. We also show that our methods provide a greater speedup over a recently proposed method for obtaining the ground states of (classical) Hamiltonians.

arXiv:0804.4259•Physical Review A•Oct 31, 2008•127 citations

Adiabatic dressing of quantum enhanced Markov chains

Wen Ting Hsieh, Alev Orfi, Dries Sels

Quantum-enhanced Markov chain Monte Carlo, a hybrid quantum-classical algorithm in which configurations are proposed by a quantum proposer and accepted or rejected by a classical algorithm, has been introduced as a possible method for robust quantum speedup. Previous work has identified competing factors that limit the algorithm's performance: the quantum dynamics should delocalize the system across a range of classical states to propose configurations beyond the reach of simple classical updates, whereas excessive delocalization produces configurations unlikely to be accepted, slowing the chain's convergence. Here, we show that controlling the degree of delocalization by adiabatically dressing the quench protocol can significantly enhance the Markov gap in paradigmatic spin-glass models.

quant-pharXiv:2603.28076•Physical Review A•Mar 31, 2026•1 citation

Quantum dynamical Hamiltonian Monte Carlo

Owen Lockwood, Peter Weiß, Filip Aronshtein +1 more

One of the open challenges in quantum computing is to find meaningful and practical methods to leverage quantum computation to accelerate classical machine-learning workflows. A ubiquitous problem in machine-learning workflows is sampling from probability distributions that we only have access to via their log probability. To this end, we extend the well-known Hamiltonian Monte Carlo (HMC) method for Markov chain Monte Carlo (MCMC) sampling to leverage quantum computation in a hybrid manner as a proposal function. Our new algorithm, Quantum Dynamical Hamiltonian Monte Carlo (QD-HMC), replaces the classical symplectic integration proposal step with simulations of quantum-coherent continuous-space dynamics on digital or analog quantum computers. We show that QD-HMC maintains key characteristics of HMC, such as maintaining the detailed balanced condition with momentum inversion, while also having the potential for polynomial speedups over its classical counterpart in certain scenarios. As sampling is a core subroutine in many forms of probabilistic inference, and MCMC in continuously parametrized spaces covers a large class of potential applications, this work widens the areas of applicability of quantum devices. Published by the American Physical Society 2024

arXiv:2403.01775•Physical Review Research•Aug 6, 2024•16 citations
Sampling tasks are a natural class of problems for quantum computers due to the probabilistic nature of the Born rule. Sampling from useful distributions on noisy quantum hardware remains a challenging problem. A recent paper [D. Layden et al., Nature (London) 619, 282 (2023).] proposed a quantum-enhanced Markov-chain Monte Carlo algorithm where moves are generated by a quantum device and accepted or rejected by a classical algorithm. While this procedure is robust to noise and control imperfections, its potential for quantum advantage is unclear. Here 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.
Quantum-enhanced Markov chain Monte Carlo, an algorithm in which configurations are proposed through a measured quantum quench and accepted or rejected by a classical algorithm, has been proposed as a possible method for robust quantum speedup on imperfect quantum devices. While this procedure is resilient to noise and control imperfections, the potential for quantum advantage is unclear. By upper-bounding the gap of the Markov chain, we identify competing factors that limit the algorithm's performance. One needs the quantum dynamics to efficiently delocalize the system over a range of classical states, but it is also detrimental to introduce too much entropy through the quench. Specifically, we show that in the long-time limit, the gap of the Markov chain is bounded by the inverse participation ratio of the classical states in the eigenstate basis, showing there is no advantage when quenching to an ergodic system. For the paradigmatic Sherrington-Kirkpatrick and three-spin model, we identify the regime of optimal spectral gap scaling and link it to the system's eigenstate properties.
Sampling problems are widely regarded as the task for which quantum computers can most readily provide a quantum advantage. Leveraging this feature, the quantum-enhanced Markov chain Monte Carlo [Layden , Nature 619, 282–287 (2023)] has been proposed recently, where sampling from a quantum computer is used as a proposal distribution and convergence to a target distribution is accelerated. However, guaranteeing convergence to the target distribution typically forces one to impose restrictive symmetry constraints on the quantum circuit, which makes it hard to design good proposal distributions and prevents making full use of the advantage of a quantum computer. We explore a hybrid quantum-classical Markov chain Monte Carlo framework that combines a quantum circuit with a generative neural sampler (GNS). The GNS is trained on quantum samples and acts as a classical surrogate to efficiently emulate quantum outputs, thereby lifting circuit constraints. We apply this method to Boltzmann sampling of spin glasses using proposals trained with a quantum approximate optimization algorithm circuit. This approach outperforms conventional methods, showing a polynomial speedup (over cubic) in spectral gap compared with uniform proposals. Notably, it maintains similar acceleration even without parameter optimization. These results establish the method as a viable sampling-based quantum algorithm for noisy intermediate-scale quantum devices and highlight its potential for solving practical problems with quantum computation.
Quantum computers theoretically promise computational advantages in many tasks, but it is much less clear how such advantages can be maintained when using existing and near-term hardware that has limitations in the number and quality of its qubits. Layden [] proposed a promising application by introducing a quantum-enhanced Markov chain Monte Carlo (QeMCMC) approach to reduce the thermalization time required when sampling from hard probability distributions. In QeMCMC, the size of the required quantum computer scales linearly with the problem, placing limitations on the sizes of systems that can be considered. In this paper we introduce a framework to coarse grain the algorithm in such a way that the quantum computation can be performed using considerably smaller quantum computers and we term the method the coarse grained quantum-enhanced Markov chain Monte Carlo (CGQeMCMC). Example strategies within this framework are put to the test, with the quantum speedup persisting while using only n simulated qubits where n is the number of qubits required in the original QeMCMC—a quadratic reduction in resources. The coarse graining framework has the potential to be practically applicable in the near term as it requires very few qubits to approach classically intractable problem instances; in this case, only six simulated qubits suffice to gain an advantage compared with standard classical approaches when investigating the magnetization of a 36-spin system. Our method can be easily combined with other classical and quantum techniques and is adaptable to various quantum hardware specifications—in particular those with limited connectivity.
The Markov-chain Monte Carlo method is at the heart of efficient approximation schemes for a wide range of problems in combinatorial enumeration and statistical physics. It is therefore very natural and important to determine whether quantum computers can speed up classical mixing processes based on Markov chains. To this end, we present a quantum algorithm, making it possible to prepare a quantum sample---i.e., a coherent version of the stationary distribution of a reversible Markov chain. Our algorithm has a significantly better running time than that of a previous algorithm based on adiabatic-state generation. We also show that our methods provide a greater speedup over a recently proposed method for obtaining the ground states of (classical) Hamiltonians.
Quantum-enhanced Markov chain Monte Carlo, a hybrid quantum-classical algorithm in which configurations are proposed by a quantum proposer and accepted or rejected by a classical algorithm, has been introduced as a possible method for robust quantum speedup. Previous work has identified competing factors that limit the algorithm's performance: the quantum dynamics should delocalize the system across a range of classical states to propose configurations beyond the reach of simple classical updates, whereas excessive delocalization produces configurations unlikely to be accepted, slowing the chain's convergence. Here, we show that controlling the degree of delocalization by adiabatically dressing the quench protocol can significantly enhance the Markov gap in paradigmatic spin-glass models.
One of the open challenges in quantum computing is to find meaningful and practical methods to leverage quantum computation to accelerate classical machine-learning workflows. A ubiquitous problem in machine-learning workflows is sampling from probability distributions that we only have access to via their log probability. To this end, we extend the well-known Hamiltonian Monte Carlo (HMC) method for Markov chain Monte Carlo (MCMC) sampling to leverage quantum computation in a hybrid manner as a proposal function. Our new algorithm, Quantum Dynamical Hamiltonian Monte Carlo (QD-HMC), replaces the classical symplectic integration proposal step with simulations of quantum-coherent continuous-space dynamics on digital or analog quantum computers. We show that QD-HMC maintains key characteristics of HMC, such as maintaining the detailed balanced condition with momentum inversion, while also having the potential for polynomial speedups over its classical counterpart in certain scenarios. As sampling is a core subroutine in many forms of probabilistic inference, and MCMC in continuously parametrized spaces covers a large class of potential applications, this work widens the areas of applicability of quantum devices. Published by the American Physical Society 2024