Halting of Quantum Turing Machines

摘要

The notion of a quantum Turing machine (QTM) is well established as a mathematical model. However, the difficulty on halting procedures has prevented us from formulating the notion of computing on an arbitrary quantum Turing machine. Here, an argument is outlined to show that any QTM can be efficiently simulated by a QTM with well-behaved halting flag. Thus, we can affirmatively solve the halting problem for QTMs.