How many iterations are needed in Grover’s quantum search for finding one out of M marked items in a database containing N items (for 1 < M < N/2)?
I would have thought we just reduce the size of the search space to M and then calculate the probability? But then does that mean the size of the overall database does not matter here?
R iterations where $(2R+1)\theta\approx\pi/2$ and $\sin\theta=\sqrt{M/N}$
Regarding your question, how do you “just reduce the size of the search space”?
At the cost of over-simplifying:
For the second part of your question, Grover's search helps in marking the M items in the whole database. You're still searching a whole database of N items.
The beauty in this implementation is that when we measure, the probability of finding these M items is higher than all the other non-marked items in the database.
