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

1. 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.


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


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


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

Answer

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.