0
$\begingroup$

The more general version of Grover's algorithm searches for one of $M$ entries that match a criterion, out of $N$ total entries.

I have seen it written that this takes $O(\sqrt{N/M})$ iterations, to find one of the $M$ matching entries, with good probability. (e.g. on wikipedia )

Is this still valid when $M$ is large, say $M=N/2$ ? In that case we get $O(1)$ iterations?

Improve this question
$\endgroup$
4
$\begingroup$

When $M=N/2$, you don't need a quantum algorithm; a classical algorithm can find a matching entry in $O(1)$ iterations on average (expected running time), just by randomly guessing an item and checking if it matches. Grover's algorithm is also randomized, so the quantum computer offers no advantage in asymptotic running time for that case.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you very much D.W. for answering. Is the probability the same in both cases? If we randomly guess an item then classically the probability is 0.5 of getting a match. What is the probability of Grover's algorithm giving a match? $\endgroup$ – Gary McGuire Jun 27 '19 at 19:46
  • $\begingroup$ Grover's algorithm would also give a 0.5 success probability, see e.g. Theorem 2 of [1]. Here it is proven that if the initial success probability is $a$, then amplitude amplification (which is just a more general form of Grover's algorithm) yields a success probability of $\max\{a,1-a\}$. [1] Brassard, Gilles, et al. "Quantum amplitude amplification and estimation." Contemporary Mathematics 305 (2002): 53-74. $\endgroup$ – smapers Jun 28 '19 at 8:13
  • 1
    $\begingroup$ Thank you. Interestingly the probability of success goes up and down as the number of iterations increases, according to this paper arxiv.org/pdf/quant-ph/9605034v1.pdf . In section 3.1 they discuss the case $M=N/4$ where Grover's algorithm succeeds after one iteration with probability 1. $\endgroup$ – Gary McGuire Jun 28 '19 at 11:52

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.