David is right about one thing. Scott had a discussion about this on his blog and I was also involved.

On the one hand, many complexity theorists simply also assume that BQP does not contain NP, just as they assume that P does not contain NP. The evidence for the former is not as dramatic as that for the latter, but there is at least an oracle separation. I.e., there is an oracle A such that BQP^{A} does not contain NP^{A}. Now, there are some famous cases where two complexity classes are equal or there is an inclusion, even though there is also a credible oracle separation. But the oracle separations for BQP vs NP seem realistic. Besides, apart from tangible evidence, I for one consider BQP to be surprisingly powerful but not incredibly powerful. It's my intuition partly because I expect BQP to be realistic and I don't expect the universe to be perverse. I think of BQP as an extension of randomized computation based on quantum probability.

On the other hand, P vs PSPACE is already an unfathomable open problem. The two main barrier results for P vs NP, Baker-Gill-Solovay and Razborov-Rudich, apply to P vs PSPACE equally well. Since PSPACE contains both NP and BQP, if you were to show that either one does not equal P, then in particular you would show that PSPACE does not equal P. Actually, I don't know a good reason to try to prove that P ≠ NP rather than to first prove that P ≠ PSPACE, since the latter is at least formally easier.

3more comments