I've been reading about the Grover algorithm for finding elements in an unstructured database by the means of quantum computing, and even done some exercises.

What I don't understand (and can't find anywhere) is what is supposed to happen if the element is NOT present in the database. The oracle would never flip any qubit, and then I don't know what would happen with the inversion about the mean operator. Would the algorithm keep iterating forever?

  • $\begingroup$ Grover's algorithm won't loop forever, because it always performs $O(\sqrt{N})$ iterations. $\endgroup$ – Dmitri Urbanowicz Dec 18 '18 at 13:03
  • $\begingroup$ That's right, I misunderstood the algorithm. $\endgroup$ – Jose Dec 18 '18 at 19:42

The most basic version of Grover's algorithm has a fixed number of iterations and assumes there is one marked item. If there is no marked item instead of one marked item, you will do those iterations but then get a random answer.

As mentioned in the wikipedia article on Grover's algorithm, the algorithm can be extended to work when there are an unknown number of marked items while still running in $O(\sqrt{N})$ time. There's just more details to work out.

| cite | improve this answer | |

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.