|
<!-- Relation of BQP to probabilistic complexity classes -->
As a class of probabilistic problems, BQP is the quantum counterpart to [[Bounded-error probabilistic polynomial|BPP]] ("bounded error, probabilistic, polynomial time"), the class of problems that can be efficiently solved by [[probabilistic Turing machine]]s with bounded error.<ref>{{cite book | author1-link= Michael Nielsen| author1=Nielsen, Michael |author2-link = Isaac L. Chuang |author2=Chuang, Isaac |title=Quantum Computation and Quantum Information |publisher=Cambridge University Press |___location=Cambridge |year=2000|page=41 |isbn=978-0-521-63503-5 |oclc= 174527496 |url=https://books.google.com/books?id=aai-P4V9GJ8C}}</ref> It is known that BPP<math>\mathsf{BPP\subseteq BQP}</math>BQP and widely suspected, but not proven, that BQP<math>\mathsf{BQP\nsubseteq BPP}</math>BPP, which intuitively would mean that quantum computers are more powerful than classical computers in terms of time complexity.<ref>Nielsen, p. 201</ref> BQP is a subset of [[PP (complexity)|PP]].
<!-- Relation of BQP to basic deterministic complexity classes -->
The exact relationship of BQP to [[P (complexity)|P]], [[NP (complexity)|NP]], and [[PSPACE (complexity)|PSPACE]] is not known. However, it is known that P<math>\mathsf{P\subseteq</math> BQP<math> \subseteq PSPACE}</math>PSPACE; that is, the class of problems that can be efficiently solved by quantum computers includes all problems that can be efficiently solved by deterministic classical computers but does not include any problems that cannot be solved by classical computers with polynomial space resources. It is further suspected that BQP is a strict superset of P, meaning there are problems that are efficiently solvable by quantum computers that are not efficiently solvable by deterministic classical computers. For instance, [[integer factorization]] and the [[discrete logarithm problem]] are known to be in BQP and are suspected to be outside of P. On the relationship of BQP to NP, little is known beyond the fact that some NP problems are in BQP (integer factorization and the discrete logarithm problem are both in NP, for example). It is suspected that NP<math>\mathsf{NP\nsubseteq BQP}</math>BQP; that is, it is believed that there are efficiently checkable problems that are not efficiently solvable by a quantum computer. As a direct consequence of this belief, it is also suspected that BQP is disjoint from the class of [[NP-complete]] problems (if any NP-complete problem were in BQP, then it follows from [[NP-hard]]ness that all problems in NP are in BQP).<ref name=BernVazi>{{cite journal |last1=Bernstein |first1=Ethan |last2=Vazirani |first2=Umesh |doi=10.1137/S0097539796300921 |title=Quantum Complexity Theory |year=1997 |pages=1411–1473 |volume=26 |journal=SIAM Journal on Computing |url=http://www.cs.berkeley.edu/~vazirani/bv.ps |issue=5|citeseerx=10.1.1.144.7852 }}</ref>
<!-- Summary of relationship to essential complexity classes -->
<!-- Relation of BQP to other complexity classes -->
It is also known that BQP is contained in the complexity class ''[[Sharp-P|{{tmath|\color{Blue}\mathsf{\#P} }}]]'' (or more precisely in the associated class of decision problems ''{{tmath|\mathsf{P<sup>^{\#P</sup>''} } }}),<ref name=BernVazi/> which is a subset of [[PSPACE]].
== Simulation of quantum circuits ==
| 