Everybody knows that there are whole classes of problems which quantum computers are able to solve much faster (i.e. with fewer instructions) than classical computers.

Is there any problem for which the reverse is true?

  • 2
    $\begingroup$ Perhaps it is because Quantum Computers do not yet exist. Also, the very nature of the two computers cannot be compared on a per instruction basis. $\endgroup$ – Dave Clarke Sep 10 '13 at 18:18
  • 3
    $\begingroup$ @Peter, if we are talking about mathematical models then I think the common models of quantum computation are generalizations of the standard classical model, isn't that the case? And if we are talking about real quantum computers then I think Dave's comment is valid. $\endgroup$ – Kaveh Sep 10 '13 at 18:53
  • 9
    $\begingroup$ Yes, but quantum computers are only allowed reversible classical operations, and it's not completely obvious that classical reversible computation isn't much slower than classical computation. (You need to use a non-obvious theorem of Charles Bennett to prove this.) Furthermore, if you only have limited memory available, it's not true ... there seem to be computations which can be done quite a bit more quickly with irreversible computation given limited space. $\endgroup$ – Peter Shor Sep 10 '13 at 18:56
  • 1
    $\begingroup$ I've voted the question up because I'd like to read answers, and because Peter Friggin' Shor thinks it's worthwhile. $\endgroup$ – Neil Toronto Sep 10 '13 at 19:13
  • 4
    $\begingroup$ Although I did not vote yet one way or the other, I don't think this is a good question since BPTIME(f(n)) \subseteq BQTIME(f(n)) is clear. If the OP has different computational model(s) in mind, then he should have specified them. $\endgroup$ – Huck Bennett Sep 10 '13 at 19:51

If you're asking whether a quantum computer can compute any function that a classical computer can compute without using many more elementary computational steps, then the answer is yes: a quantum computer can perform any reversible classical computation, and if you keep the input around, any classical computation can be made reversible at a cost of multiplying the number of steps by a small constant factor.

If you're asking whether a quantum computer can compute any function that a classical computer can without using many more resources, the answer is much less clear. The construction that lets you make a $T$-step computation reversible using $O(T)$ steps also takes $O(T)$ space (i.e., memory cells). You can achieve a smaller blow-up in space at the cost of a superlinear number of steps. See Time/Space Trade-Offs for Reversible Computation by Charles H. Bennett.

For an actual physical quantum computer, it's very likely that you might also be able to make it faithfully simulate a classical computer by letting it lose coherence, but in this case it's no longer really working as a quantum computer, and if you try to use a quantum computer that is operating this way as a subroutine in a quantum computation, it might not work properly.

  • $\begingroup$ Exactly the kind of information I was looking for. Thank you! $\endgroup$ – user17560 Sep 12 '13 at 13:26

http://www.youtube.com/watch?v=g_IaVepNDT4 check it out, that guy explains your question. He starts with the concept of a qbit and around the 5:15 mark he goes into what you asked.

Hope this helps!

  • 1
    $\begingroup$ The video was very interesting, but AFAICS starting at 5:15 what he actually explains is that superposition doesn't help all algorithms (i.e. quantum algorithms are not at an advantage everywhere), rather than that quantum algorithms are at a disadvantage for some problems. $\endgroup$ – user17560 Sep 12 '13 at 13:29

Your Answer

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