Sampling from complicated probability distributions is a classically difficult computational problem. Recent research has employed quantum computers to sample from distributions that are complicated, but these distributions are typically not explicitly useful and seldom arise in applications.
In the new paper Quantum-enhanced Markov Chain Monte Carlo, researchers from IBM Quantum introduce and experimentally demonstrate a quantum-enhanced Markov Chain Monte Carlo (MCMC) algorithm that is well-suited to current superconducting quantum processors for sampling from distributions that can be both complicated and useful. The team uses the algorithm to perform MCMC sampling on the Boltzmann distribution of classical Ising models.
A classical Ising model consists of several variables called spins, and its coefficients comprise couplings and fields. An Isling model instance is often represented as a graph, with each spin configuration assigned an energy and a corresponding Boltzmann probability where the partition function ensures normalization.
Sampling from Boltzmann probability is a common subroutine in many disparate applications: 1) In statistical physics, it is used to compute thermal averages; 2) In machine learning, to train Boltzmann machines; and 3) In combinatorial optimization, as part of the popular simulated annealing algorithm.
A problem with sampling from Boltzmann probability is that when couplings and fields have varying signs and follow no particular pattern and temperature tends to zero, such sampling amounts to minimizing spin configuration with assigned energy. This becomes an NP-hard problem for spin glasses, which cannot be solved by classical methods such as MCMC, a leading algorithmic technique for sampling from the Boltzmann distribution of Ising models.
To address this issue, the team introduces an MCMC algorithm that leverages a quantum computer to propose moves and a classical computer to accept/reject them in the sampling process. The approach thus alternates between two steps: quantum proposal and classical accept/reject.
The team selected the quantum step of their algorithm heuristically to accelerate MCMC convergence in spin glasses at low temperatures, then evaluated the resulting Markov chains through simulations and experiments. The results show that the resulting Markov chains are guaranteed to converge to the desired Boltzmann distribution, even though they may not be possible to efficiently simulate classically. Moreover, the researchers note that the proposed algorithm uses relatively simple and shallow quantum circuits, enabling a quantum speedup on current hardware despite any experimental imperfections.
The team believes the promising results demonstrate that their proposed algorithm can open a new research path that will enable quantum computers to solve useful — not merely difficult — problems in the near term.
The paper Quantum-enhanced Markov Chain Monte Carlo is on arXiv.
Author: Hecate He | Editor: Michael Sarazen
We know you don’t want to miss any news or research breakthroughs. Subscribe to our popular newsletter Synced Global AI Weekly to get weekly AI updates.
0 comments on “IBM’s Quantum-Enhanced Markov Chain Monte Carlo Algorithm Facilitates Complicated Probability Distribution Sampling”