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 ε>0, there is a 2qfa M which recognizes the non-regular language L={a^mb^m|m⩾1} with (one-sided) error bounded by E, 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-ε. 2. For every regular language L, there is 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 2qfar´s which recognize the non-context-free language {a^m b^mc^m|m⩾1}, based on the same technique used for 1. Consequently, the class of languages recognized by linear time, bounded error 2qfa´s properly includes the regular languages. Since it is known that 2-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. We prove that the class of languages recognizable by bounded error 1qfa´s is properly contained in the class of regular languages