Quantum measurement occurrence is undecidable

Printer-friendly versionSend by emailPDF version

J. Eisert, M. P. Mueller, C. Gogolin



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. Formally, an undecidable problem is a decision problem for which one cannot construct a single algorithm that will always provide a correct answer in finite time. In this work, we show that surprisingly, very natural, apparently simple problems in quantum measurement theory can be undecidable even if their classical analogues are decidable. Undecidability appears as a genuine quantum property. The problem we consider is to determine whether sequentially used identical Stern-Gerlach-type measurement devices, giving rise to a tree of possible outcomes, have outcomes that never occur. Finally, we point out implications for measurement-based quantum computing and studies of quantum many-body models and suggest that a plethora of problems may indeed be undecidable.