Quantum complexity theory: Difference between revisions

Revision as of 02:27, 11 October 2018

Revision as of 03:04, 11 January 2019

Line 6:

Two important quantum complexity classes are [[BQP]] and [[QMA]] which are the bounded-error quantum analogues of [[P (complexity)|P]] and [[NP (complexity)|NP]]. One of the main aims of quantum complexity theory is to find out where these classes lie with respect to classical complexity classes such as P, NP, [[PP (complexity)|PP]], [[PSPACE]] and [[List of complexity classes|other complexity classes]].

==Quantum query complexity ==

In the query complexity model, the input is given as an oracle (black box). The algorithm gets information about the input only by querying the oracle. The algorithm starts in some fixed quantum state and the state evolves as it queries the oracle.

Quantum Query Complexity is the smallest number of queries to the oracle that are required in order to calculate the function. Clearly,This makes the 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. ItsThe algorithm's Quantum Query Complexity is <math display="inline">O{\left(\sqrt{N}\right)}</math>, a quadratically improvement over the best possible classical query complexity, (i.e. a [[linear search]]).

== Quantum complexity theorists ==