The Halting Problem for Quantum Computers

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.

4 pages, Revised version

Cited by in corpus (11)

• Strongly Universal Quantum Turing Machines and Invariance of Kolmogorov Complexity
• Quantum Kolmogorov Complexity and the Quantum Turing Machine
• Weakly measured while loops: peeking at quantum states
• Algorithmic Information Theoretic Issues in Quantum Mechanics
• Quantum Kolmogorov Complexity and Information-Disturbance Theorem
• Quantum Kolmogorov complexity and quantum correlations in deterministic-control quantum Turing machines
• Quantum Iterative Deepening with an application to the Halting problem
• Beyond z=0. The Deutsch-Jozsa decided monochromatic languages
• The basic principles to construct a generalized state-locking pulse field and simulate efficiently the reversible and unitary halting protocol of a universal quantum computer
• Quantum Turing Machines: Local Transition, Preparation, Measurement, and Halting
• On Quantum Turing Machine Halting Deterministically