Quantum Real - Time Turing Machine

Margherita Zorzi

Amandeep Singh Bhatia, Ajay Kumar

This paper proposed a quantum analogue of classical queue automata by using the definition of the quantum Turing machine and quantum finite-state automata. However, quantum automata equipped with storage medium of a stack has been considered, but the concept of quantum queue automata has not been introduced so far. The classical Turing machines can be simulated by classical queue automata. Motivated by the efficiency of the quantum Turing machine and nature of classical queue automata, we have introduced the notion of quantum queue automata using unitary criteria. Our contributions are as follows. We have also introduced a generalization of real-time deterministic queue automata, the real-time quantum queue automata which work in real-time i.e. the input head can move towards the right direction only and takes exactly one step per input symbol. We have shown that real-time quantum queue automata is more superior than its real-time classical variants by using quantum transitions. We have proved the existence of the language that can be recognized by real-time quantum queue automata and cannot be recognized by real-time deterministic (reversible) queue automata. Further, we have shown that there is a language that can be recognized by real-time quantum queue automata but not by real-time non-deterministic queue automata.

Joachim Hertel

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

Andrés Sicard, Mario E. Vélez

For quantum Turing machines we present three elements: Its components, its time evolution operator and its local transition function. The components are related with the components of deterministic Turing machines, the time evolution operator is related with the evolution of reversible Turing machines and the local transition function is related with the transition function of probabilistic and reversible Turing machines.