Revision as of 07:45, 3 March 2020 edit Jaydavidmartin (talk \| contribs) Extended confirmed users 14,760 edits →Overview: wording change ← Previous edit		Revision as of 07:46, 3 March 2020 edit undo Jaydavidmartin (talk \| contribs) Extended confirmed users 14,760 edits m →Quantum query complexity: wording adjustment Next edit →
Line 14: Quantum query complexity is the smallest number of queries to the oracle that are required in order to calculate the function. This makes the quantum query complexity a lower bound on the overall time complexity of a function. 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, ~~(i.e.~~which is a [[linear search]]). ==See also==

Quantum complexity theory: Difference between revisions