Content deleted Content added
→Other types of quantum computational queries: Grover's algorithm is definitely optimal |
→Grover's algorithm: added source for claim |
||
Line 121:
==== Grover's algorithm ====
An example depicting the power of quantum computing is [[Grover's algorithm]] for searching unstructured databases. The algorithm's quantum query complexity is <math display="inline">O{\left(\sqrt{N}\right)}</math>, a quadratic improvement over the best possible classical query complexity <math>O(N)</math>, which is a [[linear search]]. Grover's algorithm is [[Asymptotic optimality|asymptotically optimal]]; in fact, it uses at most a <math>1+o(1)</math> fraction more queries than the best possible algorithm.<ref>{{Cite journal|last=Zalka|first=Christof|date=1999-10-01|title=Grover's quantum searching algorithm is optimal|url=https://link.aps.org/doi/10.1103/PhysRevA.60.2746|journal=Physical Review A|volume=60|issue=4|pages=2746–2751|doi=10.1103/PhysRevA.60.2746}}</ref>
==== Deutsch-Jozsa algorithm ====
| |||