Quantum Approximate Counting

Counting the number of solutions to a combinatorial problem is a distinct and often harder task than finding a single solution. Classical exact counting of solutions to problems like Boolean satisfiability falls in the complexity class #P, which is believed harder than NP. Approximate counting relaxes the requirement to an estimate within a multiplicative factor (1 +/- epsilon), and classical randomized algorithms can do this for many problems using repeated random sampling. The classical query complexity for approximate counting of t solutions out of N items scales as O(sqrt(N/t) / epsilon), drawing from random sampling and making it expensive when t is small or N is large.

Quantum approximate counting uses amplitude estimation, a generalization of Grover’s algorithm, to count solutions quadratically faster. The setup begins with Grover’s oracle for the problem: a unitary that marks solution states by a phase flip. Amplitude estimation applies quantum phase estimation to the Grover iterate (oracle composed with the diffusion operator) to extract the rotation angle theta, from which the number of solutions t follows by the relation t = N sin^2(theta/2). A single run of phase estimation with k ancilla qubits produces an estimate of theta with error O(1/k), translating to an error in t of O(sqrt(t(N-t))/k). The query complexity to achieve epsilon-relative error scales as O(sqrt(N/t) / epsilon), a quadratic speedup over the classical O(N/t) sampling bound.

The accuracy-versus-query trade-off is explicit: more ancilla qubits in phase estimation give a more precise angle estimate and a tighter count, but require deeper circuits. For problems where a rough estimate suffices (factor-of-2 approximation rather than 1% accuracy), the algorithm is shallower and more amenable to near-term hardware. Quantum approximate counting has been analyzed for applications in database search (how many rows match a query condition), combinatorial optimization (how many near-optimal solutions exist), and satisfiability problems (estimating solution density before committing to a search). It also underpins quantum speedups for estimating Monte Carlo integrals, where the integrand evaluation counts as the oracle.

An important distinction separates approximate counting from exact counting. Exact counting of satisfying assignments to a Boolean formula is #P-complete, and no quantum algorithm is known to solve #P-complete problems efficiently; quantum computers are not believed to be able to solve #P-hard problems in polynomial time. Quantum approximate counting provides a speedup only in the query model: the number of oracle calls is reduced quadratically, but each oracle call may itself require a circuit whose depth is polynomial in the problem size. On near-term hardware, depth limitations restrict the oracle complexity that can be queried, and the benefit of approximate counting is most accessible for shallow oracles. Fault-tolerant implementations at large scale remain the setting where the quadratic query savings translates most directly into wall-clock runtime reduction.