Quantum Confusion

For every computer scientist waiting for the first working quantum computer, there are two that are hoping that that day will never come, because it means that they will have to start developing quantum algorithms. Why is that a problem? Well, have a good look at Shor's quantum algorithm for integer factorisation. Yep, it's not pretty, in fact, I'm not sure I could find out how it works from that article.

Fortunately for me, and other lazy computer scientists, Scott Aaron has provided an easy-to-understand guide to Shor's algorithm. In the process of explaining it, he also debunks some of the most common myths about quantum computing:

Look: if you think about quantum computing in terms of “parallel universes” (and whether you do or don’t is up to you), there’s no feasible way to detect a single universe that’s different from all the rest. Such a lone voice in the wilderness would be drowned out by the vast number of suburb-dwelling, Dockers-wearing conformist universes. What one can hope to detect, however, is a joint property of all the parallel universes together — a property that can only be revealed by a computation to which all the universes contribute.

(Note: For safety reasons, please don’t explain the above to popular writers of the “quantum computing = exponential parallelism” school. They might shrivel up like vampires exposed to sunlight.)