Counting Solutions

Grover's algorithm searches for one or more marked items but requires you to know $M$ — the number of solutions — in advance so that you can run the right number of iterations. Quantum counting removes that assumption by estimating $M$ directly, using phase estimation on the Grover iterate.

The spectrum of the Grover iterate

Every Grover iteration $G = D \, U_f$ is a rotation by $2\theta$ in the two-dimensional plane spanned by the good and bad states, where

$\sin\theta = \sqrt{\frac{M}{N}}, \qquad N = 2^n.$

Because $G$ is a rotation by exactly $2\theta$ , its eigenvalues are the complex numbers $e^{\pm 2i\theta}$ (Nielsen and Chuang, §6.3). Quantum phase estimation (QPE) can extract $\theta$ from these eigenvalues. Once we have an estimate $\hat\theta$ of $\theta$ , the number of marked items follows from inverting the formula:

$\hat{M} = N \sin^2\!\hat\theta.$

The counting circuit

The full quantum counting algorithm uses two registers:

A phase register of $t$ ancilla qubits prepared in $H^{\otimes t}|0^t\rangle$ . More ancilla qubits give a more accurate estimate of $\theta$ .
A target register of $n$ data qubits initialised to the uniform superposition $H^{\otimes n}|0^n\rangle$ (an approximate eigenstate of $G$ ).

Controlled applications of $G^{2^0}, G^{2^1}, \ldots, G^{2^{t-1}}$ entangle the phase register with the eigenvalue. An inverse QFT on the phase register then concentrates probability on the bitstring nearest to $2^t \cdot (2\theta / 2\pi) = 2^t \theta / \pi$ . Reading that bitstring gives $\hat\theta$ and therefore $\hat{M}$ .

Error analysis

With $t$ ancilla qubits the estimate satisfies $|\hat\theta - \theta| \leq \pi / 2^t$ . The resulting error in $\hat{M}$ is bounded by

$|\hat{M} - M| \leq 2\pi \sqrt{M N} / 2^t + \pi^2 N / 4^t,$

which decreases exponentially as $t$ grows (Nielsen and Chuang, §6.3). For a given absolute precision $\varepsilon$ it suffices to take $t = O\!\left(\log\!\left(\sqrt{N}/\varepsilon\right)\right)$ ancilla qubits.

A worked example

Take $n = 2$ qubits so $N = 4$ , with $M = 1$ marked item. Then

$\theta = \arcsin\!\sqrt{1/4} = \arcsin(1/2) = \pi/6.$

A phase estimation run that perfectly resolves $\theta$ returns $\hat\theta = \pi/6$ . Plugging into the counting formula:

$\hat{M} = 4 \cdot \sin^2(\pi/6) = 4 \cdot (1/2)^2 = 4 \cdot 1/4 = 1.$

The estimate is exact here because $\theta = \pi/6$ is a rational multiple of $\pi$ and can be represented exactly.

Try it

The exercise asks you to implement the counting formula. You are given $N = 4$ and a QPE output $\theta = \pi/6$ — compute and return the estimated number of marked items.

Run your code to see the quantum state.