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
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
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
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.
Sampling from complicated probability distributions is a hard computational problem arising in many fields, including statistical physics, optimization, and machine learning. Quantum computers have recently been used to sample from complicated distributions that are hard to sample from classically, but which seldom arise in applications. Here we introduce a quantum algorithm to sample from distributions that pose a bottleneck in several applications, which we implement on a superconducting quantum processor. The algorithm performs Markov chain Monte Carlo (MCMC), a popular iterative sampling technique, to sample from the Boltzmann distribution of classical Ising models. In each step, the quantum processor explores the model in superposition to propose a random move, which is then accepted or rejected by a classical computer and returned to the quantum processor, ensuring convergence to the desired Boltzmann distribution. We find that this quantum algorithm converges in fewer iterations than common classical MCMC alternatives on relevant problem instances, both in simulations and experiments. It therefore opens a new path for quantum computers to solve useful--not merely difficult--problems in the near term.
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.
Sampling problems are widely regarded as the task for which quantum computers can most readily provide a quantum advantage. Leveraging this feature, the quantum-enhanced Markov chain Monte Carlo [Layden , Nature 619, 282–287 (2023)] has been proposed recently, where sampling from a quantum computer is used as a proposal distribution and convergence to a target distribution is accelerated. However, guaranteeing convergence to the target distribution typically forces one to impose restrictive symmetry constraints on the quantum circuit, which makes it hard to design good proposal distributions and prevents making full use of the advantage of a quantum computer. We explore a hybrid quantum-classical Markov chain Monte Carlo framework that combines a quantum circuit with a generative neural sampler (GNS). The GNS is trained on quantum samples and acts as a classical surrogate to efficiently emulate quantum outputs, thereby lifting circuit constraints. We apply this method to Boltzmann sampling of spin glasses using proposals trained with a quantum approximate optimization algorithm circuit. This approach outperforms conventional methods, showing a polynomial speedup (over cubic) in spectral gap compared with uniform proposals. Notably, it maintains similar acceleration even without parameter optimization. These results establish the method as a viable sampling-based quantum algorithm for noisy intermediate-scale quantum devices and highlight its potential for solving practical problems with quantum computation.
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.