Content deleted Content added
m Various citation & identifier cleanup, plus AWB genfixes (arxiv version pointless when published) |
Citation bot (talk | contribs) Add: s2cid, bibcode, arxiv, eprint, class. Removed parameters. Some additions/deletions were actually parameter name changes. | You can use this bot yourself. Report bugs here. | Suggested by Headbomb | All pages linked from cached copy of Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox | via #UCB_webform_linked 48/60 |
||
Line 15:
== Overview of complexity classes ==
Some important complexity classes are P, BPP, BQP, PP, and P-Space. To define these we first define a promise problem. A promise problem is a decision problem which has an input assumed to be selected from the set of all possible input strings. A promise problem is a pair <math>A=(A_{yes},A_{no})</math>. <math>A_{yes}</math> is the set of yes instances, <math>A_{no}</math> is the set of no instances, and the intersection of these sets is such that <math>A_{yes}\cap A_{no}=\emptyset</math>. All of the previous complexity classes contain promise problems.<ref name=":27">{{cite arxiv|last=Watrous|first=John|date=2008-04-21|title=Quantum Computational Complexity|
{| class="wikitable"
|+
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|arxiv=quant-ph/9711070|bibcode=1999PhRvA..60.2746Z|s2cid=1542077}}</ref>
==== Deutsch-Jozsa algorithm ====
| |||