5
$\begingroup$

I have seen various explanations for the power of quantum computers:

Quantum computers perform operations in parallel universes enter image description here Quantum computers can use quantum tunneling to reach a global extremum of a function enter image description here Quantum computers can manipulate quantities of information smaller that 1 bit independently and perform logical operations on such quantities. enter image description here Constant entropy of unitary evolution allows quantum computers to roll back in time, when the answer is wrong, so to perform multiple calculations during the same time interval. enter image description here

Which of these explanations is more correct or do they supplement each other?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Chapter 9 of arXiv:1206.0785 "The Quantum Frontier" lists some of the claimed sources of quantum speedup (not necessarily the ones you list), and explains why these explanations are unsatisfactory. $\endgroup$ – Dan Stahlke Nov 24 '13 at 22:47
  • 1
    $\begingroup$ By the way, do you have a reference for the "smaller than 1 bit" point of view? I have never heard of this before. $\endgroup$ – Dan Stahlke Nov 24 '13 at 22:49
  • 2
    $\begingroup$ Do you have a reference for either the third or fourth points of view? I don't think I've seen either of them before. $\endgroup$ – Peter Shor Nov 25 '13 at 0:39
  • $\begingroup$ @Peter Shor Sorry, I do not remember where I have seen them. Possibly the later is related to closed timelike curves. $\endgroup$ – Anixx Nov 25 '13 at 4:30
  • $\begingroup$ Cross-posted to CSTheory $\endgroup$ – Manishearth Nov 25 '13 at 5:06
6
$\begingroup$

Which of these explanations is more correct or do they supplement each other?

All of them and none of them?

Those explanations all look like they're biased towards particular interpretations of quantum mechanics. I think each arose out of people's favorite interpretation for quantum phenomena.

For example, Quantum computers perform operations in parallel universes is clearly based on the many worlds interpretation. You last explanation could come from this too.

The fractional bit explanation seems to come from a quantum information interpretation.

The tunneling explanation is pretty hand-wavy and would need to be expanded to really comment much about it.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ One can talk about parallel leafs of a wave function instead of universes. $\endgroup$ – Anixx Nov 24 '13 at 17:47
  • $\begingroup$ That sounds awfully similar to the path integral formulation of quantum mechanics. It's a useful computational and cognitive tool but it's hard to say that it's the "correct" description of reality. $\endgroup$ – Brandon Enright Nov 24 '13 at 18:02
  • $\begingroup$ The parallel universes explanation (or the exponential size of state space) is unsatisfactory, in my opinion, since this would also apply to classical probability distributions (which can be viewed as vectors). The difference is that probability distributions admit a hidden variables interpretation. But the distinction between probability distributions and quantum states is subtle. I like the quote that opens Prong 2 of Aaronson's Are Quantum States Exponentially Long Vectors?. $\endgroup$ – Dan Stahlke Nov 24 '13 at 22:55
  • $\begingroup$ @DanStahlke the difference between quantum and classical multiple universes is that quantum universes can interfere with one another, whereas classical ones are always independent. (I'm not saying multiple universes is the right interpretation - I don't think it is - but that distinction makes it a little harder to dismiss.) $\endgroup$ – Nathaniel Nov 25 '13 at 4:18
  • $\begingroup$ @Nathaniel sure, but again there is a subtlety as classical probabilistic "universes" can still interfere constructively, just not destructively. But since you bring up interference I will mention my own paper arXiv:1305.2186. $\endgroup$ – Dan Stahlke Nov 25 '13 at 13:23

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.