Quantum complexity theory: Difference between revisions

Revision as of 19:48, 19 September 2009

Revision as of 00:02, 28 September 2009

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.

#REDIRECT [[Quantum computer#Relation to computational complexity theory]]

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_(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_(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]].

==References==

{{cite arXiv|eprint=0804.3401v1}}

{{comp-sci-theory-stub}}

{{quantum_computing}}

[[Category:Computational complexity theory]]

[[Category:Quantum complexity theory]]