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:2408.07881

Quantum enhanced Markov chains require fine-tuned quenches

Alev Orfi, Dries Sels

Published Aug 15, 2024• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2408.07881

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

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•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

Quasi-optimal quantum Markov chain spectral gap estimation

Adam Connolly, Steven Herbert, Julien Sorci

This paper proposes a quantum algorithm for Markov chain spectral gap estimation that is quasi-optimal (i.e., optimal up to a polylogarithmic factor) in the number of vertices for all parameters, and additionally quasi-optimal in the reciprocal of the spectral gap itself, if the permitted relative error is above some critical value. In particular, these results constitute an almost quadratic advantage over the best-possible classical algorithm. Our algorithm also improves on the quantum state of the art, and we contend that this is not just theoretically interesting but also potentially practically impactful in real-world applications: knowing a Markov chain's spectral gap can speed-up sampling in Markov chain Monte Carlo. Our approach uses the quantum singular value transformation, and as a result we also develop some theory around block-encoding Markov chain transition matrices, which is potentially of independent interest. In particular, we introduce explicit block-encoding methods for the transition matrices of two algebraically-defined classes of Markov chains.

quant-pharXiv:2601.07601•Jan 13, 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-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•4 citations
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.
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, 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.
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.
This paper proposes a quantum algorithm for Markov chain spectral gap estimation that is quasi-optimal (i.e., optimal up to a polylogarithmic factor) in the number of vertices for all parameters, and additionally quasi-optimal in the reciprocal of the spectral gap itself, if the permitted relative error is above some critical value. In particular, these results constitute an almost quadratic advantage over the best-possible classical algorithm. Our algorithm also improves on the quantum state of the art, and we contend that this is not just theoretically interesting but also potentially practically impactful in real-world applications: knowing a Markov chain's spectral gap can speed-up sampling in Markov chain Monte Carlo. Our approach uses the quantum singular value transformation, and as a result we also develop some theory around block-encoding Markov chain transition matrices, which is potentially of independent interest. In particular, we introduce explicit block-encoding methods for the transition matrices of two algebraically-defined classes of Markov chains.
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 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.