Latest Issue of Science News

Context

Science past and present
Tom Siegfried

Context


Context

Robert Redford film foretold Shor’s quantum computing bombshell

still from the movie "Sneakers"

The star-studded 1992 thriller Sneakers foretold a world in which a computer could decode all the computerized classified data in the world. Two years after the movie came out, mathematician Peter Shor figured out the math that makes cryptography vulnerable to quantum computers.

Sponsor Message

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

Note: To comment, Science News subscribing members must now establish a separate login relationship with Disqus. Click the Disqus icon below, enter your e-mail and click “forgot password” to reset your password. You may also log into Disqus using Facebook, Twitter or Google.

X
Cosmology

Maybe time’s arrow needs ergodicity as well as entropy

By Tom Siegfried 4:46pm, April 1, 2014
Explaining the arrow of time might require an equilibrium universe with hidden ergodic dynamics.
Cosmology,, History of Science

Top 10 cosmological discoveries

By Tom Siegfried 9:34am, March 21, 2014
The cosmic microwave background radiation has played a part in many of cosmology’s greatest discoveries.
Cosmology,, History of Science

Inflation rides gravity waves into cosmological history

By Tom Siegfried 5:15pm, March 17, 2014
The discovery of gravity waves in the cosmic microwave radiation signals the success of inflationary cosmology.
History of Science

Top 10 scientists of the 13th century

By Tom Siegfried 5:39pm, March 14, 2014
Modern science began to emerge in Western Europe centuries before the Scientific Revolution, thanks to a few scholars who were ahead of their time.
History of Science

Medieval cosmology meets modern mathematics

By Tom Siegfried 1:47pm, March 12, 2014
Applying modern math to Robert Grosseteste’s theory of the heavenly spheres reveals a medieval idea’s similarity to modern cosmology.
Physics

Key to free will may be stripping reality naked

By Tom Siegfried 3:48pm, March 3, 2014
If reality emerges from an unseen foundation, human free will could influence the future.
Quantum Physics

Finding a quantum way to make free will possible

By Tom Siegfried 3:27pm, February 26, 2014
Maybe quantum influences from the Big Bang make humans unpredictable, permitting the possibility of free will.
Quantum Physics,, Cosmology

Einstein was wrong about spooky quantum entanglement

By Tom Siegfried 8:28am, February 19, 2014
Einstein’s biggest blunder wasn’t about vacuum energy in space, but in confusing people about quantum entanglement.
Numbers

There’s something suspicious about using statistics to test statistics

By Tom Siegfried 3:15pm, February 11, 2014
The use of statistics to validate medical studies suffers from flaws of faulty assumptions.
Numbers

To make science better, watch out for statistical flaws

By Tom Siegfried 12:30pm, February 7, 2014
Study denying that most medical research papers are wrong may turn out to be wrong.
Subscribe to RSS - Context