On hybrid models of quantum finite automata

Abstract: In the literature, there exist several quantum finite automata (QFA) models with both quantum and classical states. These models are of particular interest,as they show praiseworthy advantages over the fully quantum models in some nontrivial aspects. This paper characterizes these models in a uniform framework by proposing a general hybrid model consisting of a quantum component and a classical one which can interact with each other. The existing hybrid QFA can be naturally regarded as the general model with specific communication patterns (classical-quantum, quantum-classical, and two-way, respectively). We further clarify the relationship between these hybrid QFA and some other quantum models. In particular, it is shown that hybrid QFA can be simulated exactly by QFA with quantum operations, which in turn has a close relationship with two early proposed models: {it ancialla QFA} and {it quantum sequential machines}.

Review text

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.

Recommendations

Cites work

Cited in

(12)

Describes a project that uses

Uses Software

QPL

This page was built for publication: On hybrid models of quantum finite automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2353395)