Robert Redford film foretold Shor’s quantum computing bombshell

First of two parts

Long before scientists were talking much about it, Robert Redford fans learned about the power of quantum computers.

It was 1992. A goofy movie called Sneakers warned about the dangers of computers and the massive amounts of encrypted information they controlled. Redford and cohorts acquired a small box, disguised as an answering machine, that was able to decode all the computerized classified data in the world.

“Cryptography systems are based on mathematical problems so complex that they cannot be solved without a key,” said David Strathairn, playing the part of one of Redford’s accomplices. Somehow a mathematician named Gunter Janek programmed a chip inside the answering machine box to solve such problems.

When Sneakers appeared in theaters, nobody had any idea how such a chip would work. Less than two years later, though, a Bell Labs mathematician duplicated the discovery of the fictional Gunter Janek. Twenty years ago this month, Peter Shor figured out the math that made cryptography vulnerable to quantum computers.

Of course, there was no such thing as a quantum computer back then. It was just an idea, discussed in the early 1980s by Richard Feynman and even before then by Paul Benioff. If you could harness the power of quantum weirdness, those physicists surmised, you could do computing in ways that ordinary classical computers couldn’t. In 1985, the physicist David Deutsch pointed out that quantum computing could be very fast — it would be like computing in many universes at once. (In fact, he thought you really would be computing in many universes at once.)

It was all very interesting, but nobody thought quantum computers would put IBM out of business. For one thing, it wasn’t clear that they offered advantages for any particular practical problem. You could imagine problems where quantum computers would be fast but not very helpful. Your quantum computer might work five times faster than your Mac, for instance, but it would give the correct answer only one-fifth of the time. You had to be lucky enough to be in the right universe to get the correct answer.

But then Shor dropped a bombshell. He found the quantum computer’s killer app: factoring.

Factoring is the complex mathematical problem alluded to in Sneakers. Factoring is the basis for the standard encryption method used to encode most government, military and commercial computer communication and data. You can encrypt the data using a very long number, with hundreds of digits. But you can break the code to read encrypted data only if you know the two prime factors that, when multiplied together, yield that long encoding number.

For small numbers, factoring is pretty easy. Take 35, for instance. It is the product of two prime numbers, 5 and 7. You shouldn’t use 35 to create a code, though, because its factors have just been revealed in the preceding sentence. Or somebody could use a calculator.

But for numbers with several hundred digits, finding the two primes would take several hundred supercomputers several hundred times the age of the universe. That’s why everybody thought standard encryption was so safe, and that Sneakers was silly. But in the film itself, Gunter Janek alluded to the possibility of a mathematical surprise. “There exists an intriguing possibility for a far more elegant approach” to factoring large numbers, Janek said. “It would be a breakthrough of Gaussian proportions.”

In the movie, of course, Janek did solve the factoring problem and was promptly killed. A year and a half later Shor solved the same problem and was promptly immortalized. (It’s probably a good thing that he had not seen Sneakers.)  

Shor started working on his factoring algorithm in 1993. In April 1994, he gave a talk at Bell Labs on a related algorithm for computing logarithms. A few days later he worked out the key to quantum factoring. Soon his paper describing the factoring algorithm was circulating around the Internet.

Shor’s paper showed how to combine the ordinary mathematical methods for finding prime factors with a trick that could be performed only on a quantum computer. It involved finding the period of a periodic function — a mathematical expression that repeats its answer at specific intervals, or periods. In Shor’s formulation of the problem, it’s (relatively) easy to find the prime factors if you know the period of the function. But it would take forever to find that period with ordinary computers.

With a quantum computer, though, you could solve the problem much faster — maybe days, or hours, or minutes, instead of billions of years. And the best part was you would be very likely to get the right answer. A quantum computer could in fact generate billions of answers, but almost all of them would be wiped out by quantum interference, kind of like the way noise-canceling headphones dampen sound waves. The remaining answer provided the period, which could then be used to calculate the primes.

Once Shor’s paper was widely distributed, the secret was out and a Sneakers scenario loomed, except for one small snag. Neither IBM nor Apple nor anybody else sold quantum computers.

“Currently, nobody knows how to build a quantum computer,” Shor wrote in his 1994 paper. “It is hoped that this paper will stimulate research on whether it is feasible to actually construct one.”

It did, of course. In the intervening two decades, quantum computing has become one of the hottest topics in both quantum physics and computer science. Rudimentary quantum computers have been built and have successfully factored numbers like 15 and 21. (Claims of success with bigger numbers have been disputed.) That’s quite a way short of the Sneakers scenario, but in real life progress is usually slower than in movies.

But Shor’s algorithm didn’t just inspire a new type of technology. It generated intellectual impetus for a new field of scientific study called quantum information theory. A few weeks after Shor’s revelation, the leaders of the emerging quantum information field met in Santa Fe to ponder the notion that quantum reality was built on an information foundation. I was there. So don’t miss Part 2.

Follow me on Twitter: @tom_siegfried