RECENT ARTICLES

A meditating mathematician is developing a theory of conscious experience to help understand the boundary between the quantum and classical world.

Underground experiments in the heart of the Italian mountains are testing the links between consciousness and collapse theories of quantum physics.

Calculating the energy needed to acquire and compute information could help explain the (in)efficiency of human brains and guide the search for extra-terrestrial intelligence.

Using precision thermometry to make mini heat engines, that might, momentarily, bust through the thermodynamic limit.

Using neural networks to test definitions of 'autonomy.'

FQXI ARTICLE

May 24, 2022

Searching for the Impossible

A quest to discover which computational tasks can never be resolved.

FQXi Awardees: Jens Eisert

January 16, 2015

Jens Eisert

Free University of Berlin

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

Jens Eisert describes his quest to Sophie Hebden.

LISTEN:

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

Decidable or undecidable?

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

We’ve shown that a computational

device cannot give an answer,

so we need to change

the question.

device cannot give an answer,

so we need to change

the question.

- Jens Eisert

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.

Comment on this Article

Please read the important Introduction that governs your participation in this community. Inappropriate language will not be tolerated and posts containing such language will be deleted. Otherwise, this is a free speech Forum and all are welcome!

Recent Comments

read all article comments

Please read the important Introduction that governs your participation in this community. Inappropriate language will not be tolerated and posts containing such language will be deleted. Otherwise, this is a free speech Forum and all are welcome!

Recent Comments

JAY wrote on February 28, 2015

is this not Entscheidungsproblem?

or

I don't know if I can decide

calculus, Church–Turing thesis, proving the undecidability of the Entscheidungsproblem, Frege–Church ontology, and the Church–Rosser theorem

is this not Entscheidungsproblem?

or

I don't know if I can decide

calculus, Church–Turing thesis, proving the undecidability of the Entscheidungsproblem, Frege–Church ontology, and the Church–Rosser theorem

CHRISTOPHER INMAN wrote on January 25, 2015

I thought it had been decided that the relationship between was set at the generation of the entangled particles and so one particle did not, in itself, change when the other was read. Is there a difference between determining a state and discovering a state?

I thought it had been decided that the relationship between was set at the generation of the entangled particles and so one particle did not, in itself, change when the other was read. Is there a difference between determining a state and discovering a state?

JOHN R. COX wrote on January 23, 2015

Robert,

from your essay: "However, any mathematical description of the 'state' [sic; spin] of the entity to be observed must take into account that the state depends on the aspect angle from which the entity is to be observed."

I see better now, your argument that a high degree of surety can be found for the otherwise Fourier unknown frequency window. Fred Gauss really got around, if you'll pardon the pun. If we look at the few Platonic solids from which we could construct...

Robert,

from your essay: "However, any mathematical description of the 'state' [sic; spin] of the entity to be observed must take into account that the state depends on the aspect angle from which the entity is to be observed."

I see better now, your argument that a high degree of surety can be found for the otherwise Fourier unknown frequency window. Fred Gauss really got around, if you'll pardon the pun. If we look at the few Platonic solids from which we could construct...

read all article comments