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