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)
Gilles Brassard, Peter Høyer, and Alain Tapp
Speedup Type
Quadratic Speedup
Difficulty
★★★☆☆
Overview
Quantum counting answers the question how many items in a collection satisfy a condition, without listing them. It combines Grover's algorithm with quantum phase estimation to estimate the number M of marked items among N, using a number of queries that is roughly the square root of N, where a classical algorithm would need on the order of N.
Counting is useful on its own, and it also solves a practical problem for Grover's algorithm itself. To search efficiently you need to know roughly how many solutions exist, because the right number of Grover iterations depends on it. Quantum counting provides that estimate.
The problem it solves
Determining how many items in a dataset satisfy a given condition, without checking every item individually.
History and background
Brassard, Høyer, and Tapp introduced quantum counting in 1998 at the International Colloquium on Automata, Languages, and Programming. It built on the earlier work of Boyer, Brassard, Høyer, and Tapp on searching with an unknown number of solutions, and on Kitaev's phase estimation.
The idea was later generalized by the same authors together with Mosca into amplitude estimation, which estimates the probability of success of any quantum process and is the basis of quantum Monte Carlo methods. Because counting is the special case where the process is a Grover search, the two are often treated together.
How it works
Uses the structure of Grover's amplitude amplification combined with phase estimation to extract a count rather than a single answer.
Recall that each Grover iteration rotates the state in a two-dimensional plane by an angle of 2 theta, where the sine squared of theta equals M over N. The Grover operator therefore has eigenvalues e to the plus and minus 2 i theta. If you can measure that rotation angle, you can compute M as N times sine squared of theta.
Quantum phase estimation measures eigenvalue phases. Applying it to the Grover operator, with the equal superposition as the input, produces an estimate of 2 theta with a precision that improves with the number of phase estimation qubits. The initial state is a mixture of the two eigenvectors, so the measurement returns either plus or minus 2 theta, and both give the same value of the sine squared.
With t phase estimation qubits, the estimate of M has an error of about the square root of M times N divided by 2 to the t, plus a smaller term. Choosing t of about half of the logarithm of N gives an error of about the square root of M, using about the square root of N Grover operator applications.
Step by step
- Prepare an n-qubit search register in the equal superposition and a t-qubit counting register in the zero state.
- Apply Hadamard gates to the counting register.
- For each counting qubit j, apply the controlled Grover operator raised to the power 2 to the j to the search register.
- Apply the inverse quantum Fourier transform to the counting register and measure it to get an integer m.
- Convert m to a phase estimate theta equal to pi times m divided by 2 to the t, and compute the estimate M equal to N times the sine squared of theta.
- Optionally repeat and take the median to boost confidence, then use the estimate to choose the number of Grover iterations for a subsequent search.
A worked example
Suppose a database has N = 1,024 entries and an unknown number M of them satisfy the condition. Using t = 8 counting qubits, the algorithm returns an integer m near 2 to the 8 times theta over pi. If the true M is 16, then the sine squared of theta is 16 over 1,024, which gives theta of about 0.125 radians, and the measurement returns an m around 10 or 11. Converting back gives an estimate M near 16 with an error of about 4.
A classical algorithm would sample items at random and count the fraction that are marked. To estimate M to within the square root of M, it would need on the order of N over M times a larger factor of samples. For M much smaller than N, the quantum method is about quadratically better.
Complexity and resources
| Item | Detail |
|---|---|
| Queries for error about the square root of M | O(square root of N) |
| Queries for relative error epsilon | O(1 over epsilon times the square root of N over M) |
| Classical sampling for the same accuracy | O(1 over epsilon squared times N over M) |
| Existence test (is M greater than zero) | O(square root of N), as in Grover |
| Qubits | n for the search plus t for counting |
What hardware it needs
- A fault-tolerant machine, since phase estimation applies the Grover operator exponentially many times in t.
- A reversible oracle that marks the solutions.
- Controlled Grover operators, which require ancillas and deep circuits.
Applications
- Determining how many iterations Grover's algorithm needs before running a search.
- Counting solutions to constraint satisfaction and combinatorial problems.
- Estimating the number of satisfying assignments, related to the complexity class sharp P.
- Providing a building block for Monte Carlo estimation and amplitude estimation.
Limitations and caveats
- The speedup is quadratic, and the cost of error correction can offset it for moderate sizes.
- Exact counting of solutions is not possible in the quantum query model faster than about the square root of N, so it only provides an approximation.
- The oracle may dominate the cost.
Common misconceptions
- Quantum counting does not list the solutions. It estimates how many there are.
- It is not a speedup for exact counting problems that are sharp-P-hard, since quantum computers are not known to solve those efficiently.
How it compares
- Grover search finds one solution, while counting estimates how many exist.
- Amplitude estimation generalizes counting to arbitrary quantum subroutines.
- Classical Monte Carlo sampling needs quadratically more samples for the same precision.
Real-world impact
Useful in cryptanalysis and statistical estimation tasks where the quantity of solutions matters as much as finding one example.
Why it matters
Quantum counting completes the Grover toolkit: you can estimate the number of solutions, then search efficiently, and it demonstrates how phase estimation and amplitude amplification work together.
It also shows the pattern that many quantum algorithms follow: convert a quantity into a rotation angle, then use phase estimation to read the angle with Heisenberg-limited scaling.
Frequently asked questions
What does quantum counting do?
It estimates the number of items that satisfy a condition among N items using about the square root of N queries.
How does it relate to Grover's algorithm?
It applies phase estimation to the Grover operator, whose rotation angle depends on the number of solutions.
Is the count exact?
No. It gives an estimate with an error that shrinks as more counting qubits are used.
Why do we need counting for Grover search?
The optimal number of Grover iterations depends on the number of solutions, so counting tells us when to stop.
How is it related to amplitude estimation?
Counting is the special case of amplitude estimation in which the quantum process is the uniform superposition over all N items.
Keep learning
- Related algorithm: Grover's Algorithm
- Related algorithm: Quantum Amplitude Estimation
- Related algorithm: Quantum Phase Estimation (QPE)
- Related algorithm: Quantum Approximate Counting
This page is written for educational purposes. Complexity statements describe the best known results at the time of review (September 30, 2026), and research in this area moves quickly, so check recent papers before relying on a specific bound.