Quantum computers, parallel computing and exponential time I've read that quantum computers can solve 'certain problems' exponentially better than classical computers.  As I think I understand it, it's NOT the same to say that quantum computers take any problems that are EXPTIME-complete, 2-EXPTIME,... and convert them to linear time or constant-time.

I would like to know something more about this matter:


Why can/can't a quantum computer solve exponential problems in sub-exponential time?
Is it at least theoretically possible to imagine a computer (quantum or otherwise) able to solve EXPTIME-complete problems in constant time? Or does this lead to a contradiction?


EDIT  a third related item:


Can quantum computers do parallel computing?


Now that the subject came up from comments, the idea about parallel computing, that's the usual/pop vision about quantum computers, like if quantum computers were able to compute "all posibilities at once" of any given problem (I think if that were the case, wouldn't be necesary to call great Peter Shor to invent a factoring algorithm!). Then "why" question about quantum computers can/cannot do parallel computing is half a computer science and a physics question.

Here a source of confusion: http://physics.about.com/od/physicsqtot/g/quantumparallel.htm
Why can't a quantum computer solve exponential problems in sub-exponential time? Factoring is believed (by some) to take classical time $2^{n^\epsilon}$ for some $\epsilon &gt; 0$, while Shor's algorithm takes time $O(n^3)$. Does that count?

Is it at least theoretically possible to imagine a computer able to solve EXPTIME-complete problems in constant time? Sure, consider a Turing machine with oracle access to all EXPTIME problems (i.e. the oracle accepts the code of an EXPTIME machine and an input, and returns the output). This doesn't lead to any contradictions. Is this realizable in practice? Probably not.

Can quantum computers do parallel computing? It is known that BQP$\subseteq$PP$\subseteq$EXPTIME, and most people expect these inclusions to be proper. Under this conjecture, there are problems solvable in classical exponential time but not quantum polynomial time. In particular, EXPTIME-complete problems shouldn't be in BQP.