Quantum-enhanced Markov chain Monte Carlo

David Layden (), Guglielmo Mazzola, Ryan V. Mishmash, Mario Motta, Pawel Wocjan, Jin-Sung Kim and Sarah Sheldon
Additional contact information
David Layden: IBM Quantum, Almaden Research Center
Guglielmo Mazzola: IBM Quantum, IBM Research – Zurich
Ryan V. Mishmash: IBM Quantum, Almaden Research Center
Mario Motta: IBM Quantum, Almaden Research Center
Pawel Wocjan: IBM Quantum, Thomas J. Watson Research Center
Jin-Sung Kim: IBM Quantum, Almaden Research Center
Sarah Sheldon: IBM Quantum, Almaden Research Center

Nature, 2023, vol. 619, issue 7969, 282-287

Abstract: Abstract Quantum computers promise to solve certain computational problems much faster than classical computers. However, current quantum processors are limited by their modest size and appreciable error rates. Recent efforts to demonstrate quantum speedups have therefore focused on problems that are both classically hard and naturally suited to current quantum hardware, such as sampling from complicated—although not explicitly useful—probability distributions1–3. Here we introduce and experimentally demonstrate a quantum algorithm that is similarly well suited to current hardware, but which samples from complicated distributions arising in several applications. The algorithm performs Markov chain Monte Carlo (MCMC), a prominent iterative technique4, 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. But like most MCMC algorithms, its convergence rate is difficult to establish theoretically, so we instead analysed it through both experiments and simulations. In experiments, our quantum algorithm converged in fewer iterations than common classical MCMC alternatives, suggesting unusual robustness to noise. In simulations, we observed a polynomial speedup between cubic and quartic over such alternatives. This empirical speedup, should it persist to larger scales, could ease computational bottlenecks posed by this sampling problem in machine learning5, statistical physics6 and optimization7. This algorithm therefore opens a new path for quantum computers to solve useful—not merely difficult—sampling problems.

Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.nature.com/articles/s41586-023-06095-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:nat:nature:v:619:y:2023:i:7969:d:10.1038_s41586-023-06095-4

Ordering information: This journal article can be ordered from
https://www.nature.com/

DOI: 10.1038/s41586-023-06095-4

Access Statistics for this article

Nature is currently edited by Magdalena Skipper

More articles in Nature from Nature
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().