Quantum counting algorithm

The quantum counting algorithm is a quantum algorithm for efficiently counting the number of solutions to a given search problem. It is based on the quantum phase estimation algorithm and on Grover's search algorithm, and it was devised by Gilles Brassard, Peter Høyer and Alain Tapp in 1998. Counting problems arise in statistical estimation, statistical physics and networking, and in quantum computing the ability to count solutions is needed to run Grover's search, which requires knowing how many solutions exist. The algorithm prepares two registers in superposition, builds the Grover operator on the space of all bit strings, and then applies controlled Grover operations followed by an inverse quantum Fourier transform to estimate the number of solutions. Without prior knowledge of the solution set, a classical deterministic count cannot do better than inspecting all N elements. The existence problem, deciding whether any solution exists, is a special case.