Can a parallel computer simulate a quantum computer? Is BQP inside NP? If you have an infinite memory infinite processor number classical computer, and you can fork arbitrarily many threads to solve a problem, you have what is called a "nondeterministic" machine. This name is misleading, since it isn't probabilistic or quantum, but rather parallel, but it is unfortunately standard in complexity theory circles. I prefer to call it "parallel", which is more standard usage.
Anyway, can a parallel computer simulate a quantum computer? I thought the answer is yes, since you can fork out as many processes as you need to simulate the different branches, but this is not a proof, because you might recohere the branches to solve a PSPACE problem that is not parallel solvable.
Is there a problem strictly in PSPACE, not in NP, which is in BQP? Can a quantum computer solve a problem which cannot be solved by a parallel machine?
Jargon gloss


*

*BQP: (Bounded error Quantum Polynomial-time) the class of problems solvable by a quantum computer in a number of steps polynomial in the input length.

*NP: (Nondeterministic Polynomial-time) the class of problems solvable by a potentially infinitely parallel ("nondeterministic") machine in polynomial time

*P: (Polynomial-time) the class of problems solvable by a single processor computer in polynomial time

*PSPACE: The class of problems which can be solved using a polynomial amount of memory, but unlimited running time.

 A: 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.
A: There is no definitive answer due to the fact that no problem is known to be inside PSPACE and outside P. But recursive Fourier sampling is conjectured to be outside MA (the probabilistic generalization of NP) and has an efficient quantum algorithm. Check page 3 of this survey by Vazirani for more details.
A: To add to mmc's response, it is currently generally suspected that NP and BQP are incomparable: that is, that neither is contained in the other. As usual for complexity theory, the evidence is circumstantial; and the suspicion here is orders of magnitude less intense (if we pretend that strength of suspicion is measurable) than the general hypothesis that P ≠ NP.
Specifically: as Aaronson and Archipov showed somewhat recently, there are problems in BQP which, if they were contained in NP, would imply that the polynomial hierarchy collaspes to the third level. Restricting myself to conveying the significance of this complexity theorist jargon, any time they talk about the "polynomial hierarchy collapsing" to any level, they mean something which they would regard as (a) quite implausible, and consequently (b) disasterous to their understanding of complexity on the level of the transition from Newtonian mechanics to quantum mechanics, i.e. a revolution of comprehension to be informally anticipated perhaps no more frequently than once every century or so. (The ultimate crisis, a total "collapse" of this "hierarchy", to the zeroeth level, would be precisely the result P = NP.)
