Over The Horizon

Schrödinger's Computer

Researchers have shown that a theoretical device known as a quantum computer could do certain calculations much faster than a conventional computer. The calculations involved are precisely those needed to break codes used throughout the world: With a working quantum computer, a vast amount of highly valuable encrypted data would be vulnerable.

All digital computers, from Cray-XMPs to the PC on your desktop, represent data with bits -- 0s and 1s. The state of a computer is represented by the pattern of 0s and 1s in its memory and registers. Every location has either a 0 or a 1, and the computer is in a single definite state at each step of a computation.

Quantum computers would take advantage of the quantum notion of superpositions of states. The most infamous such superposition is Schrödinger's cat, sealed in a box and put into a state that is equal parts alive and dead. In a quantum computer, each bit is a kind of Schrödinger's cat and can be a 0, a 1, or some superposition of both. The computer as a whole can be in a superposition of trillions of different states.

Of what use is such a superposition? Like a parallel processor composed of numerous computers working simultaneously, the quantum computer can assign a different calculation to each element of its superposition. For example, to factor a large number n on a quantum computer (ie, to find out what numbers multiply together to give n), one can quickly load a superposition of all the possible factors p and q. Then each element of the computer's superposition calculates the product pq for its values of p and q and checks if it equals n. It only remains to extract the particular element of the superposition that discovered the correct factors.

There's the rub. When one looks into Schrödinger's cat-box one sees either a fully alive cat or a fully dead cat, not a superposition. Similarly, when one tries to read off the state of a quantum computer, all but one element of the superposition will vanish, and the one that remains will be random. The result is no better than trying a couple of random values of p and q on a conventional computer.

This is where the recent result of Peter Shor of AT&T Bell Labs in New Jersey enters the picture. He has shown that by following a clever algorithm, one can eliminate states that would yield no useful information, leaving only states that provide strong clues to the required answer. By performing the computation a number of times, one can find the required answer.

The security of the RSA public-key encryption system, used throughout the world, rests on a would-be eavesdropper being unable to factor a large, publicly known number in less than, say, centuries of computer time. With a quantum computer an eavesdropper could crack any RSA-encoded message much more rapidly.

Whether a working quantum computer can ever be built is debatable. One recently proposed design represents bits with quantum states of individual atoms. Whatever the design, maintaining a perfect quantum superposition throughout a long calculation will be a technical challenge that seems to verge on the impossible, today.

Graham Collins, NZSM, Washington DC

Graham P. Collins NZSM, New York