Academy K

Optimal Number of Grover Iterations

InterviewDerivationGrover's algorithmquantum speedup

Related module: Search and amplitude amplification

Problem statement

In Grover's algorithm searching for one marked item among NN items, the success probability after kk iterations is approximately sin⁡2((2k+1)θ)\sin^2((2k+1)\theta) where sin⁡θ=1/N\sin\theta = 1/\sqrt{N}.

  1. For large NN, what is the optimal number of iterations k∗k^*?
  2. What is the quantum speedup compared to classical search?
  3. Why does the probability decrease if you iterate too many times?

Practise this problem

Verify you understand it—not just that you read the answer.

Learn the foundations

The Quantum Computing track covers this topic and more in depth.