Quantum counting

Quantum counting answers "how many of the $N=2^n$ basis states satisfy an oracle" without checking each one, by running quantum phase estimation on the Grover iterator $G=-AS_0A^{-1}S_\chi$ built from that oracle.

Why it works. In the 2-dimensional subspace spanned by the uniform superposition of marked ("good") and unmarked ("bad") states, $G$ acts as a rotation by angle $\theta$ where

$$\sin^2\!\left(\frac{\theta}{2}\right) = \frac{M}{N},$$

so $G$ has eigenvalues $e^{\pm i\theta}$ on the two eigenvectors of that rotation. Phase estimation with $t$ counting qubits applied to (controlled powers of) $G$ estimates $\theta$ to $t$-bit precision; the count is recovered as $\tilde M = N\sin^2(\tilde\theta/2)$.

Small worked instance. Take $N=4$ ($n=2$ system qubits) with $M=1$ marked state. Then $\sin^2(\theta/2)=1/4 \Rightarrow \sin(\theta/2)=1/2 \Rightarrow \theta/2=\pi/6 \Rightarrow \theta=\pi/3$. In units of $2\pi$, the phase to be estimated is $\varphi=\theta/2\pi=1/6$. A 3-bit counting register (t=3, giving $1/8$-resolution phase bins) would place the estimate near the bin closest to $1/6\approx 0.167$, i.e. bin $0.125$ or $0.25$ out of $8$ — illustrating why more counting qubits are needed as $M/N$ gets small or precise counts are required.

Complexity. With $t$ counting qubits the circuit uses $O(2^t)$ controlled applications of $G$ (each one Grover-oracle call), giving an estimate of $M$ with additive error $O(N/2^t)$ with high probability — a quadratic improvement in oracle calls over classical sampling-based estimation of $M/N$ to the same precision, matching the standard Grover speedup structure it is built from.