Search FQXi


RECENT FORUM POSTS

Jason Wolfe: "Start with a fact. The universe used to be small, rolled up about 13.7..." in Bohemian Reality:...

Jason Wolfe: "An afterlife falls into your lap with a few assumptions that are easy for..." in Bohemian Reality:...

Jason Wolfe: "Dear Lorraine, Consciousness in its simplest form will only seek out..." in Wandering Towards a Goal:...

Jason Wolfe: "Mystical religious beliefs are completely justified. it is the scientific..." in Wandering Towards a Goal:...

Joe Fisher: "Dear Foundational Questions Institute Members, Y’all made your initial..." in Our Place in the...

Joe Fisher: "Dear Eugene Lim and Richard Easther, “Undaunted by the lack of tools to..." in Our Place in the...

agaric backlink: "Obat Liver Paling Ampuh Cara Mengobati Bronkitis Paling Ampuh Cara..." in FQXi Essay Contest 2016:...

anil sharma: "Sometimes it is not possible to take care of infant babies especially while..." in FQXi Essay Contest 2016:...


RECENT ARTICLES
click titles to read articles

Our Place in the Multiverse
Calculating the odds that intelligent observers arise in parallel universes—and working out what they might see.

Sounding the Drums to Listen for Gravity’s Effect on Quantum Phenomena
A bench-top experiment could test the notion that gravity breaks delicate quantum superpositions.

Watching the Observers
Accounting for quantum fuzziness could help us measure space and time—and the cosmos—more accurately.

Bohemian Reality: Searching for a Quantum Connection to Consciousness
Is there are sweet spot where artificial intelligence systems could have the maximum amount of consciousness while retaining powerful quantum properties?

Quantum Replicants: Should future androids dream of quantum sheep?
To build the ultimate artificial mimics of real life systems, we may need to use quantum memory.


FQXI ARTICLE
September 25, 2017

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.

LISTEN:

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


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


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?


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

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.