Quantum speedup of Monte Carlo methods

Research output: Contribution to journalArticle (Academic Journal)peer-review

43 Citations (Scopus)
219 Downloads (Pure)

Abstract

Monte Carlo methods use random sampling to estimate numerical quantities which are hard to compute deterministically. One important example is the use in statistical physics of rapidly mixing Markov chains to approximately compute partition functions. In this work we describe a quantum algorithm which can accelerate Monte Carlo methods in a very general setting. The algorithm estimates the expected output value of an arbitrary randomised or quantum subroutine with bounded variance, achieving a near-quadratic speedup over the best possible classical algorithm. Combining the algorithm with the use of quantum walks gives a quantum speedup of the fastest known classical algorithms with rigorous performance bounds for computing partition functions, which use multiple-stage Markov chain Monte Carlo techniques. The quantum algorithm can also be used to estimate the total variation distance between probability distributions efficiently.
Original languageEnglish
Article number20150301
Number of pages20
JournalProceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences
Volume471
Issue number2181
Early online date19 Aug 2015
DOIs
Publication statusPublished - 8 Sep 2015

Bibliographical note

Accepted: 21 July 2015

Keywords

  • Monte Carlo methods
  • quantum algorithms
  • partition functions

Fingerprint

Dive into the research topics of 'Quantum speedup of Monte Carlo methods'. Together they form a unique fingerprint.

Cite this