Quantum amplitude estimation and Monte Carlo

Short answer: Quantum amplitude estimation (QAE) is a quantum algorithm that the research literature says can reduce the number of samples needed for Monte Carlo style estimation, with a near-quadratic improvement over classical sampling in the number of uses of the underlying procedure. A 2015 paper in Proceedings of the Royal Society A, by Ashley Montanaro, extends this to arbitrary subroutines with bounded variance. A later paper describes Iterative QAE, a variant that avoids quantum phase estimation. These are query-complexity results, not hardware results.

The classical baseline

Monte Carlo methods use random sampling to estimate numerical quantities that are hard to compute deterministically, according to the Proceedings A abstract. It gives as an important example the use in statistical physics of rapidly mixing Markov chains to approximately compute partition functions. A paper on Iterative QAE in npj Quantum Information says the estimation error bound of classical Monte Carlo simulation scales as one over the square root of M, where M is the number of classical samples, while QAE achieves a scaling of one over M for M quantum samples. It describes this as a quadratic speedup.

Montanaro's result

The Proceedings A paper describes a quantum algorithm that 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. In the text, the author assumes the variance of the subroutine output is at most sigma squared and presents an algorithm that estimates the mean up to additive error epsilon, with 99 percent success probability, using the subroutine about sigma over epsilon times, up to polylogarithmic factors. The paper says known lower bounds on the quantum complexity of approximating the mean imply this is optimal up to polylogarithmic factors.

The author stresses that the result holds for an arbitrary algorithm used as a black box, given only an upper bound on the variance, and that the subroutine need not be a classical randomized procedure but can itself be a quantum algorithm.

Applications named in the papers

The abstract says that combining the algorithm with quantum walks gives a speedup over the fastest known classical algorithms, with rigorous performance bounds, for computing partition functions using multiple-stage Markov chain Monte Carlo techniques. It says the algorithm can also estimate the total variation distance between probability distributions efficiently.

The npj Quantum Information paper says QAE has the potential to achieve a quadratic speedup for many applications classically solved through Monte Carlo simulation, and that it has been shown that QAE can be leveraged in the financial services sector, for example for risk analysis or option pricing, and for generic tasks such as numerical integration. The word potential matters there: the paper does not claim that a financial application has been run at advantage scale.

Iterative QAE

The npj paper introduces Iterative QAE (IQAE), a variant that does not rely on quantum phase estimation but is based only on Grover's algorithm, which it says reduces the required number of qubits and gates. The authors say they prove it achieves a quadratic speedup up to a double-logarithmic factor compared to classical Monte Carlo simulation, with provably small constant overhead. They also report an empirical study in which their algorithm outperformed other known QAE variants without phase estimation, some by orders of magnitude in the number of samples needed for the same accuracy and confidence level.

What this does not tell you

This article summarises abstracts and introductions of two papers and a textbook chapter. The speedups are stated in terms of how many times a subroutine is called. They say nothing about the cost of building that subroutine on hardware, and no source here reports a practical advantage on a real device.

FAQ

What does QAE speed up?

Estimating an expected value, as in Monte Carlo methods. The npj paper says error scales as one over M for M quantum samples, against one over the square root of M classically.

Does it need a classical subroutine?

No. The 2015 paper says the subroutine can itself be a quantum algorithm, used as a black box with a known variance bound.

What is Iterative QAE?

A variant that avoids quantum phase estimation and uses only Grover's algorithm, with fewer qubits and gates, according to its authors.

Is it used in finance today?

The paper says QAE has the potential for risk analysis and option pricing. It does not report a deployment.

Is the speedup proven?

The papers describe proven complexity bounds for query counts. Practical advantage on hardware is not claimed.