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

Finding the quantum speedup of the Monte Carlo Markov chain algorithm

Oscar van Bommel Barcia

Published Jan 1, 2026• 0 citations
OpenAlex

Abstract

In this thesis we define and analyze several proposed quantum approaches to sample from the classical Ising and Potts models, comparing them to the classical Metropolis-Hastings algorithm. We conclude that the highest currently achievable reduction in time complexity is a quadratic improvement obtained using M.~Szegedy's quantum random walk, and we detail the steps needed to construct this walk for purpose of the sampling of the classical Ising or Potts model.

Related papers

Quantum speedup of Monte Carlo methods

Ashley Montanaro

Monte Carlo methods use random sampling to estimate numerical quantities which are hard to compute deterministically. One important example is the use in statistical physics of rapidly mixing Markov chains to approximately compute partition functions. In this work, we describe a quantum algorithm which can accelerate Monte Carlo methods in a very general setting. The algorithm estimates the expected output value of an arbitrary randomized or quantum subroutine with bounded variance, achieving a near-quadratic speedup over the best possible classical algorithm. Combining the algorithm with the use of quantum walks gives a quantum speedup of the fastest known classical algorithms with rigorous performance bounds for computing partition functions, which use multiple-stage Markov chain Monte Carlo techniques. The quantum algorithm can also be used to estimate the total variation distance between probability distributions efficiently.

arXiv:1504.06987•Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences•Aug 26, 2015•431 citations

Practical advantage beyond the quadratic speedup limit with fully-quantum walks

Massimiliano Incudini, Guglielmo Mazzola

We introduce a new class of fully-quantum Metropolis walks in which both the proposal and acceptance steps are intrinsically quantum. Unlike standard quantum walks obtained by quantizing classically efficient Markov chains, our algorithm employs Hamiltonian simulation as a quantum-native proposal mechanism, enlarging the class of quantum walks beyond classical counterparts. We target the problem of sampling from the low-temperature Gibbs distribution of classical dense Ising models, within a fixed error in total variation distance. This approach achieves about a cubic polynomial asymptotic advantage over previous quantum-walks, resulting in a total sixth-degree polynomial queries speedup compared to the best classical walk. This shows that speedups beyond the widely assumed quadratic limit are possible within the quantum walk formalism. We perform a complete fault-tolerant compilation of all algorithmic primitives and benchmark against CPU, GPU, and FPGA implementations of the best classical Markov chain. Under identical hardware assumptions, the resulting advantage runtime crossover is reduced from approximately $10^3$ years for conventional quantum walks to less than one day. These results identify fully-quantum Markov chains as a promising route toward practical quantum advantage.

quant-pharXiv:2607.22818•Jul 28, 2026•1 citation

Quantum circuits for the Metropolis–Hastings algorithm

Baptiste Claudon, Pablo Rodenas-Ruiz, Jean‐Philip Piquemal +1 more

Abstract Szegedy’s quantization of a reversible Markov chain provides a quantum walk whose spectral gap is quadratically larger than that of the classical walk. Quantum computers are therefore expected to provide a speedup of Metropolis–Hastings (MH) simulations. Existing generic methods to implement the quantum walk require coherently computing the transition probabilities of the underlying Markov kernel. However, reversible computing methods require a number of qubits that scales with the complexity of the computation. This overhead is undesirable in near-term fault-tolerant quantum computing, where few logical qubits are available. In this work, we present a Szegedy quantum walk construction which follows the classical proposal-acceptance logic, and does not require further reversible computing methods. We also compare this construction with an alternative to Szegedy’s approach which also provides a quadratic gap amplification. Since each step of the quantum walks uses a constant number of proposal and acceptance steps, we expect the end-to-end quadratic speedup to hold for MH Markov Chain Monte-Carlo simulations.

arXiv:2506.11576•Journal of Physics A Mathematical and Theoretical•Jul 14, 2026•9 citations

Efficient Quantum Walk Circuits for Metropolis-Hastings Algorithm

Jessica Lemieux, Bettina Heim, David Poulin +2 more

We present a detailed circuit implementation of Szegedy's quantization of the Metropolis-Hastings walk. This quantum walk is usually defined with respect to an oracle. We find that a direct implementation of this oracle requires costly arithmetic operations. We thus reformulate the quantum walk, circumventing its implementation altogether by closely following the classical Metropolis-Hastings walk. We also present heuristic quantum algorithms that use the quantum walk in the context of discrete optimization problems and numerically study their performances. Our numerical results indicate polynomial quantum speedups in heuristic settings.

arXiv:1910.01659•Quantum•Jun 29, 2020•60 citations

Experimental Realization of the Markov Chain Monte Carlo Algorithm on a Quantum Computer

Baptiste Claudon, Sergi Ramos-Calderer, Jean-Philip Piquemal

Quantum algorithms present a quadratically improved complexity over classical ones for certain sampling tasks. For instance, the Quantum Amplitude Estimation (QAE) algorithm promises to speed up the estimation of the mean of certain functions, given access to the quantum state corresponding to the probability distribution to be sampled from. Classically, samples are often obtained by simulating a Markov chain. In this work, we experimentally use encodings of Markov chains to prepare quantum states and run a quantum Markov Chain Monte Carlo (qMCMC) algorithm on Quantinuum System Model H2 and Quantinuum Helios quantum computers. We first demonstrate that it is possible to obtain accurate results by operating directly on the physical qubits. Crucially, to pave the way toward fault-tolerant execution, we also implement these algorithms using logical qubits protected by the Iceberg Quantum Error Detection (QED) code. By applying multiple rounds of mid-circuit QED during a random walk, we successfully catch and filter out hardware errors. These experiments demonstrate the feasibility of qMCMC on quantum hardware, bringing us closer to realizing quadratic quantum speedups with broad applications ranging from molecular modeling to machine learning and finance.

quant-pharXiv:2603.08395•Mar 10, 2026•1 citation

Quantum walk based search methods and algorithmic applications

Katalin Friedl

This thesis provides an introduction to the quantum walk based search method which is the quantum analogue of the classical Markov chain based search. We develop the basic theory of the Markov chain based search together with its quantisation due to Mario Szegedy[Sz2]. We deeply analyse their relationship, and sketch some of the possible algorithmic applications. The thesis also addresses the question of the implementation, which is largely hidden by the high level description. We show how to implement the quantum walk based search algorithm in the case of the element distinctness problem. We implement the necessary operations using only very basic data structures, mainly arrays. Also while we use a weak and basic computational model we could still significantly reduce the exponent of the polylog terms arising from counting non oracle calls. Another interesting achievement is that we could parallelise the Setup operation reducing its circuit depth form O(N ) to O(polylog(N)). Probably the most important tool we introduced for the implementation is the use of reversible sorting networks, but we introduce some other tricks as well. The optimal quantum query algorithm for the element distinctness problem was first described by Andris Ambainis [Amb3] and provided the basis of the generalised method. In this seminal paper Ambainis also addressed the question of implementation. However that implementation method does not fully cast into the general framework which was introduced later. The operations described by Ambainis use some involved data structures, such as skip lists and hash table. Also it uses a strong computational model for example, a qRAM query has cost only 1. In contrast with Ambainis’s single node implementation method ours uses bipartite style approach fitting the general framework of Szegedy. At first sight it may seem unnecessary since it results in a duplication of a large amount of data stored during the walk steps, but in fact it simplifies the implementation process. On the structure of the thesis: Section 1 covers some background on quantum walks and basic techniques related to the quantum walk based search method. Section 2-5 gives a comprehensive description of the general scheme introduced by Szegedy and derives the main theorems showing the quadratic speed-up compared to the classical case. These Sections roughly follow the structure of Szegedy’s original paper [Sz2], but the proofs are restructured, so that I could state the main theorem in a slightly stronger form with a much improved constant. Section 6 addresses the implementation issues already mentioned. Finally, Section 7 gives a brief overview of the further generalised scheme introduced by Frederic Magniez, Ashwin Nayak, Jeremie Roland and Miklos Santha. Quantum walk based search methods and algorithmic applications 2

•Jan 1, 2014•3 citations
In this thesis we define and analyze several proposed quantum approaches to sample from the classical Ising and Potts models, comparing them to the classical Metropolis-Hastings algorithm. We conclude that the highest currently achievable reduction in time complexity is a quadratic improvement obtained using M.~Szegedy's quantum random walk, and we detail the steps needed to construct this walk for purpose of the sampling of the classical Ising or Potts model.
Monte Carlo methods use random sampling to estimate numerical quantities which are hard to compute deterministically. One important example is the use in statistical physics of rapidly mixing Markov chains to approximately compute partition functions. In this work, we describe a quantum algorithm which can accelerate Monte Carlo methods in a very general setting. The algorithm estimates the expected output value of an arbitrary randomized or quantum subroutine with bounded variance, achieving a near-quadratic speedup over the best possible classical algorithm. Combining the algorithm with the use of quantum walks gives a quantum speedup of the fastest known classical algorithms with rigorous performance bounds for computing partition functions, which use multiple-stage Markov chain Monte Carlo techniques. The quantum algorithm can also be used to estimate the total variation distance between probability distributions efficiently.
We introduce a new class of fully-quantum Metropolis walks in which both the proposal and acceptance steps are intrinsically quantum. Unlike standard quantum walks obtained by quantizing classically efficient Markov chains, our algorithm employs Hamiltonian simulation as a quantum-native proposal mechanism, enlarging the class of quantum walks beyond classical counterparts. We target the problem of sampling from the low-temperature Gibbs distribution of classical dense Ising models, within a fixed error in total variation distance. This approach achieves about a cubic polynomial asymptotic advantage over previous quantum-walks, resulting in a total sixth-degree polynomial queries speedup compared to the best classical walk. This shows that speedups beyond the widely assumed quadratic limit are possible within the quantum walk formalism. We perform a complete fault-tolerant compilation of all algorithmic primitives and benchmark against CPU, GPU, and FPGA implementations of the best classical Markov chain. Under identical hardware assumptions, the resulting advantage runtime crossover is reduced from approximately 10310^3103 years for conventional quantum walks to less than one day. These results identify fully-quantum Markov chains as a promising route toward practical quantum advantage.
Abstract Szegedy’s quantization of a reversible Markov chain provides a quantum walk whose spectral gap is quadratically larger than that of the classical walk. Quantum computers are therefore expected to provide a speedup of Metropolis–Hastings (MH) simulations. Existing generic methods to implement the quantum walk require coherently computing the transition probabilities of the underlying Markov kernel. However, reversible computing methods require a number of qubits that scales with the complexity of the computation. This overhead is undesirable in near-term fault-tolerant quantum computing, where few logical qubits are available. In this work, we present a Szegedy quantum walk construction which follows the classical proposal-acceptance logic, and does not require further reversible computing methods. We also compare this construction with an alternative to Szegedy’s approach which also provides a quadratic gap amplification. Since each step of the quantum walks uses a constant number of proposal and acceptance steps, we expect the end-to-end quadratic speedup to hold for MH Markov Chain Monte-Carlo simulations.
We present a detailed circuit implementation of Szegedy's quantization of the Metropolis-Hastings walk. This quantum walk is usually defined with respect to an oracle. We find that a direct implementation of this oracle requires costly arithmetic operations. We thus reformulate the quantum walk, circumventing its implementation altogether by closely following the classical Metropolis-Hastings walk. We also present heuristic quantum algorithms that use the quantum walk in the context of discrete optimization problems and numerically study their performances. Our numerical results indicate polynomial quantum speedups in heuristic settings.
Quantum algorithms present a quadratically improved complexity over classical ones for certain sampling tasks. For instance, the Quantum Amplitude Estimation (QAE) algorithm promises to speed up the estimation of the mean of certain functions, given access to the quantum state corresponding to the probability distribution to be sampled from. Classically, samples are often obtained by simulating a Markov chain. In this work, we experimentally use encodings of Markov chains to prepare quantum states and run a quantum Markov Chain Monte Carlo (qMCMC) algorithm on Quantinuum System Model H2 and Quantinuum Helios quantum computers. We first demonstrate that it is possible to obtain accurate results by operating directly on the physical qubits. Crucially, to pave the way toward fault-tolerant execution, we also implement these algorithms using logical qubits protected by the Iceberg Quantum Error Detection (QED) code. By applying multiple rounds of mid-circuit QED during a random walk, we successfully catch and filter out hardware errors. These experiments demonstrate the feasibility of qMCMC on quantum hardware, bringing us closer to realizing quadratic quantum speedups with broad applications ranging from molecular modeling to machine learning and finance.
This thesis provides an introduction to the quantum walk based search method which is the quantum analogue of the classical Markov chain based search. We develop the basic theory of the Markov chain based search together with its quantisation due to Mario Szegedy[Sz2]. We deeply analyse their relationship, and sketch some of the possible algorithmic applications. The thesis also addresses the question of the implementation, which is largely hidden by the high level description. We show how to implement the quantum walk based search algorithm in the case of the element distinctness problem. We implement the necessary operations using only very basic data structures, mainly arrays. Also while we use a weak and basic computational model we could still significantly reduce the exponent of the polylog terms arising from counting non oracle calls. Another interesting achievement is that we could parallelise the Setup operation reducing its circuit depth form O(N ) to O(polylog(N)). Probably the most important tool we introduced for the implementation is the use of reversible sorting networks, but we introduce some other tricks as well. The optimal quantum query algorithm for the element distinctness problem was first described by Andris Ambainis [Amb3] and provided the basis of the generalised method. In this seminal paper Ambainis also addressed the question of implementation. However that implementation method does not fully cast into the general framework which was introduced later. The operations described by Ambainis use some involved data structures, such as skip lists and hash table. Also it uses a strong computational model for example, a qRAM query has cost only 1. In contrast with Ambainis’s single node implementation method ours uses bipartite style approach fitting the general framework of Szegedy. At first sight it may seem unnecessary since it results in a duplication of a large amount of data stored during the walk steps, but in fact it simplifies the implementation process. On the structure of the thesis: Section 1 covers some background on quantum walks and basic techniques related to the quantum walk based search method. Section 2-5 gives a comprehensive description of the general scheme introduced by Szegedy and derives the main theorems showing the quadratic speed-up compared to the classical case. These Sections roughly follow the structure of Szegedy’s original paper [Sz2], but the proofs are restructured, so that I could state the main theorem in a slightly stronger form with a much improved constant. Section 6 addresses the implementation issues already mentioned. Finally, Section 7 gives a brief overview of the further generalised scheme introduced by Frederic Magniez, Ashwin Nayak, Jeremie Roland and Miklos Santha. Quantum walk based search methods and algorithmic applications 2