3 ms·
It is unknown if BQP >= NP or NP-complete
by lostmsu 9y ago
It is unknown if BQP >= NP or NP-complete
- tromp 9y agoNP-completeness is a property of problems, while BQP is a complexity class (set of problems). If any NP-complete problem is in BQP, then NP is a subset of BQP. But it's not even known whether BQP > P, so we could have P = BQP < NP.