Search FQXi


RECENT FORUM POSTS

Cristinel Stoica: "Dear Lorraine, I'm sorry to disappoint you, but QBism gives the humans..." in Wandering Towards a Goal:...

Steven Andresen: "I note your reservations. What I propose doesn’t change the observations..." in Alternative Models of...

Georgina Woodward: "Lorraine, did you read "Georgina Woodward replied on Jul. 22, 2017 @ 03:14..." in Wandering Towards a Goal:...

Georgina Woodward: "Hi Steven, I can only speak for myself. I am uncertain of my ability to..." in Alternative Models of...

sridattadev kancharla: "Dear All, Using Imaginary part of s in the e power yields correct..." in FQXi Essay Contest 2016:...

sridattadev kancharla: "Dear All, I am using Sign function to determine the direction of..." in FQXi Essay Contest 2016:...

Cohen Geoffrey: "The origin of life on planet Earth A "cosmic cloud" falls from infinite..." in Biological Creativity

Georgina Woodward: "In the example of a spinning ball that was given it should be assumed that..." in The Reality of the...


RECENT ARTICLES
click titles to read articles

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.

Painting a QBist Picture of Reality
A radical interpretation of physics makes quantum theory more personal.

The Spacetime Revolutionary
Carlo Rovelli describes how black holes may transition to "white holes," according to loop quantum gravity, a radical rewrite of fundamental physics.


FQXI ARTICLE
July 23, 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)



Important: In order to combat spam, please select the letter in this menu between 'I' and 'K':




Recent Comments


Thanks a lot for the post. It has helped me get some nice ideas. I hope I will see some really good result soon. [url=http://getcracksoft.com/]http://getcracksoft.com/[/url]


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?

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.