Zenith Grant Awardee

Jens Eisert

Free University of Berlin

Project Title

Decidable and undecidable in quantum mechanics

Project Summary

Is the number 3571 prime? This is an instance of a decision problem: the answer is either yes or no (here: yes). And even though it may be computationally difficult to come up with a correct answer, one might think that any computer – or mind – should be able to come up with a solution. In seminal work, Alan Turing showed that this is not true: There are decision problems for which no machine and mind can always come to the correct conclusion in finite time. In this proposal, we approach the most fundamental of the physical theories that we know today, quantum mechanics, from the perspective of undecidability. This appears to be a extremely promising arena for research: recent work by us and colleagues shows that there are apparently very simple, natural problems in quantum measurement theory that surprisingly turn out to be undecidable even though the classical analogue is readily decidable. We will develop a new mathematical machinery to investigate undecidability in quantum theory. Apart from a new tool to assess complex quantum systems, our research has potential implications for our world view based on the theory of quantum mechanics and our concept of reality.

Technical Abstract

We aim at bringing research on the complexity of quantum and classical tasks to a new level: We ask what quantum problems are not only computationally hard, but in fact undecidable, i.e., there cannot be an algorithm that always provides the correct answer. In a recent work we were able to show that remarkably, there are simple, natural problems in quantum measurement theory that are undecidable, despite their natural classical analogues being perfectly decidable. Motivated by these and related recent findings, we suggest a concerted research action on undecidability in quantum mechanics. We will develop tools to prove problems in quantum information and many body theory undecidable. This is a high risk endeavor, because there is little intuition for whether the problems we are interested in are decidable or undecidable, but also a possibly very high gain. If successful, a plethora of new directions opens up. Even a solution to the long-standing problem of the existence of NPT bound entanglement seems possible. Maybe more importantly, this research will contribute to a better understanding of the old question of what is (un)speakable in quantum mechanics and potentially has implications for our understanding of reality and our world view.