Editing BQP (section)

=== P and BQP {{anchor|BQP, P, and NP}} ===

We know <math> \mathsf{P} \subseteq \mathsf{BQP} </math>, since every classical circuit can be simulated by a quantum circuit. <ref> Nielsen, Michael A.; Chuang, Isaac L. (2000), Quantum Computation and Quantum Information, Cambridge: Cambridge University Press, ISBN 0-521-63235-8, MR 1796805.</ref>

It is conjectured that BQP solves hard problems outside of P, specifically, problems in NP. The claim is indefinite because we don't know if P=NP, so we don't know if those problems are actually in P. Below are some evidence of the conjecture:

*[[Integer factorization]] (see [[Shor's algorithm]])<ref name="Shor">[http://www.arxiv.org/abs/quant-ph/9508027 arXiv:quant-ph/9508027v2 ''Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer'', Peter W. Shor]</ref>
*[[Discrete logarithm]]<ref name="Shor"/>
*Simulation of quantum systems (see [[universal quantum simulator]])
*Approximating the [[Jones polynomial]] at certain roots of unity
*[[HHL algorithm|Harrow-Hassidim-Lloyd (HHL) algorithm]]