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.


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.

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.
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.

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.

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.

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.

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