Revision as of 21:13, 17 December 2019 edit 31.161.140.1 (talk) →Quantum query complexity: corrected improper capitalisation ← Previous edit		Revision as of 04:18, 24 December 2019 edit undo Dougluce (talk \| contribs) 452 edits m English fix. Next edit →
Line 13: 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 ~~quadratically~~quadratic improvement over the best possible classical query complexity (i.e. a [[linear search]]). == Quantum complexity theorists ==

Quantum complexity theory: Difference between revisions