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.
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.
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})$.
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.
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
103 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.
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.