Hacker News new | ask | show | jobs
by lostmsu 3081 days ago
It is unknown if BQP >= NP or NP-complete
1 comments
tromp 3080 days ago
NP-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.

link