Searching for the Impossible

Physicist Jens Eisert likens himself to Sherlock Holmes. The fictional sleuth was famously preoccupied with eliminating the impossible in his hunt for the truth. Eisert is involved in a similar quest: eliminating "undecidable" problems that cannot, even in theory, ever be resolved by a computer.

In particular, Eisert, who is based at the Free University of Berlin, is interested in the quantum world, and how we understand and describe tasks in terms of their computational complexity. So far, he says he has found "the most crazy, the most extreme forms of difference," where a problem is perfectly decidable in the classical world, and not just hard, but undecidable in the quantum world. The approach could, for instance, help physicists exploiting quantum properties for securely encoding data.

As a starting point, Eisert considered a historic experiment that’s often taught in beginner quantum physics classes to explain one of the weirdest aspects of the subatomic world. In their original 1922 experiment Otto Stern and Walter Gerlach directed a beam of atoms through a non-uniform magnetic field, which exerts a force on the atoms because they possess an intrinsic angular momentum, similar to that of a spinning football. But unlike a football, in the quantum world this angular momentum—which we call ’spin’—can only take certain discrete values. As a result the atoms were deflected upward or downward according to the orientation of their spin by discrete amounts, producing two distinct bright spots on a glass plate detector.

Empty Port

Eisert considered a thought experiment in which a series of Stern Gerlach devices with five possible deflections—or output ports—are chained together so that an atom flying out of one device is fed into the input for the next device. His question was: Is it possible to construct an algorithm to compute whether there is an empty port, a value that an atom will never take?

In the quantum case, atoms can be in superpositions of multiple different states at the same time. The probabilities of the atoms’ state on exiting each round of the experiment must take this into account. This net effect ends up being so complex that the problem is undecidable (Phys. Rev. Lett. 108, 260501 (2012)).

To show that this undecidability is a genuinely quantum feature, Eisert and his colleagues Christian Gogolin, then also at the Free University of Berlin, and Markus Mueller of Heidelberg University in Germany, compared the situation with the "classical" case, in which the experiment was repeated without any quantum weirdness. In this case, the devices just make classical measurements, and the atoms have set states on exiting each round of the experiment, rather than existing in superpositions. This changes the mathematics for describing how the devices work, honing it down to a subset of the quantum behaviour, which makes the problem decidable.

This is the first time that someone has made a connection between physical devices and undecidability, says quantum physicist Steve Flammia, who works at the University of Sydney and has collaborated with Eisert on various projects since 2008. "This sort of split—between the quantum and classical version of the problem—this is the novel thing here and is what makes this work most interesting," Flammia says.

Scott Aaronson, a computer scientist at MIT and an FQXi member, agrees: "I’m a very big fan, especially since Eisert and his colleagues were able to show that the analogous classical problems are decidable."

Eisert describes himself as hyperactive, and Flammia, whole-heartedly agrees. "I’d say his productivity is his key strength," adds Flammia. "He is an expert at using every crack of time in the day."

Flammia recalls working out a problem, with Eisert, on the blackboard. "I looked back at him and saw that he was fiddling with his phone, so I asked whether he was paying attention, and he said, ’oh hang on, I’m just submitting this paper.’ He is always multi-tasking, to the point of annoyance!" laughs Flammia.

Another physical example of undecidability, presented at a conference this year in Barcelona by Toby Cubitt of the University of Cambridge, relates to the energy states of atoms in any sort of lattice structure, like the surface of a metal or crystal. In the quantum world an atom’s electrons can only exist at discrete energy levels, and if there is a large gap between the lowest energy level for those atoms in the lattice and the next energy level, it is said to have a "spectral gap." Such a gap affects the properties of the material and is important, for example, in the physics of semi-conductor devices used in electronics.

"Deciding whether a quantum many-body system has a gap or not is a very physical, very practical and very important problem. But for very foundational reasons, in some instances, it is undecidable," says Eisert. What does this mean? Eisert says it has implications for the sorts of questions that we pose of many-body systems. "Asking about a gap is not really a well-defined question," he says. "We’ve shown that a computational device cannot give an answer, so we need to change the question or reconfigure some definitions."

With the help of a $50,000 grant from FQXi, Eisert is turning his attention to another problem, which he says, "has the right smell of an undecidable problem," and is one of the big open questions relating to securely encrypting data for transmission using quantum key distribution. One such cryptographic protocol, for instance, exploits quantum entanglement—in which two photons are linked so that disturbing one immediately affects its partner. In this case, a secure cryptographic key is generated by sharing pairs of entangled photons between two legitimate parties. If an eavesdropper intercepts one of the pair, the disturbance will disrupt the system in a noticeable way, alerting the users that the system has been breached.

But photons that have been sent down an optical fibre channel between communicating parties can be subjected to noise. If the states of the photons deteriorate, so that they are no longer entangled fully, this could threaten security. "A big question that emerged about 15 years ago is under what circumstances can such states be transformed, in this composite context, into maximally entangled states again?" says Eisert. No one has ever solved the problem, but is that because it is truly undecidable, as Eisert suspects or just very hard?

"If there were such a connection, that would be extremely interesting," says Flammia. But Flammia says he would be surprised if it proves to be an undecidable problem.

And if it is not undecidable? Well, then to paraphrase Sherlock Holmes, once you’ve eliminated the undecidable, what’s left, no matter how hard, must be worth investigating further.