Quoting Wikipedia: BQP is suspected to be disjoint from NP-complete and a strict superset of P, but that is not known. Both integer factorization a

Quoting Wikipedia: BQP is suspected to be disjoint from NP-complete and a strict superset of P, but that is not known. Both integer factorization and discrete log are in BQP. Both of these problems are NP problems suspected to be outside BPP, and hence outside P. Both are suspected to not be NP-complete. There is a common misconception that quantum computers can solve NP-complete problems in polynomial time. That is not known to be true, and is generally suspected to be false.[82] https://en.wikipedia.org/wiki/Quantum_computing#Relation_to_computational_complexity_theory https://en.wikipedia.org/wiki/Quantum_computing#Relation_to_...