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

• 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

• My very cursory understanding was that quantum computers essentially were using parallelism to speed up computation. However, there's limits on how much certain problems can be parallelized, which would leave some exponential. As for solving in constant time, I find that hard to imagine, since you would be able to give it a problem of any length and it would solve it within the same bound. But I'm not an expert. – jmite Jun 25 '13 at 15:48
• @jmite That's incorrect. Quantum computers are not glorified parallel machines - they're not parallel at all. The internal state might be in superposition, but that's very different from parallelization. – Yuval Filmus Jun 25 '13 at 17:09
• Good to know! Glad I didn't answer then. – jmite Jun 25 '13 at 19:50
• the conventional theoretical wisdom is that QM and parallelism are not intrinsically connected, and that this is an unfortunate mass media simplification that specialists cringe at and work to clarify, but imho this is verging on dogmatic by some & given all the known circumstantial connections, I regard it more as an open question worthy of further research. see also connections between QM computing and parallelism & the ensuing discussion which has various refs/links etc – vzn Jun 25 '13 at 23:27
• @vzn: Apologies for deleting and re-commenting, but I think that it's pertinent: as one of the cringing specialists, I've now taken the time to explicitly describe why the "connections" (in your linked answer at CSTheory) between QM computing and parallelism are not really connections. It is not logically impossible that such connections could be made: but #1 no convincing connections actually exist yet AFAIK, and #2 attempts to understand QC in terms of parallelism obscures more than it illuminates. This hopefully shows you why we cringe when people enthuse about such "connections". – Niel de Beaudrap Mar 25 '14 at 9:33

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 > 0$, while Shor's algorithm takes time $O(n^3)$. Does that count?
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.