Number of Grover Iterations
Approximately optimal number of Grover iterations to find one of $M$ marked items among $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
- Lov K. Grover (1996). A fast quantum mechanical algorithm for database search. Proc. 28th ACM STOC, pp. 212–219 doi:10.1145/237814.237866
- 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
