Content deleted Content added
→References: added reference |
m →Overview: added wikilinks |
||
Line 7:
A complexity class is a collection of problems that 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]]. The quantum complexity class [[BQP]] is defined in this way as the set of all 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 how these classes relate to classical complexity classes such as [[P (complexity)|P]], [[NP (complexity)|NP]], [[PP (complexity)|PP]], [[PSPACE]] and [[List of complexity classes|other complexity classes]].
==Quantum query complexity ==
| |||