Editing Grover's algorithm (section)

==Optimality ==
Grover's algorithm is optimal up to sub-constant factors. That is, any algorithm that accesses the database only by using the operator ''U<sub>ω</sub>'' must apply ''U<sub>ω</sub>'' at least a <math>1-o(1)</math> fraction as many times as Grover's 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|arxiv=quant-ph/9711070|bibcode=1999PhRvA..60.2746Z|s2cid=1542077}}</ref> The extension of Grover's algorithm to ''k'' matching entries, {{pi}}(''N''/''k'')<sup>1/2</sup>/4, is also optimal.<ref name=Boyer /> This result is important in understanding the limits of quantum computation.

If the Grover's search problem was solvable with {{math|log<sup>c</sup>}} ''N'' applications of ''U<sub>ω</sub>'', that would imply that [[NP (complexity class)|NP]] is contained in [[BQP]], by transforming problems in NP into Grover-type search problems. The optimality of Grover's algorithm suggests that quantum computers cannot solve [[NP-completeness|NP-Complete]] problems in polynomial time, and thus NP is not contained in BQP.

It has been shown that a class of non-local [[Hidden-variable theory|hidden variable]] quantum computers could implement a search of an <math>N</math>-item database in at most <math>O(\sqrt[3]{N})</math> steps. This is faster than the <math>O(\sqrt{N})</math> steps taken by Grover's algorithm.<ref>{{Cite web|url=http://www.scottaaronson.com/papers/qchvpra.pdf|title=Quantum Computing and Hidden Variables|last=Aaronson|first=Scott}}</ref>