Select your localized edition:

Close ×

More Ways to Connect

Discover one of our 28 local entrepreneurial communities »

Be the first to know as we launch in new countries and markets around the globe.

Interested in bringing MIT Technology Review to your local market?

MIT Technology ReviewMIT Technology Review - logo


Unsupported browser: Your browser does not meet modern web standards. See how it scores »

{ action.text }

Algorithm Attack

But how? Feynman and the other theoreticians had focused on quantum computing as a mathematical abstraction-and with good reason. “Building a real quantum computer is a viciously difficult task,” says Chuang. Everything depends on making sure the qubits retain their incredibly fragile quantum-mechanical mix of 1 and 0-what physicists refer to as staying “coherent.” One bump from a stray air molecule, one twitch in the magnetic field, one ricochet of a random photon, and coherency vanishes. Let that happen in a quantum computer and your qubits will instantly collapse from both-and to either-or-meaning that you will suddenly find yourself looking at an ordinary computer full of ordinary 1s and 0s.

“Quantum mechanics goes away when you look at it,” sighs Chuang. “So you have to make sure that the computer is extremely well isolated from the rest of the world.” But the isolation can’t be total, either, since you still need to put data in and read out the results. “This,” Chuang declares, “is the discord that stalks quantum computing. How can you control it if, at the same time, you have to leave it alone?”

As the 1980s became the 1990s, many researchers continued to grapple with the problem. Chuang even made it the subject of his doctoral dissertation at Stanford. But nothing they proposed seemed feasible. And with no compelling application at hand, quantum computing seemed destined for the same cul-de-sac as countless other exotic pieces of science.

Two developments-one theoretical, one practical-have rescued quantum computing from irrelevancy, explains MIT physicist Seth Lloyd. On the theoretical side, it was a factoring algorithm discovered by Peter Shor of AT&T Research labs-an achievement that went right to the heart of modern cryptography. In most current encryption schemes, including those used to send credit-card numbers and other sensitive information across the Internet, an eavesdropper can break the code of a given message only by factoring a very large number. Now, factoring small numbers is trivial-grade school kids learn that 12 = 2 x 2 x 3. But factoring large numbers is one of the quintessentially hard problems in computer science. No matter how clever the algorithms, in fact, the time required to factor larger and larger numbers grows exponentially. Go beyond a few hundred digits, and even the fastest machines in the world will be overwhelmed: The factoring time will vastly exceed the lifetime of the universe.

Or rather, it will with a conventional computer. Shor proved that a quantum computer could factor large numbers in a time that increases only as some power of the numbers’ size-rapid growth, to be sure, but not remotely as explosive as exponential growth. Indeed, a conventional computer would need to crank away for billions of years to factor a 400-digit number. A quantum machine could do the job in about a year. The implication was that “unbreakable” codes might now be breakable. And with that announcement, the National Security Agency, the Pentagon, the cryptography community, and indeed, the whole computer community woke up to the fact that quantum computing wasn’t a theorist’s plaything anymore. Peter Shor was holding out the possibility of a real and critically important application.

Meanwhile, on the experimental side, quantum computing was beginning to look much more possible in the lab. In 1993, for example, Lloyd brought the mathematical abstractions down to earth when he showed how quantum computation could be carried out by qubits arranged in a regular array-just the kind of quantum computer that might actually get built. Then in 1996, Chuang and MIT’s Gershenfeld made things even more concrete when they suddenly saw a way to build it.

“I went into Ike’s office on a Monday and didn’t emerge until Friday,” laughs Gershenfeld, thinking back to the quantum computing conference that brought him to the University of California at Santa Barbara and the Institute for Theoretical Physics, where Chuang had a postdoc appointment. “We got this feeling that comes along only rarely, that there was this beautiful structure already existing in the world, and that we were seeing it for the first time.”

0 comments about this story. Start the discussion »

Tagged: Computing

Reprints and Permissions | Send feedback to the editor

From the Archives


Introducing MIT Technology Review Insider.

Already a Magazine subscriber?

You're automatically an Insider. It's easy to activate or upgrade your account.

Activate Your Account

Become an Insider

It's the new way to subscribe. Get even more of the tech news, research, and discoveries you crave.

Sign Up

Learn More

Find out why MIT Technology Review Insider is for you and explore your options.

Show Me