title: Quantum measurement occurrence is undecidable.
abstract: In this work, we show that very natural, apparently simple problems in quantum measurement theory can be undecidable even if their classical analogues are decidable. Undecidability hence appears as a genuine quantum property here. 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. 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.
authors.affiliation: Qmio Group, Dahlem Center for Complex Quantum Systems, Freie Universität Berlin, 14195 Berlin, Germany.
authors.forename: J
authors.initials: J
authors.lastname: Eisert
authors.forename: M P
authors.initials: MP
authors.lastname: Müller
authors.forename: C
authors.initials: C
authors.lastname: Gogolin