What is the relation between BQP complexity class and P and NP?
closed as off topic by Kaveh Nov 25 '12 at 18:07
Questions on Theoretical Computer Science Stack Exchange are expected to relate to research-level theoretical computer science within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here. If this question can be reworded to fit the rules in the help center, please edit the question.
P is contained within BQP. This is trivial, since quantum operations are a superset of classical operations. Indeed, BQP contains BPP as well, since you can use Hadamards to produce randomness in the computational basis.
Much less trivial is the relationship between NP and BQP. At present, the consensus opinion seems to be that neither entirely contains the other, though clearly both contain P, and certain problems believed to be NP-intermediate like factoring integers, so their intersection is itself non-trivial. There are oracles relative to which BQP is not contained within NP (via recursive Fourier sampling for example), and conversely oracles relative to which NP is not contained within BQP (this is true with probability 1 relative to a random oracle, see quant-ph/9701001).
We do know that BQP is contained within PP, but there is strong evidence that it is not contained within the polynomial hierarchy at all (see Scott Aaronson's paper on BQP and the polynomial hierarchy for example).