A famous result by Alan Turing, dating back to 1936, is that a general algorithm solving the halting problem on a Turing machine for all possible inputs and programs cannot exist - the halting problem is undecidable. In this talk I will show that surprisingly simple problems in quantum mechanics can be undecidable in this sense, even if the corresponding classical problem is decidable. Undecidability appears here as a genuine quantum property. This gives a new twist to quantum complexity theory.


Seminar, February 13, 2014, 12:00. Seminar Room

Hosted by Prof. Antonio Acín