On the class of languages recognizable by 1-way quantum finite automata
Andris Ambainis, Arnolds Ķikusts, Māris Valdats
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.
arXiv:quant-ph/0009004•Sep 1, 2000•6 citations