Parts | Days | Selection | Search | Updates | Downloads | Help

MP: Fachverband Theoretische und Mathematische Grundlagen der Physik

MP 17: Quanteninformation II

MP 17.2: Talk

Thursday, March 1, 2012, 15:25–15:50, ZHG 003

Undecidability as a genuine quantum property — Jens Eisert¹, Markus P. Müller², and •Christian Gogolin¹ — ¹Dahlem Center for Complex Quantum Systems, Freie Universität Berlin, 14195 Berlin, Germany — ²Perimeter Institute for Theoretical Physics, 31 Caroline Street North, Waterloo, ON N2L 2Y5, Canada

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 it will be shown 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, which has up to now mostly been concerned with quantitative separations between quantum and classical physics in terms of hardness.