On the power of quantum finite state automata

In this paper, we introduce 1-way and 2-way quantum finite state automata (1qfa's and 2qfa's), which are the quantum analogues of deterministic, nondeterministic and probabilistic 1-way and 2-way finite state automata. We prove the following facts regarding 2qfa's. 1. For any epsilon > 0, there is a 2qfa M which recognizes the non-regular language L = (a(m)b(m) \ m greater than or equal to 1) with (one-sided) error bounded by epsilon, and which halts in linear time. Specifically, M accepts any string in L with probability 1 and rejects any string not in L with probability at least 1-epsilon. 2. For every regular language L, there as a reversible (and hence quantum) 2-way finite state automaton which recognizes L and which runs in linear time. In fact, it is possible to define 2qfa's which recognize the non-context-free language (a(m)b(m)c(m) \ m greater than or equal to 1), based on the same technique used for 1. Consequently, the class of languages recognized by linear tame, bounded error 2qfa's properly includes the regular languages. Since it is known that e-way deterministic, nondeterministic and polynomial expected time, bounded error probabilistic finite automata can recognize only regular languages, it follows that 2qfa's are strictly more powerful than these "classical" models. In the case of 1-way automata, the situation is reversed. lye prove that the class of languages recognizable by bounded error 1qfa's is properly contained in the class of regular languages.