How a quantum computer can factor a large number

An article today in New Scientist discusses two quantum computers, independantly built by two different research teams, that are capable of running Shor’s quantum factorization algorithm. The current machines are only large enough to factor a small number–in this case, the number 15–but assuming the engineering challenges can be overcome and a larger quantum computer with more qubits is created, the quick factoring of large numbers (like those used in RSA public key cryptography) will be possible using the same algorithm.

Scott Aaronson wrote a most excellent essay titled “Shore, I’ll Do It” that explains, in man on the street terms, how Shor’s algorithm and the quantum Fourier transform works.

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.

If you’ve ever wondered how a quantum computer actually accomplishes work, have a read.

Shor, I’ll do it – Link
Quantum threat to our secret data – [via] Link