Quantum complexity theory: Difference between revisions

Revision as of 05:42, 18 February 2016

Revision as of 20:56, 1 April 2016

Line 1:

'''Quantum complexity theory''' is a part of [[computational complexity theory]] in [[theoretical computer science]]. It studies [[complexity classes]] defined using [[quantum computers]] and [[quantum information]] which are [[computational model]]s based on [[quantum mechanics]]. It studies the hardness of problems in relation to these complexity classes, and the relationship between quantum complexity classes and classical (i.e., non-quantum) complexity classes.

A complexity class is a collection of problems which can be solved by some computational model under resource constraints. For instance, the complexity class [[P_P (complexity)|P]] is defined to be the set of problems solvable by a [[Turing machine]] in [[polynomial time]]. Similarly, one may define a quantum complexity class using a quantum model of computation, such as a standard [[quantum computer]] or a [[quantum Turing machine]]. Thus, the complexity class [[BQP]] is defined to be the set of problems solvable by a quantum computer in polynomial time with bounded error.

Two important quantum complexity classes are [[BQP]] and [[QMA]] which are the bounded-error quantum analogues of [[P_P (complexity)|P]] and [[NP_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_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, Quantum Query Complexity is a lower bound on the overall time complexity of a function.

Line 12:

An example depicting the power of Quantum Computing is [[Grover's algorithm]] for searching unstructured databases. Its Quantum Query Complexity is ''O''(''N''^1/2) which is quadratically better than the best known classical query complexity.

==External Linkslinks==

* [https://complexityzoo.uwaterloo.ca/Complexity_Zoo:B#bqp Complexity Zoo] is a good place to read more about Quantum Complexity Theory.

==References==

*{{cite arXiv|eprint=0804.3401v1|author1=John Watrous|authorlink=John Watrous (computer scientist)|title=Quantum Computational Complexity|class=quant-ph|year=2008}}

*{{cite book| author = [[Artem Kaznatcheev]]|title= Quantum query complexity| url= http://cstheory.blogoverflow.com/2011/07/quantum-query-complexity/}}

{{comp-sci-theory-stub}}

{{quantum_computing}}

Line 26 ⟶ 23:

[[Category:Computational complexity theory]]

[[Category:Quantum complexity theory| ]]

{{comp-sci-theory-stub}}