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:quant-ph/0610047 · International Journal of Theoretical Physics

Unsolvability of the Halting Problem in Quantum Dynamics

Daegene Song

Published Dec 6, 2007• 7 citations
arXivHTMLPDF
DOI
10.1007/s10773-007-9621-x

Related papers

Theory of Quantum Computing and its Analog of the Halting Problem

Andrii Hopanchuk

•Jan 1, 2025•0 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

Quantum Entanglement Proves Undecidability: MIP*=RE Deepens Computation's Limits — E8 Intelligence Research

Andrew Stewart Caldin

FINDING: The halting problem's undecidability is foundational to computation limits; recent MIP*=RE result shows quantum entanglement can encode undecidable problems, deepening the boundary of knowability. | MATH: Halting problem: no computable function H(P,I) exists such that H returns 1 iff program P halts on input I; proof via diagonalization (Cantor's argument adapted by Turing, 1936). MIP*=RE: the class of problems verifiable by a classical verifier with two entangled quantum provers equals recursively enumerable sets — implies the algorithmic unsolvability of the quantum commuting operator problem (Connes' embedding conjecture is false). | CONNECTION: Diagonalization mirrors the golden ratio's self-referential recursion (φ = 1 + 1/φ) — both exploit fixed-point impossibility. The undecidability lattice is a non-crystallographic structure (no finite root system captures it), but the MIP*=RE result embeds halting in a *tensor product* of Hilbert spaces — a lattice of quantum states Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

•Oct 16, 2026•0 citations

Halting of Quantum Turing Machines

Masanao Ozawa

Lecture notes in computer science•Jan 1, 2002•6 citations

Quantum Dynamics and Computation [Working Title]

IntechOpen eBooks•Jan 1, 2019•0 citations

Remarks on the Halting problem, unitarity and reversibility in quantum theory of computations

Alexander Shalyt-Margolin, A. Ya. Tregubovich, В. И. Стражев

The Halting problem for the quantum computer is considered. It is shown, that if the halting for the quantum computer takes place then the corresponding dynamics is described by an irreversible operator.

•Jun 19, 2001•0 citations
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.
FINDING: The halting problem's undecidability is foundational to computation limits; recent MIP*=RE result shows quantum entanglement can encode undecidable problems, deepening the boundary of knowability. | MATH: Halting problem: no computable function H(P,I) exists such that H returns 1 iff program P halts on input I; proof via diagonalization (Cantor's argument adapted by Turing, 1936). MIP*=RE: the class of problems verifiable by a classical verifier with two entangled quantum provers equals recursively enumerable sets — implies the algorithmic unsolvability of the quantum commuting operator problem (Connes' embedding conjecture is false). | CONNECTION: Diagonalization mirrors the golden ratio's self-referential recursion (φ = 1 + 1/φ) — both exploit fixed-point impossibility. The undecidability lattice is a non-crystallographic structure (no finite root system captures it), but the MIP*=RE result embeds halting in a *tensor product* of Hilbert spaces — a lattice of quantum states Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com