A Quantum Computer Has Factored the Number 15

This may sound like a trivial achievement, but it is actually a considerable physics milestone. It represents the most complex calculation yet performed in quantum computing, which offers a radically different means of information processing through the use of quantum mechanics. Even more noteworthy, it is the first experimental demonstration of Shor's algorithm, a quantum-computer program which can potentially factor large numbers in a fraction of the time needed for the world's currently fastest supercomputers. Such large numbers are used as the basis of encryption codes; the codes are broken by finding the prime-number factors of the large numbers.

IBM-Almaden and Stanford University researchers (Isaac Chuang, now at MIT, ichuang@cba.mit.edu) built a quantum computer whose working substance was a liquid consisting of a billion billion molecules. The molecules were specially designed to contain 7 nuclear "spins"--5 from fluorine nuclei and 2 from carbon-13 nuclei. Analogous to a bar magnet which could point north or south, each spin could represent the binary digits "0" or "1" (or both 0 and 1 at the same time through the subtleties of quantum mechanics) and could be controlled by magnetic fields and radio waves (i.e., nuclear magnetic resonance techniques). By manipulating the 7 qubits, the computer could take advantage of quantum computing's unique parallel processing capabilities to determine that the factors of 15 were 3 and 5. Enormous challenges must be surmounted to build larger-scale quantum computers which could factor very large numbers, and this is an early step forward. (Vandersypen et al., Nature, 20/27 December 2001; also see IBM-Almaden news release.)