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:2603.28076 · Physical Review A

Adiabatic dressing of quantum enhanced Markov chains

Wen Ting Hsieh, Alev Orfi, Dries Sels

quant-phcond-mat.dis-nnSubmitted Mar 30, 2026• Announced Mar 31, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

Comments
12 pages, 9 figures (3 in main text, 6 in appendix)

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.

Physical Review A•Nov 25, 2024•3 citations

Quantum enhanced Markov chains require fine-tuned quenches

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, however, 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 3-spin model, we identify the regime of optimal spectral gap scaling and link it to the system's eigenstate properties.

arXiv:2408.07881•Aug 15, 2024•0 citations

Bounding speedup of quantum-enhanced Markov chain Monte Carlo

Alev Orfi, Dries Sels

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 [Layden, D. et al. Nature 619, 282-287 (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.

arXiv:2403.03087•Mar 5, 2024•0 citations

Irreversibility Enhances Quantum-Enhanced Markov-Chain Monte Carlo

Kefan Cao, Zidong Cui, Lei Wang +1 more

Detailed balance underlies conventional Markov-chain Monte Carlo (MCMC) algorithms. Yet in classical systems, breaking detailed balance generates irreversible probability currents and can accelerate sampling. Whether irreversibility can similarly enhance quantum MCMC remains an intriguing question. Here we show that irreversibility provides a new route to improving the recent quantum-enhanced MCMC (QEMC), which combines quantum proposals with classical acceptance. By introducing state-dependent proposals that break detailed balance while preserving the target stationary distribution, we develop an irreversible quantum-enhanced Monte Carlo (IQEMC). Guided by Landau-Zener transitions, IQEMC promotes large energy descents from high-energy states while maintaining stable transitions near low-energy states. On spin-glass benchmarks, IQEMC outperforms QEMC without increasing computational complexity and, unlike the annealing baseline, exhibits a spectral gap that increases with system size and annealing speed. These results establish irreversibility as a physically grounded mechanism for enhancing quantum MCMC.

cond-mat.stat-mechCross-listedarXiv:2606.23350•Jun 23, 2026•0 citations

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

Alev Orfi, Dries Sels

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.

Physical Review A•Nov 12, 2024•11 citations

Quantum annealing enhanced Markov-Chain Monte Carlo

Shunta Arai, Tadashi Kadowaki

In this study, we propose quantum annealing-enhanced Markov Chain Monte Carlo (QAEMCMC), where QA is integrated into the MCMC subroutine. QA efficiently explores low-energy configurations and overcomes local minima, enabling the generation of proposal states with a high acceptance probability. We benchmark QAEMCMC for the Sherrington-Kirkpatrick model and demonstrate its superior performance over the classical MCMC method. Our results reveal larger spectral gaps, faster convergence of energy observables, and reduced total variation distance between the empirical and target distributions. QAEMCMC accelerates MCMC and provides an efficient method for complex systems, paving the way for scalable quantum-assisted sampling strategies.

arXiv:2502.08060•Scientific Reports•Jul 1, 2025•6 citations
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.
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.
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, however, 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 3-spin model, we identify the regime of optimal spectral gap scaling and link it to the system's eigenstate properties.
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 [Layden, D. et al. Nature 619, 282-287 (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.
Detailed balance underlies conventional Markov-chain Monte Carlo (MCMC) algorithms. Yet in classical systems, breaking detailed balance generates irreversible probability currents and can accelerate sampling. Whether irreversibility can similarly enhance quantum MCMC remains an intriguing question. Here we show that irreversibility provides a new route to improving the recent quantum-enhanced MCMC (QEMC), which combines quantum proposals with classical acceptance. By introducing state-dependent proposals that break detailed balance while preserving the target stationary distribution, we develop an irreversible quantum-enhanced Monte Carlo (IQEMC). Guided by Landau-Zener transitions, IQEMC promotes large energy descents from high-energy states while maintaining stable transitions near low-energy states. On spin-glass benchmarks, IQEMC outperforms QEMC without increasing computational complexity and, unlike the annealing baseline, exhibits a spectral gap that increases with system size and annealing speed. These results establish irreversibility as a physically grounded mechanism for enhancing quantum MCMC.
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.
In this study, we propose quantum annealing-enhanced Markov Chain Monte Carlo (QAEMCMC), where QA is integrated into the MCMC subroutine. QA efficiently explores low-energy configurations and overcomes local minima, enabling the generation of proposal states with a high acceptance probability. We benchmark QAEMCMC for the Sherrington-Kirkpatrick model and demonstrate its superior performance over the classical MCMC method. Our results reveal larger spectral gaps, faster convergence of energy observables, and reduced total variation distance between the empirical and target distributions. QAEMCMC accelerates MCMC and provides an efficient method for complex systems, paving the way for scalable quantum-assisted sampling strategies.