In an important milestone toward making powerful computers that exploit the mind-bending possibilities of calculating with individual atoms, scientists at the I.B.M. Almaden Research Center, in San Jose, Calif., are announcing today that they have performed the most complex such calculation yet: factoring the number 15.
The answer itself was no surprise: 3 and 5, the numbers that divide into 15, leaving no remainder. But the exercise that led to that simple result — the first factoring of a number with an exotic device called a quantum computer — holds the promise of one day solving problems now considered impossible, and cracking seemingly impenetrable codes.
Tiny though they are, the switches that manipulate ones and zeroes in current state-of-the-art computers each consist of billions of atoms. In the quantum computing experiment, the scientists performed the calculation by manipulating single atoms, the submicroscopic equivalent of abacus beads. This confirmed a big advantage: because of the chimerical nature of quantum mechanics, the law that rules the atomic realm, the procedure's multiple steps could be carried out simultaneously.
If this kind of quantum parallelism can be extended to a larger scale, an effort far from trivial, numbers hundreds of digits long could be factored with ease. Since many schemes used to protect electronic information are based on the near impossibility of factoring large numbers, building a working quantum computer would be not only a mathematical coup but a cryptographic one as well, potentially putting much of the world's most secret information in jeopardy.
"We now believe that quantum computing is going to be a fact of nature," said Dr. Isaac L. Chuang, who led the team of researchers, from I.B.M. and Stanford University. "That's incredibly surprising to me. I started out thinking that quantum computing was not going to be a viable enterprise." He said he was happy to have been proved wrong.
Dr. Peter Shor, the scientist at AT&T Laboratories who proved seven years ago that quantum factoring was a theoretical possibility, called the new advance, being reported today in the journal Nature, "an impressive accomplishment," though he added, "There's still a long road ahead before we develop useful quantum computers."
Factoring is what mathematicians call an intractable problem. It is easy to factor small numbers, but as they increase in size, calculation time grows exponentially. In 1999, experts set a record by factoring a 155-digit number — a feat that required 292 computers grinding away for half a year. Because of the exponential nature of the problem, factoring a number twice that long could take hundreds of millions of years.
Cryptographers have drawn on this fact to develop codes considered all but unbreakable. The sender of a message picks two long prime numbers (those that have no factors) and multiplies them together. This yields a larger number that becomes the key used to encrypt the text. Breaking the code entails working backward to recover the original factors, a procedure requiring enough calculations to flummox a supercomputer.
Quantum computing, however, works by different rules. In 1994, Dr. Shor invented an algorithm — a sequence of operations — that would allow a quantum computer to do the calculations simultaneously, factoring numbers hundreds of digits long in perhaps minutes.
This is possible because a quantum computer's counters consist of single atoms, which can point up or down, indicating 1 or 0, the two symbols of binary arithmetic. More important, quantum mechanics allows an atom to point both up and down simultaneously, indicating 1 and 0 at the same time.
Thus two atoms can simultaneously register four quantities: 00, 01, 10 and 11 (the numbers 0 through 3 in the binary tongue). Three atoms can hold eight numbers, four can hold 16. By the time you reach seven atoms — the number harnessed for the I.B.M. experiment — you have a tiny device with the capability of simultaneously registering 128 different numbers. Flipping the atoms up and down in various patterns causes a calculation to be performed — on all the numbers at once.
In the experiment, Dr. Chuang and his colleagues — Dr. Lieven M. K. Vandersypen, Matthias Steffen, Gregory Breyta, Dr. Costantino S. Yannoni and Dr. Mark H. Sherwood — used a molecule consisting primarily of fluorine and carbon atoms.
A vial of liquid containing quadrillions of the molecules was placed inside a machine called a nuclear magnetic resonance spectrometer, using the same technology on which hospitals draw for M.R.I. scanning. By bombarding the molecules with a precise sequence of electromagnetic pulses, the experimenters carefully flipped the atoms back and forth between 1 and 0, carrying out the steps of Dr. Shor's algorithm.
Rapidly factoring numbers the size of those used in cryptography would probably require delicate manipulation of tens of thousands of atoms, and the slightest disturbance could cause the calculation to come undone. But with the principle of quantum factoring proved on paper and now demonstrated in the laboratory, some scientists are optimistic.
"We have to move far beyond this," Dr. Chuang said. "But at least we have demonstrated that it is possible."