1206.2131 (Lvzhou Li et al.)

On hybrid models of quantum finite automata    [PDF]

Lvzhou Li, Yuan Feng

In the literature, there are several hybrid models of quantum finite automata (QFA) which are distinguished from other QFA models by consisting of two interactive components: a quantum component and a classical one, accompanied with possible communication between them. These hybrid models are of particular interest, which is reflected at least by the following two points. (i) They are more realistic than fully quantum models, since using the current technology, large-scale quantum processors are still a long term goal, whereas building a hybrid model augmented with a small number of qubits is relatively easy. (ii) Hybrid models usually save efficiently states by being augmented with a small number of quantum states, and it is thus meaningful to construct a hybrid model for a practical problem (language) with a desired trade-off between quantum and classical states. Consequently, it is relevant to characterize the structure of these models in an intuitive way and to clearly clarify the relationship between these models and others. All these are helpful for well understanding hybrid models and for achieving an instruction to construct these models. Hereby, we would like to do that in this paper. First, we characterize the structure of these hybrid models in a uniform framework: a hybrid model can be regarded as a communication system consisting of two components, and the communication between them can be modeled by controlled operations. By doing so, we provide an intuitive insight into the structure of hybrid models. Second, we clarify the relationship between these hybrid models and some other quantum models. Specifically, we show that the existing hybrid models of QFA can be simulated exactly by QFA with quantum operations, which in turn has close relationship with two early proposed models: {\it anciall QFA} and {\it quantum sequential machines

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