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
Quantum Physics

Tom’s Top 10 interpretations of quantum mechanics

By Tom Siegfried 12:14pm, February 5, 2014
Quantum mechanics has given birth to dozens of interpretations, which themselves need interpretations.
Physics

Quarks celebrate their 50th anniversary

By Tom Siegfried 4:11pm, January 30, 2014
In a 1997 interview with Context blogger Tom Siegfried, Murray Gell-Mann discussed the origin of the idea for the subatomic particles that he named quarks.
Quantum Physics

Gell-Mann, Hartle spin a quantum narrative about reality

By Tom Siegfried 3:00pm, January 21, 2014
The “consistent histories” approach to quantum physics removes any role for people in creating “quasiclassical” reality.
Quantum Physics

‘QBists’ tackle quantum problems by adding a subjective aspect to science

By Tom Siegfried 8:00am, January 15, 2014
Advocates of a program called “Quantum Bayesianism” take a subjective approach to resolving the paradoxes of quantum physics.
Physics

Google search fails to find any sign of time travelers

By Tom Siegfried 6:08pm, January 3, 2014
A search of the Internet for signs of time travelers from the future fares no better than the party hosted by Stephen Hawking that nobody attended.
Physics

Tom’s top 10 time travel movies

By Tom Siegfried 6:07pm, January 3, 2014
The lack of a credible scientific basis doesn’t stop movie makers from making films about time travel.
History of Science

50 years later, it’s hard to say who named black holes

By Tom Siegfried 3:05pm, December 23, 2013
In 1964, Science News Letter was the first publication to print the term black hole, but nobody is really sure who used the term first.
Cosmology

Cosmic inflation has its flaws, but so do its critics

By Tom Siegfried 4:34pm, December 11, 2013
Philosophical predispositions color efforts to debunk a popular theory about the evolution of the universe.
Numbers

Rise of Big Data underscores need for theory

By Tom Siegfried 2:00pm, December 3, 2013
Big Data can help scientists cope with complex systems, but only with an appreciation of its limits and recognition of the need for theoretical modeling.
Numbers

Why Big Data is bad for science

By Tom Siegfried 1:00pm, November 26, 2013
Big Data is supposed to be a scientific bonanza, but it challenges the capabilities of computer science, statistical tests and perhaps calls for revamping the scientific method itself.
Subscribe to RSS - Context