MilestoneTheory & algorithmsConfirmed

Brassard, Høyer and Tapp combine Grover and Shor to count solutions

May 27, 1998

Gilles Brassard, Peter Høyer and Alain Tapp generalize Grover's search into what they call amplitude amplification, and combine it with ideas from Shor's algorithm to estimate how many solutions a search problem has.

Why it matters

Amplitude amplification and estimation became standard tools, the basis of quadratic quantum speedups for counting, estimation and Monte Carlo methods.

Gilles Brassard · Peter Høyer · Alain Tapp · Université de Montréal

See it on the timeline

Related

• Lov Grover finds a quantum algorithm for faster unstructured search (May 1996)
• Peter Shor shows a quantum computer could factor large numbers quickly (Nov 1994)
• Montanaro gives a quantum speedup for Monte Carlo methods (Apr 27, 2015)