Quantum Counting

Quantum counting is a quantum algorithmic primitive that estimates the number of solutions to a search problem without requiring that the solutions be found or enumerated. It is a direct application of Quantum Phase Estimation applied to the Grover diffusion operator, treating the count of solutions as an eigenvalue problem. The algorithm achieves a quadratic speedup over classical counting methods, requiring O(√N) queries to estimate the number of solutions M to a problem with N candidates. Quantum counting is particularly valuable in optimization and constraint satisfaction, where knowing the density of solutions informs whether a problem is worth solving or whether heuristics should be abandoned. The technique also demonstrates a general principle: that quantum algorithms can extract aggregate statistical properties of solution spaces more efficiently than classical algorithms can extract individual solutions. This principle extends beyond counting to estimating expectation values, spectral densities, and other macroscopic properties of quantum and classical systems.