Hacker News new | past | comments | ask | show | jobs | submit login

I would say this explanation is essentially wrong. It makes it sound like the difference is that the computer is ternary rather than binary, which of course would not be a significant difference.

Part of this is that the "more than one state at at time" applies to the whole computer, not individual bits, but the thing is that the whole "more than one state at a time" thing isn't it either.

To see this, instead of a quantum computer, let's consider a probabilistic computer. Rather than having one state, the computer at any time has a probability distribution over states -- it can "be in multiple states at once", each with some probability. Only at the end of a computation do you "collapse" it back into a single value. Except that such a computer is equivalent to an ordinary computer equipped with a TRNG, which is not much more powerful than an ordinary computer at all.

Quantum computers are often described as "trying everything at once", as if they were nondeterministic Turing machines, but they are not; perhaps, in some sense, they do try everything at once, but they cannot then automatically pick out whichever possibility worked. It only "tries everything at once" in the same sense the probabilistic computer does. The probabilistic computer can only pick out the right answer if you somehow set it up that the right answer has high probability and the wrong ones don't; it can't say "this answer is right, kill all the other possibilities now!".

The quantum computer is the same way. What makes quantum computers faster is the fact that instead of probabilities, they use amplitudes. To each state -- well, what I was calling states above, really they would be "basis states" -- would be associated an amplitude rather than a probability. Amplitudes yield probabilities -- the probability is the square of the absolute value of the amplitude -- but they do more; in particular, they can be negative. Indeed, they can be complex, but that they can be negative is usually enough. This allows one to do many more tricks with them, in quite a few ways, but in particular, it means that it's easier to set it up for the right answer to come out with high probability, because unlike probabilities, amplitudes can cancel out. All quantum algorithms, as I understand it, are about using appropriate tricks to get the amplitudes for the wrong answers to mostly cancel out.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: