Languages Recognizable by Quantum Finite Automata

There are several nonequivalent definitions of quantum finite automata. Nearly all of them recognize only regular languages but not all regular languages. On the other hand, for all these definitions there is a result showing that there is a language

l

such that the size of the quantum automaton recognizing

L

is essentially smaller than the size of the minimal deterministic automaton recognizing

L

.

For most of the definitions of quantum finite automata the problem to describe the class of the languages recognizable by the quantum automata is still open. The partial results are surveyed in this paper. Moreover, for the most popular definition of the QFA, the class of languages recognizable by a QFA is not closed under union or any other binary Boolean operation where both arguments are significant.

The end of the paper is devoted to unpublished results of the description of the class of the recognizable languages in terms of the second order predicate logics. This research is influenced by the results of Büchi [1,2], Elgot [3], Trakhtenbrot [4] (description of regular languages in terms of MSO), R.Fagin [5,6] (description of NP in terms of ESO), von Neumann [7] (quantum logics), Barenco, Bennett et al. [8](universal quantum gates).