Quantum algorithm: Difference between revisions

Revision as of 21:36, 1 April 2018

Revision as of 12:44, 6 May 2018

Line 148:

{{main article|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 Ω<math>O(''{N''})</math> queries required classically.<ref>

{{Cite arXiv

| last = Grover | first = L. K.

Line 155:

| class = quant-ph

| eprint = quant-ph/9605043

}}</ref> Classically, Ω<math>O(''{N''})</math> queries are required, even if we allow bounded-error probabilistic algorithms.

[[De Broglie–Bohm theory|Bohmian Mechanics]] is a non-local hidden variable interpretation of quantum mechanics. It has been shown that a non-local hidden variable quantum 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 will allow quantum computers 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|date=|website=|archive-url=|archive-date=|dead-url=|access-date=}}</ref>

===Quantum counting===