The Metropolis-Hastings algorithm is a cornerstone of Markov Chain Monte Carlo methods, underpinning a wide range of applications in computational physics, Bayesian inference, and machine learning. Quantum variants of Metropolis-Hastings promise accelerated mixing through quantum walks, but their practical realisation remains challenging. In this work, we construct and simulate an explicit circuit level implementation of a quantum Metropolis-Hastings algorithm based on the framework introduced by Claudon \emph{et al.} (arXiv:2506.11576). We present the full quantum workflow required to prepare a stationary distribution, including a number of modifications required to make the algorithm implementable in a realistic quantum circuit model. Our results demonstrate that these modifications are essential to recover the correct stationary behaviour and highlight both the potential and current limitations of quantum Metropolis-Hastings algorithms, which are expected to become practically relevant in the fault tolerant quantum computing regime.
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.
Abstract Markov chain Monte Carlo (MCMC) methods are a family of algorithms designed to approximate probability distributions that are otherwise intractable to sample from directly. However, as the dimensionality and complexity of the target distribution increase, the convergence of these methods can slow considerably, demanding substantial computational resources. In this context, quantum computing emerges as a promising framework to address this limitation, with different quantum circuit constructions serving as quantum MCMC methods. In this work, we present a quantum circuit based on the discrete quantum walk (DQW) algorithm that implements the algorithmic steps of the Metropolis–Hastings method, encoding the target distribution in a position quantum register. The circuit incorporates auxiliary registers to compute and discretize the acceptance probability, and uses controlled operations to modulate the walker’s evolution accordingly. Simulation results show that the marginal probability distribution encoded in the position register converges asymptotically toward the discretized target distribution for both single and multimodal distributions. We further analyze the effect of circuit parameters on convergence behavior and approximation quality, refining the construction by enabling the evaluation of multiple candidate moves per iteration, therefore reducing the number of iterations required for convergence within our implementation. Finally, we provide a qualitative comparison of our approach with related quantum MCMC methods, namely Szegedy’s quantum walk and QAOA, and discuss structural differences as well as the potential incorporation of adaptive proposal techniques within the proposed circuit framework.
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.
The Markov chain Monte Carlo (MCMC) method, especially the Metropolis-Hastings (MH) algorithm, is a widely used technique for sampling from a target probability distribution
P on a state space $\mathrm{\ensuremath{\Omega}}$ and applied to various problems such as estimation of parameters in statistical models in the Bayesian approach. Quantum algorithms for MCMC have been proposed, yielding the quadratic speedup with respect to the spectral gap $\mathrm{\ensuremath{\Delta}}$ compared to classical counterparts. In this paper, we consider the quantum version of the MH algorithm in the case that calculating
P is costly because the log-likelihood
L for a state $x\ensuremath{\in}\mathrm{\ensuremath{\Omega}}$ is obtained via computing the sum of many terms, $\frac{1}{M}{\ensuremath{\sum}}_{i=0}^{M\ensuremath{-}1}\ensuremath{\ell}(i,x)$. We propose calculating
L by quantum Monte Carlo integration and combine it with the existing method called quantum simulated annealing (QSA) to generate the quantum state that encodes
P in amplitudes. We consider not only state generation but also finding a credible interval for a parameter, a common task in Bayesian inference. In the proposed method for credible interval calculation, the number of queries to the quantum circuit to compute $\ensuremath{\ell}$ scales on $\mathrm{\ensuremath{\Delta}}$, the required accuracy $\ensuremath{\epsilon}$, and the standard deviation $\ensuremath{\sigma}$ of $\ensuremath{\ell}$ as $\stackrel{\ifmmode \tilde{}\else \~{}\fi{}}{O}(\ensuremath{\sigma}/{\ensuremath{\epsilon}}^{2}{\mathrm{\ensuremath{\Delta}}}^{3/2})$, in contrast to $\stackrel{\ifmmode \tilde{}\else \~{}\fi{}}{O}(M/\ensuremath{\epsilon}{\mathrm{\ensuremath{\Delta}}}^{1/2})$ for QSA with
L calculated exactly. Therefore, the proposed method is advantageous if $\ensuremath{\sigma}$ scales on
M sublinearly. As one such example, we consider parameter estimation in a gravitational wave experiment, where $\ensuremath{\sigma}=O({M}^{1/2})$.
Integer linear programming (ILP) remains computationally challenging due to its NP-complete nature despite its central role in scheduling, logistics, and design optimization. We introduce a fully quantum Metropolis-Hastings algorithm for ILP that implements a coherent random walk over the discrete feasible region using only reversible quantum circuits, without quantum-RAM assumptions or classical pre/post-processing. Each walk step is a unitary update that prepares coherent candidate moves, evaluates the objective and constraints reversibly -- including a constraint-satisfaction counter to enforce feasibility -- and encodes Metropolis acceptance amplitudes via a low-overhead linearized rule. At the logical level, the construction uses
O(nlog2N) qubits to represent
n integer variables over the interval
[−N,N−1], and the Toffoli-equivalent cost per Metropolis step grows linearly with the total logical qubit count. Using explicit ripple-carry adder constructions, we support linear objectives and mixed equality/inequality constraints. Numerical circuit-level simulations on a broad ensemble of randomly generated instances validate the predicted linear resource scaling and exhibit progressive thermalization toward low-cost feasible solutions under the annealing schedule. Overall, the method provides a coherent, resource-characterized baseline for fully quantum constraint programming and a foundation for incorporating additional quantum speedups in combinatorial optimization.
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.