Quantum Algorithms Database
Quantum Counting
Estimates the number of solutions to a search problem, combining Grover's Algorithm with quantum phase estimation.
Year
1998
Inventor(s)
Brassard, Høyer & Tapp
Speedup Type
Quadratic Speedup
Difficulty
★★★☆☆
The Problem
Determining how many items in a dataset satisfy a given condition, without checking every item individually.
How It Works
Uses the structure of Grover's amplitude amplification combined with phase estimation to extract a count rather than a single answer.
Real-World Impact
Useful in cryptanalysis and statistical estimation tasks where the quantity of solutions matters as much as finding one example.