Quantum measurement occurrence is undecidable
arXiv:1111.3965 · doi:10.1103/PhysRevLett.108.260501
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.
4+ pages, 1 figure, added a proof that the QMOP is still undecidable for exponentially small but nonzero probability
References in corpus (4)
Cited by in corpus (30)
- Undecidability of the Spectral Gap (short version)
- Matrix product operators and states: NP-hardness and undecidability
- Quantum POMDPs
- Tensor Network Contractions for #SAT
- Undecidability of the Spectral Gap in One Dimension
- Quantum evolution in the stroboscopic limit of repeated measurements
- Undecidability of the fate of relaxation in one-dimensional quantum systems
- Undecidability in quantum thermalization
- Universality of Sequential Quantum Measurements
- Are problems in Quantum Information Theory (un)decidable?
- Debugging Quantum Processes Using Monitoring Measurements
- Undecidability in Tensor Network States
- Uncomputability and complexity of quantum control
- Epistemic Horizons and the Foundations of Quantum Mechanics
- Undecidability of the Spectral Gap (full version)
- A quantum information approach to statistical mechanics
- Halos and undecidability of tensor stable positive maps
- Undecidability in Physics: a Review
- Many bounded versions of undecidable problems are NP-hard
- Model Checking Quantum Systems --- A Survey
- (Un)decidable Problems about Reachability of Quantum Systems
- Can quantum gravity be both consistent and complete?
- A smallest computable entanglement monotone
- The Inferential Design of Entropy and its Application to Quantum Measurements
- Quantum Tensor Networks, Stochastic Processes, and Weighted Automata
- Unprovability of First Maxwell's Equation in Light of EPR's Completeness Condition -- A Computational Approach from Logico-linguistic Perspective
- The Undecidable Charge Gap and the Oil Drop Experiment
- A Note on Quantum Markov Models
- Embodied observations from an intrinsic perspective can entail quantum dynamics
- Undecidability of the spectral gap in rotationally symmetric Hamiltonians