Quantum speedup of Monte Carlo methods

By Ashley Montanaro. Proceedings of the Royal Society A, 2015

442 citations recorded by the source corpus.

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 randomized 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.

Subfields: Artificial Intelligence, Spectroscopy, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/ffaed4269534af1c9ef2eb00a36a9010a6bf1c4f

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Spectroscopy

In Statistics and Probability

Citations in the corpus

Option Pricing using Quantum Computers (2019, unknown): “The advantage of pricing options on a quantum computer comes from the Amplitude Estimation (AE) algorithm [21] which provides a quadratic speed-up over classical Monte Carlo simulations [24, 25].”
Amplitude estimation without phase estimation (2019, methodology): “ Carlo integration as an example of the application of our algorithm, as follows. In this section, we ﬁrst review the quantum algorithm to calculate the Monte Carlo integrationby amplitude estimation [15] and then explain the amplitude ampliﬁcation operator used in our algorithm. Next, we present th”
Quantum risk analysis (2018, methodology): “AE can be used to approximate the expected value of a random variable.(19,20) By choosing f(i)= i/(N− 1) we estimate E X N 1 and hence E1⁄2X .”
Quantum computing for finance: Overview and prospects (2018, background): “[10] to estimate its expectation value.”
Continuous-variable quantum neural networks (2018, background): “Sufficiently powerful quantum computers can in principle provide computational speedups for key machine learning algorithms and subroutines such as data fitting [4], principal component analysis [5], Bayesian inference [6, 7], Monte Carlo methods [8], support vector machines [9, 10], Boltzmann machi”