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• 3 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

On the Halting Problem for Quantum Turing Machines

正直 小澤

数理解析研究所講究録•Oct 1, 1998•0 citations

Unsolvability of the Halting Problem in Quantum Dynamics

Song, D

It is shown that the halting problem cannot be solved consistently in both the Schrodinger and Heisenberg pictures of quantum dynamics. The existence of the halting machine, which is assumed from quantum theory, leads into a contradiction when we consider the case when the observer's reference frame is the system that is to be evolved in both pictures. We then show that in order to include the evolution of observer's reference frame in a physically sensible way, the Heisenberg picture with time going backwards yields a correct description.

•Oct 7, 2006•7 citations

Halting of Quantum Turing Machines

Masanao Ozawa

Lecture notes in computer science•Jan 1, 2002•7 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•0 citations

Limits and Solvability of Quantum Computing

World scientific series on nonlinear science, series A•Nov 25, 2024•0 citations
It is shown that the halting problem cannot be solved consistently in both the Schrodinger and Heisenberg pictures of quantum dynamics. The existence of the halting machine, which is assumed from quantum theory, leads into a contradiction when we consider the case when the observer's reference frame is the system that is to be evolved in both pictures. We then show that in order to include the evolution of observer's reference frame in a physically sensible way, the Heisenberg picture with time going backwards yields a correct description.
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.