Quantum complexity theory: Difference between revisions

Revision as of 06:29, 24 July 2018

Revision as of 02:27, 11 October 2018

Line 11:

Quantum Query Complexity is the smallest number of queries to the oracle that are required in order to calculate the function. Clearly, Quantum Query Complexity is 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. Its Quantum Query Complexity is ''<math display="inline">O''{\left(''\sqrt{N''}\right)}<sup>1/2</supmath>), which isa quadratically betterimprovement thanover the best possible classical query complexity, a [[linear search]].

== Quantum complexity theorists ==

{{Expand list|date=October 2018}}

*[[Scott Aaronson]]

*[[John Watrous (computer scientist)|John Watrous]]

*[[David Cory]]

*[[Richard Cleve]]

*[[John Preskill]]

==See also==

* [[BQP]]

* [[Polynomial hierarchy]] (PH)

*[[Quantum Turing machine]]

==References==