5 ms·
Quantum computing means breaking Bounded Quantum Polynomial, not NP. Integer factorization is in NP, and also in BQP; but some problems can just as well be in N
by lolcraft 13y ago
Quantum computing means breaking Bounded Quantum Polynomial, not NP. Integer factorization is in NP, and also in BQP; but some problems can just as well be in NP and not in BQP. And NP-complete is not a subset of BQP, as far as anyone knows.
- dllthomas 13y agoStrictly, we don't actually know BQP is more powerful than P, right?