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.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.

arXiv:1111.3965Physical Review LettersJun 25, 201250 citations

On the Quantum Measurement Problem

Časlav Brukner

arXiv:1507.05255The frontiers collectionNov 14, 2016152 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**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, 20260 citations

On equivalence, languages equivalence and minimization of multi-letter and multi-letter measure-many quantum automata

Tianrong Lin

We first show that given a $k_1$ -letter quantum finite automata $\mathcal{A}_1$ and a $k_2$ -letter quantum finite automata $\mathcal{A}_2$ over the same input alphabet $Σ$ , they are equivalent if and only if they are $(n_1^2+n_2^2-1)|Σ|^{k-1}+k$ -equivalent where $n_1$ , $i=1,2$ , are the numbers of state in $\mathcal{A}_i$ respectively, and $k=\max\{k_1,k_2\}$ . By applying a method, due to the author, used to deal with the equivalence problem of {\it measure many one-way quantum finite automata}, we also show that a $k_1$ -letter measure many quantum finite automaton $\mathcal{A}_1$ and a $k_2$ -letter measure many quantum finite automaton $\mathcal{A}_2$ are equivalent if and only if they are $(n_1^2+n_2^2-1)|Σ|^{k-1}+k$ -equivalent where $n_i$ , $i=1,2$ , are the numbers of state in $\mathcal{A}_i$ respectively, and $k=\max\{k_1,k_2\}$ . Next, we study the language equivalence problem of those two kinds of quantum finite automata. We show that for $k$ -letter quantum finite automata, the non-strict cut-point language equivalence problem is undecidable, i.e., it is undecidable whether $L_{\geqλ}(\mathcal{A}_1)=L_{\geqλ}(\mathcal{A}_2)$ where $0<λ\leq 1$ and $\mathcal{A}_i$ are $k_i$ -letter quantum finite automata. Further, we show that both strict and non-strict cut-point language equivalence problem for $k$ -letter measure many quantum finite automata are undecidable. The direct consequences of the above outcomes are summarized in the paper. Finally, we comment on existing proofs about the minimization problem of one way quantum finite automata not only because we have been showing great interest in this kind of problem, which is very important in classical automata theory, but also due to that the problem itself, personally, is a challenge. This problem actually remains open.We first show that given a $k_1$-letter quantum finite automata $\mathcal{A}_1$ and a $k_2$-letter quantum finite automata $\mathcal{A}_2$ over the same input alphabet $Σ$, they are equivalent if and only if they are $(n_1^2+n_2^2-1)|Σ|^{k-1}+k$-equivalent where $n_1$, $i=1,2$, are the numbers of state in $\mathcal{A}_i$ respectively, and $k=\max\{k_1,k_2\}$. By applying a method, due to the author, used to deal with the equivalence problem of {\it measure many one-way quantum finite automata}, we also show that a $k_1$-letter measure many quantum finite automaton $\mathcal{A}_1$ and a $k_2$-letter measure many quantum finite automaton $\mathcal{A}_2$ are equivalent if and only if they are $(n_1^2+n_2^2-1)|Σ|^{k-1}+k$-equivalent where $n_i$, $i=1,2$, are the numbers of state in $\mathcal{A}_i$ respectively, and $k=\max\{k_1,k_2\}$. Next, we study the language equivalence problem of those two kinds of quantum finite automata. We show that for $k$-letter quantum finite automata, the non-strict cut-point language equivalence problem is undecidable, i.e., it is undecidable whether $L_{\geqλ}(\mathcal{A}_1)=L_{\geqλ}(\mathcal{A}_2)$ where $0<λ\leq 1$ and $\mathcal{A}_i$ are $k_i$-letter quantum finite automata. Further, we show that both strict and non-strict cut-point language equivalence problem for $k$-letter measure many quantum finite automata are undecidable. The direct consequences of the above outcomes are summarized in the paper. Finally, we comment on existing proofs about the minimization problem of one way quantum finite automata not only because we have been showing great interest in this kind of problem, which is very important in classical automata theory, but also due to that the problem itself, personally, is a challenge. This problem actually remains open.

arXiv:1203.0113Mar 1, 20120 citations

We first show that given a

k_1

-letter quantum finite automata

\mathcal{A}_1

and a

k_2

-letter quantum finite automata

\mathcal{A}_2

over the same input alphabet

Σ

, they are equivalent if and only if they are

(n_1^2+n_2^2-1)|Σ|^{k-1}+k

-equivalent where

n_1

i=1,2

, are the numbers of state in

\mathcal{A}_i

respectively, and

k=\max\{k_1,k_2\}

. By applying a method, due to the author, used to deal with the equivalence problem of {\it measure many one-way quantum finite automata}, we also show that a

k_1

-letter measure many quantum finite automaton

\mathcal{A}_1

and a

k_2

-letter measure many quantum finite automaton

\mathcal{A}_2

are equivalent if and only if they are

(n_1^2+n_2^2-1)|Σ|^{k-1}+k

-equivalent where

n_i

i=1,2

, are the numbers of state in

\mathcal{A}_i

respectively, and

k=\max\{k_1,k_2\}

. Next, we study the language equivalence problem of those two kinds of quantum finite automata. We show that for

k

-letter quantum finite automata, the non-strict cut-point language equivalence problem is undecidable, i.e., it is undecidable whether

L_{\geqλ}(\mathcal{A}_1)=L_{\geqλ}(\mathcal{A}_2)

where

0<λ\leq 1

and

\mathcal{A}_i

are

k_i

-letter quantum finite automata. Further, we show that both strict and non-strict cut-point language equivalence problem for

k

-letter measure many quantum finite automata are undecidable. The direct consequences of the above outcomes are summarized in the paper. Finally, we comment on existing proofs about the minimization problem of one way quantum finite automata not only because we have been showing great interest in this kind of problem, which is very important in classical automata theory, but also due to that the problem itself, personally, is a challenge. This problem actually remains open.