The Information (71 page)
9666
511279233373417143396810270092798736308917. They estimated that the computation used more than 10
20
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 for searching a vast unsorted database. That is the canonical hard problem for a world of limitless information—needles and haystacks.
“Quantum computers were basically a revolution,”
♦
Dorit Aharonov of Hebrew University told an audience in 2009. “The revolution was launched into the air by Shor’s algorithm. But the
reason
for the revolution—other than the amazing practical implications—is that they redefine what is an
easy
and what is a
hard
problem.”
What gives quantum computers their power also makes them exceedingly difficult to work with. Extracting information from a system means observing it, and observing a system means interfering with the quantum magic. Qubits cannot be watched as they do their exponentially many operations in parallel; measuring that shadow-mesh of possibilities reduces it to a classical bit. Quantum information is fragile. The only way to learn the result of a computation is to wait until after the quantum work is done.
Quantum information is like a dream—evanescent, never quite existing as firmly as a word on a printed page. “Many people can read a book and get the same message,” Bennett says, “but trying to tell people about your dream changes your memory of it, so that eventually you forget the dream and remember only what you said about it.”
♦
Quantum erasure, in turn, amounts to a true undoing: “One can fairly say that even God has forgotten.”
As for Shannon himself, he was unable to witness this flowering of the seeds he had planted. “If Shannon were around now, I would say he would be very enthusiastic about the entanglement-assisted capacity of a channel,”
♦
says Bennett. “The same form, a generalization of Shannon’s formula, covers both classic and quantum channels in a very elegant way. So it’s pretty well established that the quantum generalization of classical
information has led to a cleaner and more powerful theory, both of computing and communication.” Shannon lived till 2001, his last years dimmed and isolated by the disease of erasure, Alzheimer’s. His life had spanned the twentieth century and helped to define it. As much as any one person, he was the progenitor of the information age. Cyberspace is in part his creation; he never knew it, though he told his last interviewer, in 1987, that he was investigating the idea of mirrored rooms: “to work out all the possible mirrored rooms that make sense, in that if you looked everywhere from inside one, space would be divided into a bunch of rooms, and you would be in each room and this would go on to infinity without contradiction.”
♦
He hoped to build a gallery of mirrors in his house near MIT, but he never did.
It was John Wheeler who left behind an agenda for quantum information science—a modest to-do list for the next generation of physicists and computer scientists together:
♦
“Translate the quantum versions of string theory and of Einstein’s geometrodynamics from the language of continuum to the language of bit,” he exhorted his heirs.
“Survey one by one with an imaginative eye the powerful tools that mathematics—including mathematical logic—has won … and for each such technique work out the transcription into the world of bits.”
And, “From the wheels-upon-wheels-upon-wheels evolution of computer programming dig out, systematize and display every feature that illuminates the level-upon-level-upon-level structure of physics.”