The relation between capabilities of quantum and other
finite automata is a bit more complicated rather than the corresponding
relation for other types of computation mode. Namely, 1-way quantum finite
automata recognize only regular languages (hence they cannot do more than
deterministic automata) but the quantum automata cannot recognize all the
regular languages. For instance, the language 
is not recognizable by any 1-way quantum finite automaton. On the other
hand, for some languages quantum automata can have much less complexity.
It is proved by A. Ambainis and R. Freivalds that, for arbitrary prime
number p, there is a quantum 1-way finite automaton with 
states recognizing the language "the length of the input word is a multiple
of p " with a bounded probability of success while every deterministic
and even probabilistic 1-way finite automaton needs p states.
Later A. Kikusts improved the construction of the quantum automaton and constructed quantum automata with even less number of states.
For probabilistic finite automata, it is easily seen that if a function
can be computed by an automaton with a probability p, then the same
function can be computed with any higher probability of the correct result
p'
;SPMgt; p less than 1. Quantum finite automata are much different.
A. Ambainis and R. Freivalds proved in that there is a language recognizable
by a quantum finite automaton with a probability 
but not recognizable by any quantum automaton with a higher probability.
A. Ambainis, R. Bonner, R. Freivalds and A. Kikusts improved this result
showing existence of a hierarchy of regular languages such that the current
language in the hierarchy can be accepted by a quantum finite automata
equal or smaller than a certain "crucial" probability, and this crucial
probability is smaller than the crucial probability for the preceding language
in the hierarchy. These probabilities converge to 
.
For multitape and multihead finite automata the problem to compare capabilities
of quantum , deterministic and probabilistic automata is difficult. Quantum
finite automata are more powerful than deterministic ones, but the relation
between capabilities of quantum and probabilistic automata was open for
a long time till the paper by A. Ambainis, R. Bonner, R. Freivalds, M.
Golovkin and M. Karpinski.