A formulation of Quantum Turing Machine

Satoshi Iriyama, Masanori Ohya

Masanao Ozawa, Harumichi Nishimura

Foundations of the notion of quantum Turing machines are investigated. According to Deutsch's formulation, the time evolution of a quantum Turing machine is to be determined by the local transition function. In this paper, the local transition functions are characterized for fully general quantum Turing machines, including multi-tape quantum Turing machines, extending the results due to Bernstein and Vazirani.

Marco Carpentieri

Masanao Ozawa, Harumichi Nishimura

Foundations of the notion of quantum Turing machines are investigated. According to Deutsch's formulation, the time evolution of a quantum Turing machine is to be determined by the local transition function. In this paper, the local transition functions are characterized for fully general quantum Turing machines, including multi-tape quantum Turing machines, extending the results due to Bernstein and Vazirani.

Masanao Ozawa

Satoshi Iriyama, Masanori Ohya

In this paper, we construct a novel model of a universal quantum Turing machine(QTM) which is free from the specific time for an input data and efficiently simulates each step of a given QTM.Deutsch [1] formulated a precise model of a quantum computer as quantum Turing machine (QTM) and proposed a model of universal quantum Turing machine which requires exponential time of $t$ to simulate any other QTM with $t$ steps.Bernstein and Vazirani[2] showed the existence of an efficient universal QTM by slightly modifying Deutsch's model.In [3] several issues related with QTM and universal QTM are discussed.Nishimura and Ozawa gave another