Quantum-enhanced Markov chain Monte Carlo

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 an IBM superconducting quantum processor. The algorithm performs Markov chain Monte Carlo (MCMC), a prominent iterative sampling technique, to sample from the Boltzmann distribution of classical Ising models. Unlike most near-term quantum algorithms, ours provably converges to the correct distribution, despite being hard to simulate classically. Moreover, it is unusually robust to noise, converging in fewer iterations than common classical MCMC alternatives both in simulations and experiments. The polynomial speedup it offers, between cubic and quartic, opens a new path for quantum computers to solve useful—not merely difficult—problems in the near term.