EquationIntermediateEquations

Number of Grover Iterations

Approximately optimal number of Grover iterations to find one of $M$ marked items among $N$.

$$k^{*}=\left\lfloor\frac{\pi}{4\theta}\right\rfloor,\qquad \sin\theta=\sqrt{\frac{M}{N}},\qquad k^{*}\approx\frac{\pi}{4}\sqrt{\frac{N}{M}}\ \ (M\ll N)$$

Symbols

$N$Search space size
$M$Number of marked items
$\theta$Initial angle
$k^{*}$Optimal number of iterations

$N$ is the size of the search space ($2^n$), $M$ is the number of marked items, $\theta$ is half the rotation angle per iteration, and $\lfloor\cdot\rfloor$ is the floor function. The aim is to make $(2k+1)\theta$ as close as possible to $\pi/2$. It applies when $M$ is known; when it is not, the method of Boyer and colleagues with random, increasing iteration counts is used. The final approximation assumes $M\ll N$.

Example

$N=8$, $M=1$: $\theta=\arcsin(0.3536)\approx0.3614$, and $\pi/(4\theta)\approx2.17$, so $k^*=2$. Check: $(2\cdot2+1)\theta\approx1.807$ is close to $\pi/2\approx1.571$. The approximation $\tfrac{\pi}{4}\sqrt8\approx2.22$ gives the same number.

Test your understanding

The quiz needs JavaScript.

Related topics

References

  1. Lov K. Grover (1996). A fast quantum mechanical algorithm for database search. Proc. 28th ACM STOC, pp. 212–219 doi:10.1145/237814.237866
  2. Michel Boyer; Gilles Brassard; Peter Høyer; Alain Tapp (1998). Tight Bounds on Quantum Searching. Fortschritte der Physik 46(4-5):493–505 doi:10.1002/(SICI)1521-3978(199806)46:4/53.0.CO;2-P