1202.6530 (Min Liang et al.)

On Quantum Turing Machine Halting Deterministically    [PDF]

Min Liang, Li Yang

We define a subclass of quantum Turing machine (QTM) named SR-QTM, which halts deterministically and has deterministic tape head position. A quantum state transition diagram (QSTD) is proposed to describe SR-QTM. With the help of QSTD, we construct a SR-QTM which is universal for all near-trivial transformations. This means there exists a QTM which is universal for the above subclass. Finally we prove that SR-QTM is computational equivalent with ordinary QTM in the bounded error setting. It can be seen that, because SR-QTM has the same time steps for different branches of computation, the halting scheme problem will not exist when considering SR-QTM as a model of quantum computing.

View original: http://arxiv.org/abs/1202.6530