MilestoneTheory & algorithmsConfirmed

Montanaro gives a quantum speedup for Monte Carlo methods

Apr 27, 2015

Ashley Montanaro describes a quantum algorithm that estimates the average output of a random process, the core of Monte Carlo methods, with a nearly quadratic speedup over the best possible classical algorithm.

Why it matters

Monte Carlo methods are used widely in finance and physics, so this is a much-studied candidate use, though error-correction costs may eat up a quadratic speedup on early machines.

Ashley Montanaro · Bristol

See it on the timeline

Related

• Brassard, Høyer and Tapp combine Grover and Shor to count solutions (May 27, 1998)
• Lov Grover finds a quantum algorithm for faster unstructured search (May 1996)
• Error-correction costs challenge early gains from quadratic quantum speedups (Nov 9, 2020)