Quantum Counting Algorithm
Combining Grover's operator with phase estimation to count the exact number of marked items in a search space.
The construction
The quantum counting algorithm merges two building blocks: the Grover iteration and quantum phase estimation. The Grover operator G acts as a rotation by angle 2*theta in the plane spanned by the marked and unmarked subspaces, with sin^2(theta) = M/N. Its eigenvalues are exp(+/- 2 i theta). Phase estimation on G extracts theta, from which M = N sin^2(theta) follows.
Circuit
- A counting register of t ancilla qubits, put into uniform superposition.
- The search register, prepared in the uniform superposition over all N states.
- Controlled applications of G^{2^0}, G^{2^1}, ..., G^{2^{t-1}} onto the search register.
- An inverse quantum Fourier transform on the counting register, then measurement to read theta.
Accuracy
With t counting qubits, phase estimation resolves theta to precision about 2^-t, so the estimate of M improves as the register grows. The number of Grover operator applications is about 2^t, and the additive error in M scales as sqrt(M(N-M))/2^t plus a rounding term. To count exactly (when M is an integer and the resolution suffices) enough counting qubits guarantee the correct integer with high probability.
Comparison with classical counting
Classically, estimating M by sampling needs O(N) queries for an exact count and O(N/M / epsilon^2) for a relative-epsilon estimate. Quantum counting achieves comparable relative accuracy with a square-root improvement in the query count, the same quadratic advantage as Grover search. Exact counting of all solutions still requires enough resolution and remains costly when M is unknown and small.
Relation to other routines
Quantum counting is phase estimation applied to the Grover operator, and it is mathematically the same as amplitude estimation where the amplitude is M/N. Its coarse, near-term-friendly relative is approximate counting, which avoids the deep phase-estimation circuit.