Editing Quantum computing (section)

=== Complexity<span class="anchor" id="Quantum complexity theory"></span> ===
{{Main|Quantum complexity theory}}

<!-- Power and limits of quantum computers -->
While quantum computers cannot solve any problems that classical computers cannot already solve, it is suspected that they can solve certain problems faster than classical computers. For instance, it is known that quantum computers can efficiently [[integer factorization|factor integers]], while this is not believed to be the case for classical computers.

<!-- Basic definition of BQP -->
The class of [[computational problem|problems]] that can be efficiently solved by a quantum computer with bounded error is called [[BQP]], for "bounded error, quantum, polynomial time". More formally, BQP is the class of problems that can be solved by a polynomial-time quantum Turing machine with an error probability of at most 1/3. 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 solved by polynomial-time [[probabilistic Turing machine]]s with bounded error.{{sfn|Nielsen|Chuang|2010|p=41}} It is known that <math>\mathsf{BPP\subseteq BQP}</math> and is widely suspected that <math>\mathsf{BQP\subsetneq BPP}</math>, which intuitively would mean that quantum computers are more powerful than classical computers in terms of [[time complexity]].{{sfn|Nielsen|Chuang|2010|p=201}}

<!-- Relation of BQP to basic complexity classes -->
[[File:BQP complexity class diagram.svg|thumb|The suspected relationship of BQP to several classical complexity classes{{sfn|Nielsen|Chuang|2010|p=42}}]]
The exact relationship of BQP to [[P (complexity)|P]], [[NP (complexity)|NP]], and [[PSPACE (complexity)|PSPACE]] is not known. However, it is known that <math>\mathsf{P\subseteq BQP \subseteq PSPACE}</math>; that is, all problems that can be efficiently solved by a deterministic classical computer can also be efficiently solved by a quantum computer, and all problems that can be efficiently solved by a quantum computer can also be solved by a deterministic classical computer 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 that are believed not to be in P are also in BQP (integer factorization and the discrete logarithm problem are both in NP, for example). It is suspected that <math>\mathsf{NP\nsubseteq BQP}</math>; 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 an NP-complete problem were in BQP, then it would follow 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>