Over the years I encountered different explanations of quantum computing advantage over classical computers. But I am not sure which explanations are in fact valid and which are not.

  1. Quantum computer utilizes parallelism. It tries to arrive to the solution by multiple ways in parallel, which saves the time needed to find the right way.

  2. Quantum computer can leap to the correct solution. It can tunnel through potential barriers on the solution landscape to a global maximum or minimum.

  3. Quantum computer can go back and forward in time, repeating the calculation with different data. It is claimed that if the result is wrong, the quantum computer in a sense "reverts time", discarding the result and repeats the calculation with different options using the same time interval.

  4. Quantum computer can manipulate quantities of information below 1 bit independently. For instance, if you have 100 variables 1/100 of a bit each, on classical computer you still need 100 bits to store them all, while on quantum computer you can store all these variables in 1 bit.

  5. Quantum computer utilizes faster-than-light speed to transfer quantum information during calculation. It is claimed that quantum information can be transferred faster than light unlike classical information.

Please tell me, which of these interpretations are correct and which are not.

  • 1
    $\begingroup$ Can you name a source or two for each of these? Two of these are fairly common to hear, but some of them I can't really believe are ever offered as any sort of well-informed attempt to explain quantum computing. $\endgroup$ – Niel de Beaudrap Dec 2 '19 at 20:47
  • 1
    $\begingroup$ This is a nice collection of common misunderstandings :) A somewhat accurate explanation is that a quantum computer uses the effect of interference in a very high dimensional space. But to understand it and use it you need to go through the math. $\endgroup$ – Danylo Y Dec 3 '19 at 9:04
  • $\begingroup$ @DanyloY: following on my comment above, I would say that one or two of these are totally unlikely to be 'common' misunderstandings. I'm not saying that the OP just made them up, but I'd like to know who is saying these sorts of things. (Are these actually the result of well-intentioned attempts by an expert to explain something difficult, or are they the sorts of folk theories that people tend to come up with whenever they're trying to understand something with very little information?) If you know of sources for these, from attempts by experts to explain quantum computing, please tell us. $\endgroup$ – Niel de Beaudrap Dec 3 '19 at 10:50
  • $\begingroup$ @NieldeBeaudrap, well, maybe the word $common$ is too strong. I don't think there are such sources, except some internet discussions of tech people that are not scientists. I think those guesses are somewhat reasonable for people who have a very little information of the actual things :) $\endgroup$ – Danylo Y Dec 3 '19 at 11:00
  • 2
    $\begingroup$ @DanyloY: It might be reasonable to expect people to make such guesses, but that makes this question (by definition) a matter of speculative physics... $\endgroup$ – Niel de Beaudrap Dec 3 '19 at 15:55

1 and 2 have elements of truth, but are only partially correct, with big caveats.

3 and 5 are complete nonsense.

You can choose to read 4 the right way to make some sense out of it, but it doesn’t contribute to the computational speed of any algorithms.

| improve this answer | |
  • $\begingroup$ How would you suggest that 4 can be interpreted to make some sense? $\endgroup$ – Niel de Beaudrap Dec 2 '19 at 23:50
  • $\begingroup$ @NieldeBeaudrap In the sense that you can encode an infinite amount of information on a qubit by specifying the Bloch vector to arbitrary accuracy. Of course that doesn’t help with processing because you cannot extract that information. $\endgroup$ – DaftWullie Dec 3 '19 at 7:10
  • $\begingroup$ Okay. Of course, that doesn't make for a very good concept of information 'storage'. $\endgroup$ – Niel de Beaudrap Dec 3 '19 at 8:11

Few experts seem willing to opine on how to interpret the power of quantum computers. I'm only aware of two notable exceptions.

Peter Shor gave an analogy that has some resemblance to #2 (in a comment to this answer):

Think of a quantum computer as a boat and a classical computer as a car. Suppose you want to go from New London, CT to Orient, NY. The ferry will take 80 minutes. Google Maps says the distance is 210 miles. So clearly, the ferry is averaging 157.5 miles per hour, right? No, it's taking a different path that is shorter (but that only boats can take). Similarly, Shor's algorithm is taking a different path that is shorter (but that only quantum computers can take).

On the other hand, David Deutsch is a vocal advocate that quantum computers leverage computing power from parallel universes, which has some resemblance to #1.

Once there are actual quantum computers, and a journalist can go to the actual labs and ask how does that actual machine work, the physicists in question will then either talk some obfuscatory nonsense, or will explain it in terms of parallel universes.

(source). Despite being in the minority, he has been consistent in this point of view since his seminal work on quantum computing from 1985.

| improve this answer | |

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