I recently stumbled upon this paper here and here on the "deep ai" website that claims "BQP is not in NP."

I thought that this result would be huge (as a corollary would be that $BQP \neq P$), so I find it strange that I haven't heard about the proof before.

Is this paper legit?

  • $\begingroup$ This question was closed as per the following journal paper: doi.org/10.1016/S0020-0190(99)00084-8 That is, BQP=/=NP $\endgroup$
    – lin
    Commented Mar 18, 2023 at 4:10
  • 2
    $\begingroup$ @lin: I am a little bit unsure because in the abstract it is stated that BQP differs from NQP . However NP and NQP are different classes. $\endgroup$ Commented Mar 18, 2023 at 8:24

1 Answer 1


There is no known relationship of BQP and NP. The wikipedia page is up to date on the relationship of BQP to other classes.

The pdf you linked is not a peer-reviewed publication, and should not be believed.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.