Editing Grover's algorithm (section)

=== Multiple matching entries ===
{{Further|Amplitude amplification}}
If, instead of 1 matching entry, there are ''k'' matching entries, the same algorithm works, but the number of iterations must be <math display="inline"> \frac{\pi}{4}{\left( \frac{N}{k} \right)^{1/2}} </math>instead of <math display="inline"> \frac{\pi}{4}{N^{1/2}}.</math>

There are several ways to handle the case if ''k'' is unknown.<ref>{{Cite web|last=Aaronson|first=Scott|date=April 19, 2021|title=Introduction to Quantum Information Science Lecture Notes|url=https://www.scottaaronson.com/qclec.pdf}}</ref> A simple solution performs optimally up to a constant factor: run Grover's algorithm repeatedly for increasingly small values of ''k'', e.g., taking ''k'' = ''N'', ''N''/2, ''N''/4, ..., and so on, taking <math>k = N/2^t</math> for iteration ''t'' until a matching entry is found.

With sufficiently high probability, a marked entry will be found by iteration <math>t = \log_2(N/k) + c</math> for some constant ''c''. Thus, the total number of iterations taken is at most

<math display="block"> \frac{\pi}{4} \Big(1 + \sqrt{2} + \sqrt{4} + \cdots + \sqrt{\frac{N}{k2^c}}\Big) = O\big(\sqrt{N/k}\big). </math>

Another approach if ''k'' is unknown is to derive it via the [[quantum counting algorithm]] prior. 

If <math>k = N/2</math> (or the traditional one marked state Grover's Algorithm if run with <math>N = 2</math>), the algorithm will provide no amplification. If <math>k > N/2</math>, increasing ''k'' will begin to increase the number of iterations necessary to obtain a solution.<ref>Nielsen-Chuang</ref> On the other hand, if <math>k \geq N/2</math>, a classical running of the checking oracle on a single random choice of input will more likely than not give a correct solution.

A version of this algorithm is used in order to solve the [[collision problem]].<ref name=Boyer>{{Citation
| first1=Michel |last1=Boyer
| first2=Gilles |last2=Brassard
| first3=Peter |last3=Høyer
| first4=Alain |last4=Tapp
| title=Tight Bounds on Quantum Searching
| journal=Fortschritte der Physik
| volume=46
| pages=493–506
| year=1998
| issue=4–5
| arxiv=quant-ph/9605034
| bibcode = 1998ForPh..46..493B
| doi=10.1002/3527603093.ch10| isbn=9783527603091
}}</ref><ref>{{Citation
| first=Andris |last=Ambainis
| s2cid=11326499
| title=Quantum search algorithms
| journal=SIGACT News
| volume=35
| number=2
| pages=22–35
| year=2004
| arxiv=quant-ph/0504012
| bibcode = 2005quant.ph..4012A|doi=10.1145/992287.992296}}
</ref>