This has been a major open problem in quantum complexity theory for 20 years. Here's what we know:

(1) Suppose you insist on talking about decision problems only ("total" ones, which have to be defined for every input), as people traditionally do when defining complexity classes like P, NP, and BQP. Then we have proven separations between BQP and NP in the "black-box model" (i.e., the model where both the BQP machine and the NP machine get access to an oracle), as mmc alluded to. On the other hand, while it's very plausible that those would extend to oracle separations between BQP and PH (the entire polynomial hierarchy), right now, we don't even know how to prove an oracle separation between BQP and AM (a probabilistic generalization of NP slightly higher than MA). Roughly the best we can do is to separate BQP from MA.

And to reiterate, all of these separations are in the black-box model only. It remains completely unclear, even at a conjectural level, whether or not these translate into separations in the "real" world (i.e., the world without oracles). We don't have any clear examples analogous to factoring, of real decision problems in BQP that are plausibly not in NP. After years thinking about the problem, I still don't have a strong intuition either that BQP should be contained in NP in the "real" world or that it shouldn't be.

(Note added: If you allow "promise problems," computer scientists' term for problems whose answers can be undefined for some inputs, then I'd guess that there *probably* is indeed a separation between PromiseBQP and PromiseNP. But my example that I'd guess witnesses the separation is just the tautological one! I.e., "given as input a quantum circuit, does this circuit output YES with at least 90% probability or with at most 10% probability, promised that one of those is the case?")

For more, check out my paper BQP and the Polynomial Hierarchy.

(2) On the other hand, if you're willing to generalize your notion of a "computational problem" beyond just decision problems -- for example, to problems of sampling from a specified probability distribution -- then the situation becomes much clearer. First, as Niel de Beaudrap said, Alex Arkhipov and I (and independently, Bremner, Jozsa, and Shepherd) showed there are sampling problems in BQP (OK, technically, "SampBQP") that can't be in NP, or indeed anywhere in the polynomial hierarchy, without the hierarchy collapsing. Second, in my BQP vs. PH paper linked to above, I proved unconditionally that relative to a *random* oracle, there are sampling and search problems in BQP that aren't anywhere in PH, let alone in NP. And unlike the "weird, special" oracles needed for the separations in point (1), random oracles can be "physically instantiated" -- for example, using any old cryptographic pseudorandom function -- in which case these separations would very plausibly carry over to the "real," non-oracle world.

This post imported from StackExchange Physics at 2014-07-24 15:40 (UCT), posted by SE-user Scott Aaronson