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

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

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

Published Jun 19, 2001• 0 citations
OpenAlex

Abstract

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.

Related papers

IRREVERSIBILITY IN THE HALTING PROBLEM OF QUANTUM COMPUTER

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

The Halting problem of a quantum computer is considered. It is shown that if halting of a quantum computer takes place the associated dynamics is described by an irreversible operator.

arXiv:quant-ph/0106108•Modern Physics Letters B•Jul 10, 2007•1 citation

The halting problem for universal quantum computers

Tien D. Kieu, Michael Danos

The halting of universal quantum computers is shown to be incompatible with the constraint of unitarity of the dynamics.

arXiv:quant-ph/9811001•Nov 2, 1998•9 citations

Remarks on the undecidability of the quantum halting problem

Daegene Song

The halting problem is a decision problem first posed and proved by Alan Turing in 1936. With the recent surge of interest in quantum computation, one is led to ask if the problem can also be considered for a quantum computer. It is reported that the halting problem may not be solved consistently in both the Schrodinger and Heisenberg pictures of quantum dynamics. The assumption of the existence of the quantum halting machine leads to a contradiction when a vector representing an observable is the system that is to be unitarily evolved in both pictures.

•Jan 22, 2007•1 citation

The Halting Problem for Quantum Computers

Noah Linden, Sandu Popescu

We argue that the halting problem for quantum computers which was first raised by Myers, is by no means solved, as has been claimed recently. We explicitly demonstrate the difficulties that arise in a quantum computer when different branches of the computation halt at different, unknown, times.

arXiv:quant-ph/9806054•Jun 16, 1998•48 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

On the Halting Problem for Quantum Turing Machines

Masanao Ozawa

Foundations of the theory of quantum Turing machines are investigated.The local transition functions are characterized for fully general quantum Tur- ing machines.Foundational problems on the preparation and the measurement of quantum Turing machines are discussed.The halt scheme, originally proposed by Deutsch, is formulated precisely and is shown to work without spoiling computation.

数理解析研究所講究録•Oct 1, 1998•2 citations
The halting problem is a decision problem first posed and proved by Alan Turing in 1936. With the recent surge of interest in quantum computation, one is led to ask if the problem can also be considered for a quantum computer. It is reported that the halting problem may not be solved consistently in both the Schrodinger and Heisenberg pictures of quantum dynamics. The assumption of the existence of the quantum halting machine leads to a contradiction when a vector representing an observable is the system that is to be unitarily evolved in both pictures.
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