By Peter Weiss
In the early 1990s, even the scientists who were in the initial stages of applying quantum mechanics to computing doubted that anyone could ever do useful calculations with their techniques. Those attitudes changed dramatically in 1994, when Peter W. Shor of what is now AT&T Labs in Florham Park, N.J., formulated an algorithm for quantum computers that theoretically could crack the encryption codes protecting secure messages on the Internet and elsewhere (SN: 5/14/94, p. 308).
Now, researchers have for the first time implemented Shor’s famous algorithm, albeit in a rudimentary test.
Shor’s achievement was finding a quantum way to rapidly discover those prime numbers, or factors, that when multiplied together equal a given number. Determining those factors is crucial to breaking encryption codes, which employ numbers so huge that conventional computers would have to run for billions of years to factor them. In contrast, quantum computers running Shor’s algorithm could theoretically find the factors in days or less.
To build a simple quantum computer that actually could carry out Shor’s algorithm, Isaac Chuang of the Massachusetts Institute of Technology and his colleagues created a new molecule with seven atoms that respond to certain electromagnetic waves. Each atom’s nucleus serves as a numerical bit that can be flipped between states, such as 1 and 0. The team then synthesized a billion billion copies of the molecule and dissolved them in an organic solvent.
By subjecting a glass vial of the liquid to radio signals from a laboratory instrument called a nuclear magnetic resonance spectrometer, the scientists manipulated the seven-bit molecules to compute the factors of the number 15, namely, 5 and 3. The liquid’s answer consists of radio signals produced by the nuclei as they interact with a magnetic field, explains Chuang, who worked at IBM Almaden Research Center in San Jose, Calif., at the time of the experiment.
He and his coworkers there and at Stanford University report the new work in the Dec. 20/27, 2001 Nature.
While factoring 15 is a trivial task, the experiment suggests that the technology required to implement Shor’s algorithm on a larger scale is possible, Chuang says.
