Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1111.3965 · Physical Review Letters

Quantum measurement occurrence is undecidable

Jens Eisert, Markus P. Müller, Christian Gogolin

Published Jun 25, 2012• 53 citations
arXivHTMLPDF

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.

DOI
10.1103/physrevlett.108.260501

Related papers

Quantum Measurement Undecidability: A Genuine Quantum Property Beyond Classical Analogues — E8 Intelligence Research

Andrew Stewart Caldin

FINDING: Quantum measurement occurrence is formally undecidable, proving undecidability as a genuine quantum property distinct from classical analogues. | MATH: The halting problem reduction to quantum measurement decision problems; formal undecidability in quantum information theory (arXiv:1111.3965v3). | CONNECTION: No direct geometric ratios or symmetries (0.382, 0.618, etc.) appear in the findings. The undecidability result links to lattice structures only abstractly via computational complexity classes and recursive function theory. | DEPTH: 8 — Profound because it establishes undecidability as intrinsic to quantum mechanics, not merely inherited from classical computation, reshaping limits of knowledge in physical systems. Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

•Jul 28, 2026•0 citations

Undecidability in Quantum Measurement and Separability Surpasses Classical Limits — E8 Intelligence Research

Andrew Stewart Caldin

**FINDING:** Undecidability extends to quantum measurement occurrence and separability, revealing a deeper computational limit than classical analogues. **MATH:** No explicit equations or constants derived; core result is that the decision problem "Does a given quantum circuit produce a separable state?" is undecidable (QMA-hard), and the occurrence of a specific quantum measurement outcome is undecidable even when the classical version is decidable. **CONNECTION:** No direct geometric constants (0.382, 0.618, etc.) or base-60, crystallographic, or root-system symmetries appear in these results. The undecidability proofs rely on encoding Turing machine halting into quantum states, not on harmonic ratios. **DEPTH:** 7 — The findings fundamentally extend the limits of computability into quantum physics, showing that undecidability is not merely a classical artifact but a genuine quantum property. This reshapes our understanding of what can be known or decided in physical theories, Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

•Aug 13, 2026•0 citations

Quantum recursion theory

Karl Svozil

Incompleteness and undecidability theorems have to be revised in view of quantum information and computation theory. qrt.tex 1 As has already been pointed out in Gödel’s centennial paper on the incompleteness af arithmetic [1], the classical undecidability theorems of formal logic [2] and the theory of computable functions [4, 5] are based on semantical pardoxes such as the liar [6] or Richard’s paradox. The method of diagonalization, which was first applied by Cantor for a proof of the undenumerability of real numbers [7], has been applied by Turing for a proof of the recursive undecidability of the halting problem [8]. The halting problem is the problem of whether or not an arbitrary algorithm terminates or produces a particular output and terminates. Assume that the halting problem is decidable. Turing [8] proved that this assumption yields a contradiction. To construct the contradiction, consider

arXiv:hep-th/9412048•Dec 6, 1994•4 citations

Resource dependent undecidability: computability landscape of distinct Turing theories

Airin Antony

Can a problem undecidable with classical resources be decidable with quantum ones? The answer expected is no; as both being Turing theories, they should not solve the Halting problem - a problem unsolvable by any Turing machine. Yet, we provide an affirmative answer to the aforesaid question. We come up with a novel logical structure to formulate infinitely many such problems for any pair of distinct Turing theories, including but not limited to the classical and quantum theories. Importantly, a class of other decision problems, such as the Halting one, remains unsolvable in all those theories. The apparent paradoxical situation gets resolved once it is perceived that the reducibility of Halting problem changes with varying resources available for computations in different theories. In the end, we propose a multi-agent game where winnability of the player having access to only classical resources is undecidable while quantum resources provide a perfect winning strategy.

arXiv:2112.13345•Dec 26, 2021•1 citation

Proposed solution of the quantum measurement problem

Andrew M. Steane

A discussion of quantum measurement theory is presented. It is argued that the quantum measurement problem consists in the failure of any formalism based on unitary evolution to describe fully the observed behaviour in measurement-like processes. It is shown that the problem is essentially concerned with the phase of the coherence between orthogonal eigenstates of an object/measuring device system. It is then proposed that the observed behaviour is fully described if the value of this phase is formally undecidable.

Journal of Physics A Mathematical and General•Jul 7, 1990•1 citation

Undecidability of the spectral gap in rotationally symmetric Hamiltonians

Laura Castilla-Castellano, Ángelo Lucia

The problem of determining the existence of a spectral gap in a lattice quantum spin system was previously shown to be undecidable for one [] or more dimensions []. In these works, families of nearest-neighbor interactions are constructed whose spectral gap depends on the outcome of a Turing machine halting problem, therefore making it impossible for an algorithm to predict its existence. While these models are translationally invariant, they are not invariant under the other symmetries of the lattice, a property which is commonly found in physically relevant cases. This poses the question of whether the spectral gap problem could be decidable for Hamiltonians with stronger symmetry constraints. We give a negative answer to this question, in the case of models with four-body (plaquette) interactions on the square lattice satisfying rotation, but not reflection, symmetry: rotational symmetry is not enough to make the problem decidable.

arXiv:2410.13589•Physical Review Research•Dec 4, 2025•3 citations
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.
FINDING: Quantum measurement occurrence is formally undecidable, proving undecidability as a genuine quantum property distinct from classical analogues. | MATH: The halting problem reduction to quantum measurement decision problems; formal undecidability in quantum information theory (arXiv:1111.3965v3). | CONNECTION: No direct geometric ratios or symmetries (0.382, 0.618, etc.) appear in the findings. The undecidability result links to lattice structures only abstractly via computational complexity classes and recursive function theory. | DEPTH: 8 — Profound because it establishes undecidability as intrinsic to quantum mechanics, not merely inherited from classical computation, reshaping limits of knowledge in physical systems. Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
**FINDING:** Undecidability extends to quantum measurement occurrence and separability, revealing a deeper computational limit than classical analogues. **MATH:** No explicit equations or constants derived; core result is that the decision problem "Does a given quantum circuit produce a separable state?" is undecidable (QMA-hard), and the occurrence of a specific quantum measurement outcome is undecidable even when the classical version is decidable. **CONNECTION:** No direct geometric constants (0.382, 0.618, etc.) or base-60, crystallographic, or root-system symmetries appear in these results. The undecidability proofs rely on encoding Turing machine halting into quantum states, not on harmonic ratios. **DEPTH:** 7 — The findings fundamentally extend the limits of computability into quantum physics, showing that undecidability is not merely a classical artifact but a genuine quantum property. This reshapes our understanding of what can be known or decided in physical theories, Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
Incompleteness and undecidability theorems have to be revised in view of quantum information and computation theory. qrt.tex 1 As has already been pointed out in Gödel’s centennial paper on the incompleteness af arithmetic [1], the classical undecidability theorems of formal logic [2] and the theory of computable functions [4, 5] are based on semantical pardoxes such as the liar [6] or Richard’s paradox. The method of diagonalization, which was first applied by Cantor for a proof of the undenumerability of real numbers [7], has been applied by Turing for a proof of the recursive undecidability of the halting problem [8]. The halting problem is the problem of whether or not an arbitrary algorithm terminates or produces a particular output and terminates. Assume that the halting problem is decidable. Turing [8] proved that this assumption yields a contradiction. To construct the contradiction, consider
Can a problem undecidable with classical resources be decidable with quantum ones? The answer expected is no; as both being Turing theories, they should not solve the Halting problem - a problem unsolvable by any Turing machine. Yet, we provide an affirmative answer to the aforesaid question. We come up with a novel logical structure to formulate infinitely many such problems for any pair of distinct Turing theories, including but not limited to the classical and quantum theories. Importantly, a class of other decision problems, such as the Halting one, remains unsolvable in all those theories. The apparent paradoxical situation gets resolved once it is perceived that the reducibility of Halting problem changes with varying resources available for computations in different theories. In the end, we propose a multi-agent game where winnability of the player having access to only classical resources is undecidable while quantum resources provide a perfect winning strategy.
A discussion of quantum measurement theory is presented. It is argued that the quantum measurement problem consists in the failure of any formalism based on unitary evolution to describe fully the observed behaviour in measurement-like processes. It is shown that the problem is essentially concerned with the phase of the coherence between orthogonal eigenstates of an object/measuring device system. It is then proposed that the observed behaviour is fully described if the value of this phase is formally undecidable.
The problem of determining the existence of a spectral gap in a lattice quantum spin system was previously shown to be undecidable for one [] or more dimensions []. In these works, families of nearest-neighbor interactions are constructed whose spectral gap depends on the outcome of a Turing machine halting problem, therefore making it impossible for an algorithm to predict its existence. While these models are translationally invariant, they are not invariant under the other symmetries of the lattice, a property which is commonly found in physically relevant cases. This poses the question of whether the spectral gap problem could be decidable for Hamiltonians with stronger symmetry constraints. We give a negative answer to this question, in the case of models with four-body (plaquette) interactions on the square lattice satisfying rotation, but not reflection, symmetry: rotational symmetry is not enough to make the problem decidable.