Content deleted Content added
m →Grover's algorithm: Task 16: replaced (0×) / removed (1×) deprecated |dead-url= and |deadurl= with |url-status=; |
→Grover's algorithm: Clarified statement as not redundant with respect to previous sentence. Tags: Mobile edit Mobile app edit Android app edit |
||
Line 122:
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 <math>O({N})</math> queries required classically.<ref>
{{Cite arXiv|eprint=quant-ph/9605043|first=Lov K.|last=Grover|author-link=Lov Grover|title=A fast quantum mechanical algorithm for database search|date=1996}}</ref> Classically, <math>O({N})</math> queries are required
Theorists have considered a hypothetical generalization of a standard quantum computer that could access the histories of the hidden variables in [[De Broglie–Bohm theory|Bohmian mechanics]]. (Such a computer is completely hypothetical and would ''not'' be a standard quantum computer, or even possible under the standard theory of quantum mechanics.) Such a hypothetical computer could implement a search of an N-item database at most in <math>O(\sqrt[3]{N})</math> steps. This is slightly faster than the <math>O(\sqrt{N})</math> steps taken by [[Grover's algorithm]]. Neither search method would either model of quantum computer to solve [[NP-completeness|NP-complete]] problems in polynomial time.<ref>{{Cite web|url=https://www.scottaaronson.com/papers/qchvpra.pdf|title=Quantum Computing and Hidden Variables|last=Aaronson|first=Scott}}</ref>
| |||