On hybrid models of quantum finite automata (Q2353395)

Unitary operators perform the state evolution of quantum finite automata (QFA). Hybrid quantum finite automatons differ from quantum finite automata. They are composed of two interactive components, a quantum component and a classical one. An input symbol is scanned; the quantum and classical components interact to evolve into new states during which communication may occur between them. There are three main classes of quantum hybrid finite automata that differ in the way they communicate which each other. In class one only quantum-classical communication is allowed, the quantum component sends its measurement result to the classical component. In class two only classical-quantum communications is allowed, the classical component sends its current state to the quantum component. In class three both classical-quantum and quantum-classical communication are allowed. First, the classical component sends its current state to the quantum component and then the quantum component sends its measurement result to the classical component. In the paper it is shown that non-hybrid quantum finite automata that perform a unitary state evolution can simulate all the three classes. It seems that hybrid quantum finite automata are equivalent to quantum finite automata. From the authors' abstract: ``As corollaries, some results in the literature concerning the language recognition power and the equivalence problem of hybrid QFA follow directly from these relationships clarified in this paper.''