By Davide Castelvecchi

From Science News, December 8th, 2007; Vol.172 #23 (p. 356)

Two teams of physicists have independently confirmed that 15 equals 3 times 5—an arduous task considering that they’ve done it by manipulating the quantum states of photons. The results are a step toward optical quantum computers, which could do some calculations exponentially faster than ordinary computers can and crack the encryption codes that protect data traveling over the Internet.

Multiplying two whole numbers is easy, but the inverse operation generally isn’t: Identifying when a number is the product of other whole numbers becomes exponentially more complex as the numbers get bigger, quickly overwhelming even the fastest supercomputers.

This is good for privacy. When Web-based programs request sensitive data over the Internet, they ask the sender’s Web browser to encrypt the data using a number, called the public key, that is the product of two prime numbers. Decrypting the data requires identifying those two prime numbers, which only the legitimate recipient knows. Anyone wishing to steal the data would have to break the public key into its prime factors.

In 1994, mathematician Peter Shor, now at the Massachusetts Institute of Technology (MIT), theoretically demonstrated that a computer based on the principles of quantum mechanics could quickly find the prime factors of public keys.

A quantum computer would represent information as quantum states of some physical system, such as the magnetic alignments of atoms or the polarization directions of photons. Shor’s algorithm exploits the ability of such systems to exist simultaneously in multiple states. The quantum computer could in essence try dividing a number by all possible factors at the same time. Only states corresponding to the true factors—those that give zero as remainder—would have any probability of actually being measured.

In 2001, researchers ran a simplified version of Shor’s algorithm using magnetic orientations of the atomic nuclei in fluorocarbon molecules (SN: 1/12/02, p. 31). Using just seven atoms to encode bits of information, the molecules’ magnetic states revealed the prime factors, 3 and 5, of the number 15.

Now two teams—one led by Jian-Wei Pan of the University of Science and Technology of China in Hefei, and the other by Andrew White of the University of Queensland in Brisbane, Australia—have performed the same feat using photons.

Photons don’t interact much with things around them, explains Pan’s colleague Daniel Browne of Oxford University in England. That facilitates keeping the photons in multiple states, in which the photons are polarized horizontally and vertically at the same time.

Both teams pointed lasers at special crystals to create pairs of photons that occupied different combinations of polarization states. Interference between the wave patterns corresponding to the photons then performed the logic operations that yielded the factors of 15. Both results appear in the Dec. 21 Physical Review Letters.

Seth Lloyd of MIT says the results are a “necessary step” toward photon-based quantum computers. But, he adds, “it’s a judgment call that they demonstrated the internal nugget of quantumness in Shor’s algorithm,” because the teams were able to implement the algorithm only in a drastically simplified form.

“It wasn’t the full demonstration; we’re years away from that yet,” White says. But both White and Browne say their results suggest that photon techniques could lead to computers that can find factors of large numbers and potentially have other applications that are beyond the capacity of current computers, such as simulating the quantum behavior of large molecules. For now, our credit card numbers may still be safe.