Quantum-enhanced Markov chain Monte Carlo
arXiv:2203.12497 · doi:10.1038/s41586-023-06095-4
Abstract
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.
References in corpus (8)
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Strong quantum computational advantage using a superconducting quantum processor
- Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light
- Quantum Simulations of Classical Annealing Processes
- Focus beyond quadratic speedups for error-corrected quantum advantage
- Speed-up via Quantum Sampling
- Sampling, rates, and reaction currents through reverse stochastic quantization on quantum computers
- Quantum Sampling Algorithms, Phase Transitions, and Computational Complexity
Cited by in corpus (30)
- Challenges of variational quantum optimization with measurement shot noise
- Quantum computing for chemistry and physics applications from a Monte Carlo perspective
- Benchmarking digital quantum simulations above hundreds of qubits using quantum critical dynamics
- Pulse-efficient quantum machine learning
- Quantum computing quantum Monte Carlo with hybrid tensor network for electronic structure calculations
- Variational quantum algorithm for ergotropy estimation in quantum many-body batteries
- Machine-Learning-Assisted Photonic Device Development: A Multiscale Approach from Theory to Characterization
- ON-OFF Neuromorphic ISING Machines using Fowler-Nordheim Annealers
- Quantum-selected configuration interaction with time-evolved state
- Quantum Dynamical Hamiltonian Monte Carlo
- Dissipative variational quantum algorithms for Gibbs state preparation
- QAOA-MC: Markov chain Monte Carlo enhanced by Quantum Alternating Operator Ansatz
- Error suppression by a virtual two-qubit gate
- Accelerating equilibrium spin-glass simulations using quantum annealers via generative deep learning
- From quantum-enhanced to quantum-inspired Monte Carlo
- Quantum computing for genomics: conceptual challenges and practical perspectives
- Connection between single-layer Quantum Approximate Optimization Algorithm interferometry and thermal distributions sampling
- Quantum-enhanced Markov Chain Monte Carlo for systems larger than your Quantum Computer
- Quantum-assisted variational Monte Carlo
- Combinatorial summation of Feynman diagrams: Equation of state of the 2D SU(N) Hubbard model
- Sampling Problems on a Quantum Computer
- Computing Canonical Averages with Quantum and Classical Optimizers: Thermodynamic Reweighting for QUBO Models of Physical Systems
- Atom Cavity Encoding for NP-Complete Problems
- Quantum Computational Insurance and Actuarial Science
- Neural-network-assisted Monte Carlo sampling trained by Quantum Approximate Optimization Algorithm
- Learning the dynamics of Markovian open quantum systems from experimental data
- Quantum Speedups for Multiproposal MCMC
- Quantum Markov chain Monte Carlo method with programmable quantum simulators
- Quantum-assisted tracer dispersion in turbulent shear flow
- Robust Error Accumulation Suppression for Quantum Circuits