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

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