Search FQXi


Georgina Woodward: "I wrote " As the EMr has periodic motion it is invariant under..." in Breaking the Universe's...

Georgina Woodward: "That should say: Pythagorean mathematics can be used to compare the seen..." in Breaking the Universe's...

Joe Fisher: "Robert Lawrence Kuhn ℅ Closer To Truth November 17, 2018 Ref: Get out..." in Dissolving Quantum...

Agus uye: "The page is very amazing happy to be on your page I found your page from..." in If the world ended...

Joe Fisher: "Today’s Closer To Truth Facebook page contained this peculiar..." in Dissolving Quantum...

Zimmer man: "Excellent and useful information, thanks for the list. androdumpper apk..." in Neutrino mysteries,...

Edwin Knox: "The genuine Earth had a genuine VISIBLE surface for many years previously..." in Superhuman: Book Review...

Joe Fisher: "Dear Dr. Zeeya Merali, Reality am not a humanly contrived finite..." in Alternative Models of...

click titles to read articles

Dissolving Quantum Paradoxes
The impossibility of building a perfect clock could help explain away microscale weirdness.

Constructing a Theory of Life
An all-encompassing framework of physics could help to explain the evolution of consciousness, intelligence, and free will.

Usurping Quantum Theory
The search is on for a fundamental framework that allows for even stranger links between particles than quantum theory—which could lead us to a theory of everything.

Fuzzballs v Black Holes
A radical theory replaces the cosmic crunchers with fuzzy quantum spheres, potentially solving the black-hole information paradox and explaining away the Big Bang and the origin of time.

Whose Physics Is It Anyway? Q&A with Chanda Prescod-Weinstein
Why physics and astronomy communities must take diversity issues seriously in order to do good science.

November 19, 2018

Searching for the Impossible
A quest to discover which computational tasks can never be resolved.
by Sophie Hebden
FQXi Awardees: Jens Eisert
January 16, 2015
Bookmark and Share

Jens Eisert
Free University of Berlin
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)).

Decidable or Undecidable?

Jens Eisert describes his quest to Sophie Hebden.


Go to full podcast

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

Decidable or undecidable?
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."

We’ve shown that a computational
device cannot give an answer,
so we need to change
the question.
- Jens Eisert
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.

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!
  • Please enter the text of your post, then click the "Submit New Post" button below. You may also optionally add file attachments below before submitting your edits.

  • HTML tags are not permitted in posts, and will automatically be stripped out. Links to other web sites are permitted. For instructions on how to add links, please read the link help page.

  • You may use superscript (10100) and subscript (A2) using [sup]...[/sup] and [sub]...[/sub] tags.

  • You may use bold (important) and italics (emphasize) using [b]...[/b] and [i]...[/i] tags.

  • You may also include LateX equations into your post.

Insert LaTeX Equation [hide]

LaTeX equations may be displayed in FQXi Forum posts by including them within [equation]...[/equation] tags. You may type your equation directly into your post, or use the LaTeX Equation Preview feature below to see how your equation will render (this is recommended).

For more help on LaTeX, please see the LaTeX Project Home Page.

LaTeX Equation Preview

preview equation
clear equation
insert equation into post at cursor

Your name: (optional)

Recent Comments

Hey, you have reached the fantastic place of VIP Delhi Call Girls service. We remain favorite for high profile call girls and High-Class Escorts. Our Apex class of escorts popular among the VIP person in Delhi. We have an exclusive range of the top class escorts to serve you better and best.

Call girls in Delhi

is this not Entscheidungsproblem?


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

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?

read all article comments

Please enter your e-mail address:
Note: Joining the FQXi mailing list does not give you a login account or constitute membership in the organization.