Latest Issue of Science News


Science past and present
Tom Siegfried



Shor’s code-breaking algorithm inspired reflections on quantum information

Sponsor Message

Second of two parts (read part 1)

When the Robert Redford film Sneakers hit theaters in 1992, most moviegoers had never heard of the Internet. They’d have guessed “World Wide Web” was a horror film involving spiders. And nobody knew that the secret code-breaking box that the Sneakers plot centered on was a quantum computer. All you learned from the movie was that it involved a “shortcut” for solving the mathematical problem on which codes were based.

But then 20 years ago, in 1994, Bell Labs mathematician Peter Shor discovered that shortcut in real life. He showed how a quantum computer — if one could be built — could crack supposedly uncrackable codes. Shor’s discovery electrified the small community of physicists who studied quantum information — the kind of information that quantum computers would process.

Just a few weeks after Shor announced his result, many of the world’s quantum information experts met in Santa Fe, N.M., for a workshop that had been planned months earlier on “Complexity, Entropy and the Physics of Information.”

For five days, about 40 physicists and mathematicians, a philosopher and a journalist (me) attended to presentations on everything from information-swallowing by black holes to chaos in arithmetic. But the bombilation was about Shor’s new method for factoring large numbers, the key to breaking codes.

“It’s a truly dramatic result,” proclaimed Umesh Vazirani a mathematician from the University of California, Berkeley. “This is the first really useful problem that has been shown to be solvable on a quantum computer.”

Among the participants was Benjamin Schumacher of Kenyon College in Ohio. Just two years earlier, he had introduced the key concept of quantum information theory: the quantum bit, or qubit. Just as ordinary computers process bits —1s and 0s — a quantum computer would process qubits. But unlike ordinary bits, always either 0 or 1, a qubit is both 0 and 1 at the same time, with some probability of turning up one way or the other when a measurement is made. In other words, a bit is like a stationary coin, either heads or tails; a qubit is like a flipped coin that is still spinning.

Shor found an algorithm that showed how manipulating qubits could be used to decode encrypted messages. All of a sudden, one of the most esoteric fields of physics became relevant to military communication, financial transactions and governmental espionage. And encryption’s vulnerability to quantum computing raised the profile of another quantum information project, quantum cryptography. Work over the previous decade had shown that quantum information could be used to transmit perfectly secure keys for coding and decoding. In a world with quantum computers, today’s keys used for encrypting messages would be worthless. So the problem became finding a way to make keys immune to quantum computing. “That is exactly what quantum cryptography solves,” Artur Ekert of Oxford University said at the Santa Fe workshop.

But for all the talk of practical applications, the deeper concern at that workshop was the implications of quantum information for understanding the meaning of quantum physics itself. On the first day, John Archibald Wheeler articulated his vision of “It from Bit,” the idea that existence itself is at its roots a manifestation of information.

For Wheeler, quantum physics was about posing questions to nature. Reality arises in the transformation of qubits into bits. Observations convert probabilities into actualities — “iron posts of observation” around which the rest of reality is constructed as if of papier-mâché.

“That leaves us with many questions in the air,” Wheeler acknowledged. “Most of all, where does the whole show come from?”

After all, Wheeler pointed out, making the world from observations always runs into the problem of how you get observers there.

“The issues that trouble me, and for which I have no answer, are, How come existence? How come the quantum?” Wheeler said. “One has hope that one can find reasoning of such a kind to build the whole show from nothing. That would be the dream.”

Wheeler’s concerns led naturally to further discussions of quantum physics and its interpretation, especially with regard to the “quantum measurement problem.” It remains a mystery how an observation transforms possibility into actuality, how the quantum math describing multiple realities allows the sudden shift to only one of the possibilities when a measurement is made. On the workshop’s last day, a general discussion of matters related to the measurement problem revealed a diversity of viewpoints on this issue among the world’s leading experts. Then (as now), after decades of quantum research, its practitioners cannot agree on how to interpret quantum physics.

“I think this discussion shows that quantum measurement is quite a horse,” said Seth Lloyd, now at MIT. “You can beat it for 50 years and it still isn’t dead yet.”

But as Anton Zeilinger, a leading quantum experimentalist, pointed out, multiple interpretations have their value.

“I think all the interpretations are important because for two reasons,” he said. “Number 1, even if they are isomorphic in terms of predictions, they might lead our intuition in a different way. So we might invent different experiments with interpretation A or with interpretation B. And the second reason … is that I still feel that someday we might understand, in John’s (Wheeler’s) words, Why the quantum? And we have not the foggiest idea, I think, which interpretation will finally help us.”

Others took up various points during the discussion. Some involved quantum decoherence, the interaction of the environment with a quantum system. Decoherence destroys the multiple quantum possibilities, leaving one reality, and has been advocated as one way of solving the measurement problem without observers.

The discussion was initiated by John Denker of Bell Labs. He posed a question about projection operators, mathematical expressions involved in representing the quantities that can be observed in a quantum measurement. Much of the ensuing conversation was quite technical. Nevertheless it strikes me as something of important historical interest, as it captured the thoughts of the best quantum thinkers at a key time in quantum history. I transcribed my tape at the time but have never had an opportunity to publish it. So I’m making it available here.

In the two decades since then, the issues raised at the Santa Fe conference have been debated, expanded, pondered, reexamined and revisited over and over again. But they have not been resolved. It seems more likely to me now that a statement at the workshop by Zeilinger was on target. “In my opinion,” he said, “there will never be a solution to the measurement problem.”

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.

Quantum Physics,, Science & Society

Quantum experts discuss the measurement problem: A transcript from 1994

By Tom Siegfried 2:00pm, April 13, 2014
A fairly complete transcript of a discussion about quantum physics on May 19, 1994, the last day of a workshop in Santa Fe, N.M., evolves into a more general discussion of the interpretation of quantum mechanics and the quantum measurement problem.
Quantum Physics,, History of Science

Robert Redford film foretold Shor’s quantum computing bombshell

By Tom Siegfried 1:00pm, April 10, 2014
Twenty years ago, Peter Shor showed how quantum computers could break secret codes, turning the movie Sneakers from fiction to fact.

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.

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.
Subscribe to RSS - Context