The Information - James Gleick [177]
“Feynman’s insight,” says Bennett, “was that a quantum system is, in a sense, computing its own future all the time. You may say it’s an analog computer of its own dynamics.”♦ Researchers quickly realized that if a quantum computer had special powers in cutting through problems in simulating physics, it might be able to solve other types of intractable problems as well.
The power comes from that shimmering, untouchable object the qubit. The probabilities are built in. Embodying a superposition of states gives the qubit more power than the classical bit, always in only one state or the other, zero or one, “a pretty miserable specimen of a two-dimensional vector,”♦ as David Mermin says. “When we learned to count on our sticky little classical fingers, we were misled,” Rolf Landauer said dryly. “We thought that an integer had to have a particular and unique value.” But no—not in the real world, which is to say the quantum world.
In quantum computing, multiple qubits are entangled. Putting qubits at work together does not merely multiply their power; the power increases exponentially. In classical computing, where a bit is either-or, n bits can encode any one of 2n values. Qubits can encode these Boolean values along with all their possible superpositions. This gives a quantum computer a potential for parallel processing that has no classical equivalent. So quantum computers—in theory—can solve certain classes of problems that had otherwise been considered computationally infeasible.
An example is finding the prime factors of very large numbers. This happens to be the key to cracking the most widespread cryptographic algorithms in use today, particularly RSA encryption.♦ The world’s Internet commerce depends on it. In effect, the very large number is a public key used to encrypt a message; if eavesdroppers can figure out its prime factors (also large), they can decipher the message. But whereas multiplying a pair of large prime numbers is easy, the inverse is exceedingly difficult. The procedure is an informational one-way street. So factoring RSA numbers has been an ongoing challenge for classical computing. In December 2009 a team distributed in Lausanne, Amsterdam, Tokyo, Paris, Bonn, and Redmond, Washington, used many hundreds of machines working almost two years to discover that 1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413 is the product of 33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489 and 36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917. They estimated that the computation used more than 1020 operations.♦
This was one of the smaller RSA numbers, but, had the solution come earlier, the team could have won a $50,000 prize offered by RSA Laboratories. As far as classical computing is concerned, such encryption is considered quite secure. Larger numbers take exponentially longer time, and at some point the time exceeds the age of the universe.
Quantum computing is another matter. The ability of a quantum computer to occupy many states at once opens new vistas. In 1994, before anyone knew how actually to build any sort of quantum computer, a mathematician at Bell Labs figured out how to program one to solve the factoring problem. He was Peter Shor, a problem-solving prodigy who made an early mark in math olympiads and prize competitions. His ingenious algorithm, which broke the field wide open, is known by him simply as the factoring algorithm, and by everyone else as Shor’s algorithm. Two years later Lov Grover, also at Bell Labs, came up with a quantum algorithm