Quantum Approximate Counting
Estimating the number of solutions to a search problem quadratically faster than classical sampling, without finding them.
The counting problem
Given a search space of size N and an oracle that marks M solutions, approximate counting estimates M without necessarily producing any solution. Classically, estimating the fraction M/N to relative accuracy requires many oracle queries. Quantum approximate counting uses the structure of Grover's algorithm to estimate M with a quadratic reduction in queries.
Counting via rotation angle
Grover's operator rotates the state in a two-dimensional plane by an angle 2*theta per iteration, where sin^2(theta) = M/N. Determining theta therefore determines M. The exact quantum counting algorithm applies phase estimation to the Grover operator to read theta. Approximate counting relaxes this: it estimates theta with limited precision or with shallower circuits, trading accuracy for feasibility.
Approaches
- Phase-estimation counting: full precision, deep circuits.
- Amplitude-estimation-style counting: schedule Grover powers and fit theta from measurement statistics.
- Coarse counting: a few Grover iterations suffice to decide whether M is large or small.
Query complexity
To estimate M to relative error epsilon, quantum counting uses about O((1/epsilon) sqrt(N/M)) oracle queries, versus the classical O((1/epsilon^2)(N/M)). The square-root improvement in N/M mirrors Grover search itself. Knowing M approximately is also useful for tuning Grover: it tells you how many iterations to run to maximize the success probability of actually finding a solution.
Uses
Approximate counting supports database size estimation, model counting for constraint problems, and calibrating Grover search with multiple targets when the number of solutions is unknown. It shares its mathematical core with amplitude estimation: both extract the angle theta that encodes a probability, differing mainly in what that probability represents.