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/9806054

The Halting Problem for Quantum Computers

Noah Linden, Sandu Popescu

Published Jun 16, 1998• 48 citations
arXivHTMLPDF

Abstract

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.
DOI
10.48550/arxiv.quant-ph/9806054

Related papers

Halting in quantum Turing computation

Willem L. Fouché, Johannes Heidema, Jones, G. +1 more

The paper considers the halting scheme for quantum Turing machines. The scheme originally proposed by Deutsch appears to be correct, but not exactly as originally intended. We discuss the result of Ozawa as well as the objections raised by Myers, Kieu and Danos and others. Finally, the relationship of the halting scheme to the quest for a universal quantum Turing machine is considered.

arXiv:0705.3077•May 22, 2007•3 citations

On Halting Process of Quantum Turing Machine

Takayuki Miyadera, Masanori Ohya

We prove that there is no algorithm to tell whether an arbitrarily constructed Quantum Turing Machine has same time steps for different branches of computation. We, hence, cannot avoid the notion of halting to be probabilistic in Quantum Turing Machine.

arXiv:quant-ph/0302051•Open Systems & Information Dynamics•Aug 24, 2005•29 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

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

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

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