7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – jmite Jun 25 '13 at 15:48
  • 8
    $\begingroup$ @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. $\endgroup$ – Yuval Filmus Jun 25 '13 at 17:09
  • 1
    $\begingroup$ Good to know! Glad I didn't answer then. $\endgroup$ – jmite Jun 25 '13 at 19:50
  • 2
    $\begingroup$ 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 $\endgroup$ – vzn Jun 25 '13 at 23:27
  • $\begingroup$ @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". $\endgroup$ – Niel de Beaudrap Mar 25 '14 at 9:33
6
$\begingroup$

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?

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.

$\endgroup$
  • $\begingroup$ First answer is a particular example but I was thinking about any exponential problem, I've added a third item to focus question about parallel computing, anyway clear answers. $\endgroup$ – Hernan_eche Jun 25 '13 at 18:38
  • $\begingroup$ Addressed your new question. $\endgroup$ – Yuval Filmus Jun 25 '13 at 18:58
3
$\begingroup$

It's certainly possible to imagine computers able to solve certain problems (EXPTIME-complete or otherwise) in constant time. Such computers are called "oracle machines," and they are an important tool in the study of complexity theory. However, it's not necessarily possible to construct these machines.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.