On the class of languages recognizable by 1-way quantum finite automata

Ambainis, Andris; Kikusts, Arnolds; Valdats, Maris

On the class of languages recognizable by 1-way quantum finite automata

Authors

Ambainis, Andris

Kikusts, Arnolds

Valdats, Maris

Description

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.
18 pages, 16 figures, extends quant-ph/0001005