IE 11 is not supported. For an optimal experience visit our site on another browser.

A quantum leap in computing

The seemingly bizarre world of quantum mechanics could open the way for a revolution in computing and cryptography.
/ Source:

The world of quantum mechanics goes against the grain of everyday experience. It’s an “Alice in Wonderland” realm beyond the ones and zeroes of classical computing. But if we can figure out how to put this world to work, it would lead to a technological quantum leap, allowing us to solve problems that would take millions of years to figure out using present-day computers. And that has huge implications for the Internet — indeed, for any means of communicating data.

Present-day computing rests on a foundation of bits, with information encoded within electronic circuitry as a series of ones and zeroes. But as circuits become more and more miniaturized, computers come closer to the fuzzy threshold of quantum physics: Quantum objects, such as electrons and other subatomic particles, can be thought of as existing in multiple states simultaneously: “up” as well as “down” … “1” as well as “0.” When you observe a quantum object, you take a snapshot of one of those states — but you also destroy quantum information.

This quantum realm serves as the lower limit for classical computing. The “one-or-zero” concept won’t work in a world of fuzzy “one-and-zero” bits.

But this property, known as “superposition,” opens the way to a completely different approach to computing. In this approach, one quantum bit — or qubit — enables you to manipulate two values at the same time. As you string together more and more qubits, the power grows exponentially. If you link two qubits together, you can work with four values at the same time. Three qubits can work with eight values, and so on. If you can get up to 40 qubits, you could work with more than a trillion values simultaneously.

What could such computers be used for? One important application would be to find the prime factors of very large numbers.

This isn’t just an empty mathematical exercise. Prime factorization happens to be the foundation for secure data communications. It’s relatively easy to multiply two prime numbers together (7,817 and 7,333, for example), but no one has found an easy way to do the calculation in reverse — that is, figure out which two prime numbers can be multiplied together to equal 57,322,061.

This is what makes public-key cryptography possible. Other people can send you messages that are coded using the product of two primes, but that secret message can be deciphered only by someone who knows the two prime factors.

Your computer automatically handles all this coding and decoding in a secure electronic transaction. That’s what protects your credit card information from electronic eavesdroppers when you buy something over the Internet. But suppose the eavesdroppers had quantum computers: With all that computing power, they could figure out the prime factors of even incredibly large numbers — and crack the code.

Thus, the development of quantum computers would require a complete change in the methods used to protect information transmitted over the Internet and other “secure” communications links.

Fortunately for code-makers, quantum computing techniques could be used as well to guarantee security (at least within a negligibly small probability). Quantum cryptography rests on the fact that quantum information cannot be measured without disrupting it. The secret-message software could be built so that attempts to eavesdrop on a message would set off an alarm — and automatically shut down transmission.

Another feature useful for quantum cryptography — and essential for quantum computing — is a bizarre characteristic called entanglement. Two quantum objects can be linked together so that if you observe the result of an interaction with one of the objects, you can figure out what the state of the other object is as well. The entanglement holds even if the two objects are widely separated.

This makes possible an “action-at-a-distance” phenomenon often called quantum teleportation — a term that often leads people to think of “Star Trek” transporters. In reality, what’s being teleported is information about a quantum object, not the object itself.

Two people could encode information, trade it back and forth, and reconstruct the information using entangled quantum systems. Even if eavesdroppers intercept the coded information, they couldn’t read the message because they wouldn’t be part of the entangled system.

Making it real
What forms do these quantum systems take? Photons, ions and atomic nuclei already are being put to work, with the spin of those particles representing ones and zeroes simultaneously.

Researchers at the Los Alamos National Laboratory have demonstrated a quantum cryptography scheme that works over 30 miles (48 kilometers) of optical fiber. At the National Institute of Standards and Technology, two trapped beryllium ions have been wired together through entanglement, potentially representing the world’s first two-qubit computational device.

In addition to ion traps, nuclear magnetic resonance devices are helping scientists use the spin of atomic nuclei in quantum computing experiments. There are even proposals to make quantum computing devices out of good old silicon.

Peter Shor, an award-winning mathematician at AT&T Labs, says it may be possible to develop a 30-qubit computer within the next decade — but that would be just the start. It would take hundreds or thousands of networked qubits to solve problems beyond the capability of classical computers. No one knows when we’ll be able to reach that point. In fact, some researchers worry that the technical hurdles are too great to overcome.

Problems and solutions
Getting the information out: Since measurement destroys quantum information, how do you actually get the results of your calculations? The output from a quantum computer might well be analogous to an interference pattern, Shor says: The correct answer would be built up through constructive interference, while incorrect answers would be canceled out through destructive interference.

Scaling up the system: The NIST experiment shows that qubits can be linked together through entanglement, but can such networks be scaled up in size? Quantum information has a tendency to “leak” into the outside environment, in a process known as decoherence. Thus, the quantum system has to be isolated from outside influence as much as possible.

Compensating for errors: No matter what you do, quantum operations are inherently “noisy.” How do you correct for errors? It turns out that you can adapt classical error-correcting techniques to quantum systems to make them fault-tolerant. If the error rate is less than one part per 10,000, you can make quantum computers work even though the individual operations you’re applying to your qubits aren’t perfectly accurate, Shor says.

If we do develop workable quantum computers, they would come in handy for much more than code-breaking and code-making. They could make it easier to find solutions to other “needle-in-a-haystack” problems — problems for which no better approach is known than exhaustively searching a large set of possible solutions for the correct one. We could gain new insights into how molecules, atoms and subatomic particles behave — unlocking secrets of the quantum world itself.

But in truth, we can’t imagine all the potential uses for quantum computing today — any more than the creators of the first digital computers, a half-century ago, could have imagined where their pioneering work would eventually lead.

This article is based on an interview with Peter Shor, senior researcher at AT&T Labs. Dr. Shor won the 1999 Godel Prize and the 1998 Nevanlinna Award for his work in quantum computing and quantum physics and has been with AT&T Labs since 1986. Dan Simon of Microsoft Research also contributed to this report.

Do you have “Cosmic Questions” about the universe’s great mysteries — such as the prospects for interstellar travel? Or are you wondering about “Common Curiosities,” such as the reasons we snore and what we can do about it? In either case, e-mail your suggestions to, or discuss your questions and answers on the Mysteries of the Universe Bulletin Board. Your topic could become the subject of a future installment of “Mysteries of the Universe.”