3
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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”?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.