Optimal Number of Iterations

Running Grover's algorithm for exactly the right number of iterations is critical. Too few and the marked state is not yet fully amplified; too many and the state over-rotates past the target — the success probability falls again. This lesson derives and lets you compute the sweet spot.

Geometry of Grover iterations

Start with the $N$ -item uniform superposition $|s\rangle$ . Split the Hilbert space into two directions:

|W\rangle = \frac{1}{\sqrt{N - M}} \sum_{\text{unmarked}} |x\rangle, \qquad |T\rangle = \frac{1}{\sqrt{M}} \sum_{\text{marked}} |x\rangle,

so $|s\rangle = \cos\theta\,|W\rangle + \sin\theta\,|T\rangle$ with

\sin\theta = \sqrt{\frac{M}{N}}.

Each Grover iteration is a rotation by $2\theta$ in this plane. After $t$ iterations the state is $\cos\bigl((2t+1)\theta\bigr)|W\rangle + \sin\bigl((2t+1)\theta\bigr)|T\rangle$ . The success probability is $\sin^2\bigl((2t+1)\theta\bigr)$ , which is maximised when $(2t+1)\theta \approx \pi/2$ , i.e.

t \approx \frac{\pi/2 - \theta}{2\theta} \approx \frac{\pi}{4\theta}.

For $M \ll N$ we have $\theta \approx \sin\theta = \sqrt{M/N}$ , giving

\boxed{t^* = \left\lfloor \frac{\pi}{4}\sqrt{\frac{N}{M}} \right\rfloor.}

This is the origin of Grover's $O(\sqrt{N})$ query complexity: the optimal iteration count grows as $\sqrt{N}$ rather than $N$ as in classical linear search.

Worked example: $N = 16$ , $M = 1$

With four qubits ( $N = 16$ ) and one marked item:

\theta = \arcsin\!\left(\sqrt{\frac{1}{16}}\right) = \arcsin(0.25) \approx 0.2527 \text{ rad}.

The exact maximizer of $\sin^2\!\bigl((2t+1)\theta\bigr)$ over integer $t$ is the integer nearest to $\tfrac{1}{2}\!\left(\tfrac{\pi}{2\theta} - 1\right)$ :

\frac{\pi/2 - \theta}{2\theta} = \frac{1.3181}{0.5054} = 2.608,

so the two candidate integers are $t = 2$ and $t = 3$ . Because $t = 3$ places the angle $(2\cdot3+1)\theta \approx 1.769$ closer to $\pi/2$ than $t = 2$ does ( $(2\cdot2+1)\theta \approx 1.263$ ), we get higher success probability at $t = 3$ ( $\approx 96.1\%$ ) than at $t = 2$ ( $\approx 90.8\%$ ).

The small-angle approximation formula reaches the same conclusion directly:

t^* = \left\lfloor \frac{\pi}{4}\sqrt{16} \right\rfloor = \left\lfloor \frac{\pi}{4} \cdot 4 \right\rfloor = \lfloor 3.1415\ldots \rfloor = 3.

For $M \ll N$ the approximation $\sin\theta \approx \theta$ is excellent, and the floor ensures we never over-rotate past the target. The answer for $N = 16$ , $M = 1$ is $t^* = 3$ .

Try it

Implement the formula in JavaScript and return the floor value for $N = 16$ , $M = 1$ . The grader checks that you return exactly 3 (the approximation result).

Run your code to see the quantum state.

Geometry of Grover iterations

Worked example: N=16N = 16N=16, M=1M = 1M=1

Try it

Worked example: $N = 16$ , $M = 1$