Multiproposal Markov chain Monte Carlo (MCMC) algorithms choose from multiple proposals to generate their next chain step in order to sample from challenging target distributions more efficiently. However, on classical machines, these algorithms require O(P) target evaluations for each Markov chain step when choosing from P proposals. Recent work demonstrates the possibility of quadratic quantum speedups for one such multiproposal MCMC algorithm. After generating P proposals, this quantum parallel MCMC (QPMCMC) algorithm requires only O( P) target evaluations at each step, outperforming its classical counterpart. However, generating P proposals using classical computers still requires O(P) time complexity, resulting in the overall complexity of QPMCMC remaining O(P). Here, we present a new, faster quantum multiproposal MCMC strategy, QPMCMC2. With a specially designed Tjelmeland distribution that generates proposals close to the input state, QPMCMC2 requires only O(1) target evaluations and O(logP) qubits when computing over a large number of proposals P. Unlike its slower predecessor, the QPMCMC2 Markov kernel (1) maintains detailed balance exactly and (2) is fully explicit for a large class of graphical models. We demonstrate this flexibility by applying QPMCMC2 to novel Ising-type models built on bacterial evolutionary networks and obtain significant speedups for Bayesian ancestral trait reconstruction for 248 observed salmonella bacteria.
Quantum computation is expected to accelerate certain computational tasks over classical counterparts. Its most primitive advantage is its ability to sample from classically intractable probability distributions. A promising approach to make use of this fact is the so-called quantum-enhanced Markov-chain Monte Carlo (qe-MCMC) method [D. Layden , ], which uses outputs from quantum circuits as the proposal distributions. In this paper, we propose the use of a quantum alternating operator ansatz (QAOA) for qe-MCMC and provide a strategy to optimize its parameters to improve convergence speed while keeping its depth shallow. The proposed QAOA-type circuit is designed to satisfy the specific constraint which qe-MCMC requires with arbitrary parameters. Through our extensive numerical analysis, we find a correlation in a certain parameter range between an experimentally measurable value, acceptance rate of MCMC, and the spectral gap of the MCMC transition matrix, which determines the convergence speed. This allows us to optimize the parameter in the QAOA circuit and achieve quadratic speedup in convergence. Since MCMC is used in various areas such as statistical physics and machine learning, this paper represents an important step toward realizing practical quantum advantage with currently available quantum computers through qe-MCMC. Published by the American Physical Society 2024
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.
In this study, we propose quantum annealing-enhanced Markov Chain Monte Carlo (QAEMCMC), where QA is integrated into the MCMC subroutine. QA efficiently explores low-energy configurations and overcomes local minima, enabling the generation of proposal states with a high acceptance probability. We benchmark QAEMCMC for the Sherrington-Kirkpatrick model and demonstrate its superior performance over the classical MCMC method. Our results reveal larger spectral gaps, faster convergence of energy observables, and reduced total variation distance between the empirical and target distributions. QAEMCMC accelerates MCMC and provides an efficient method for complex systems, paving the way for scalable quantum-assisted sampling strategies.
One of the open challenges in quantum computing is to find meaningful and practical methods to leverage quantum computation to accelerate classical machine-learning workflows. A ubiquitous problem in machine-learning workflows is sampling from probability distributions that we only have access to via their log probability. To this end, we extend the well-known Hamiltonian Monte Carlo (HMC) method for Markov chain Monte Carlo (MCMC) sampling to leverage quantum computation in a hybrid manner as a proposal function. Our new algorithm, Quantum Dynamical Hamiltonian Monte Carlo (QD-HMC), replaces the classical symplectic integration proposal step with simulations of quantum-coherent continuous-space dynamics on digital or analog quantum computers. We show that QD-HMC maintains key characteristics of HMC, such as maintaining the detailed balanced condition with momentum inversion, while also having the potential for polynomial speedups over its classical counterpart in certain scenarios. As sampling is a core subroutine in many forms of probabilistic inference, and MCMC in continuously parametrized spaces covers a large class of potential applications, this work widens the areas of applicability of quantum devices. Published by the American Physical Society 2024
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})$.