Content deleted Content added
Line 142:
{{main|Grover's algorithm}}
Grover's algorithm searches an unstructured database (or an unordered list) with N entries, for a marked entry, using only <math>O(\sqrt{N})</math> queries instead of the Ω(''N'') queries required classically.<ref>
{{Cite arxiv | last = Grover | first = L. K.
|
| title = A fast quantum mechanical algorithm for database search
|
| eprint = quant-ph/9605043
| class = quant-ph▼
}}</ref> Classically, Ω(''N'') queries are required, even if we allow bounded-error probabilistic algorithms.
===Quantum counting===
Quantum counting solves a generalization of the search problem. It solves the problem of counting the number of marked entries in an unordered list, instead of just detecting if one exists. Specifically, it counts the number of marked entries in an <math>N</math>-element list, with error <math>\epsilon</math> making only <math>\Theta\left(\frac{1}{\epsilon} \sqrt{\frac{N}{k}}\right)</math> queries, where <math>k</math> is the number of marked elements in the list.<ref>
{{Cite arxiv |
|last2=Hoyer |first2=P.
|last3=Tapp |first3=A.
| date = 1998
| title = Quantum Counting |
| eprint = quant-ph/9805082
}}</ref><ref>
{{cite arxiv
}}</ref><ref>{{cite arxiv|eprint=quant-ph/0005055|author1=Gilles Brassard|title=Quantum Amplitude Amplification and Estimation|class=quant-ph|year=2000|author2=Peter Hoyer|author3=Michele Mosca|author4=Alain Tapp}}</ref> More precisely, the algorithm outputs an estimate <math>k'</math> for <math>k</math>, the number of marked entries, with the following accuracy: <math>|k-k'| \leq \epsilon k</math>.▼
|last1=Brassard |first1=G.
|last2=Hoyer |first2=P.
|last3=Mosca |first3=M.
|last4=Tapp |first4=A.
|year=2000
|title=Quantum Amplitude Amplification and Estimation
|eprint=quant-ph/0005055
▲
==Algorithms based on quantum walks==
| |||