1. On the class of languages recognizable by 1-way quantum finite automata
Andris Ambainis, Arnolds Kikusts, Maris Valdats
http://arxiv.org/abs/quant-ph/0009004
It is an open problem to characterize the class of languages recognized by quantum finite automata (QFA). We examine some necessary and some sufficient conditions for a (regular) language to be recognizable by a QFA. For a subclass of regular languages we get a condition which is necessary and sufficient. Also, we prove that the class of languages recognizable by a QFA is not closed under union or any other binary Boolean operation where both arguments are significant.