<p>When <span class="math-container">$M=N/2$</span>, you don't need a quantum algorithm; a classical algorithm can find a matching entry in <span class="math-container">$O(1)$</span> 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.</p>

CC BY-SA 4.0
2019-06-27T19:46:03.267Z
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?
Gary McGuire
CC BY-SA 4.0
2019-06-28T08:13:39.467Z
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.
smapers
CC BY-SA 4.0
2019-06-28T11:52:33.560Z
Thank you. Interestingly the probability of success goes up and down as the number of iterations increases, according to this paper https://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.
Gary McGuire
CC BY-SA 4.0
2019-06-27T16:23:39.670Z
2019-06-27T16:23:39.670Z
D.W.
<p>The more general version of Grover's algorithm searches for one of <span class="math-container">$M$</span> entries that match a criterion, out of <span class="math-container">$N$</span> total entries.</p>

<p>I have seen it written that this takes <span class="math-container">$O(\sqrt{N/M})$</span> iterations, to find one of the <span class="math-container">$M$</span> matching entries, with good probability.
(e.g. on <a href="https://en.wikipedia.org/wiki/Grover%27s_algorithm#Extension_to_space_with_multiple_targets" rel="nofollow noreferrer">wikipedia</a> )</p>

<p>Is this still valid when <span class="math-container">$M$</span> is large, say <span class="math-container">$M=N/2$</span> ?  In that case we get <span class="math-container">$O(1)$</span> iterations? </p>

<quantum-computing>
Grover's algorithm, M out of N, when M is large
Gary McGuire
# Grover's algorithm, M out of N, when M is large

(Asked by: username_0 on 2019-06-27)

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](https://en.wikipedia.org/wiki/Grover%27s_algorithm#Extension_to_space_with_multiple_targets) )

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

**Tags:** quantum-computing


---

## 1 answers

### Answer by username_1 on 2019-06-27. Score: 4

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.

> **Comments:**
> **username_0**: Thank you very much username_1 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?  
> **username_2**: 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.  
> **username_0**: Thank you. Interestingly the probability of success goes up and down as the number of iterations increases, according to this paper https://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.  

---

