On the convergence of Markov chain distribution within quantum walk circuit subspace

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.