What languages does a (1-way) quantum finite state automata recognize?
Quantum finite automata (QFAs) are quantum counterparts of the usual finite automata.

In [1] it is shown that 1-way QFAs recognize a proper subset of the regular languages:

Proposition 6: Let $L$ be any language recognized by a 1QFA with bounded error. Then $L$ is regular.

Proposition 7: The language $L = \{a,b\}^*a$ cannot be recongized by a 1QFA with bounded error.

However in [2] :

... Our first results consider relations between 1-way QFAs and 1-way reversible automata.
Clearly, a 1-way reversible automaton is a special case of a QFA and, therefore, cannot
recognize all regular languages. It is a natural question whether 1-way QFAs are more
powerful than 1-way reversible automata. Interestingly, the answer depends on the accepting
probability of a QFA. If a QFA gives a correct answer with a large probability (greater than
7/9), it can be replaced by a 1-way reversible automaton. However, this is not true for 0.68...
and smaller probabilities.

Then, we show that QFAs can be much more space-efficient than deterministic and even
probabilistic finite automata. Namely, there is a 1-way QFA that can check whether the
number of letters received from the input is divisible by a prime p with only $O(\log p)$ states
(this is equivalent to $\log \log p$ bits of memory). Any deterministic or probabilistic finite
automaton needs p states ($\log p$ bits of memory). We think that this space-efficient quantum
algorithm may be interesting for design of other quantum algoritms as well....

For a quick introduction see: 


[1] Attila Kondacs and John Watrous, On the Power of Quantum Finite State Automata;
[2] Andris Ambainis and Rusins Freivaldsy, 1-way quantum nite automata: strengths, weaknesses and generalizations; 
[3] Abuzer Yakaryilmaz and A. C. Cem Say, Unbounded-error quantum computation with small space bounds; 
[4] Andris Ambainis and Abuzer Yakaryilmaz, Superiority of exact quantum automata for promise problems;
[5] Cristopher Moore and James P. Crutchfield, Quantum Automata and Quantum Grammars;
[6] Andris Ambainis, Quantum Finite Automata.