6533b822fe1ef96bd127d70c

RESEARCH PRODUCT

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

Andris AmbainisArnolds KikustsMaris Valdats

subject

Quantum PhysicsComputer Science::Programming LanguagesFOS: Physical sciencesComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)Computer Science::Computational ComplexityQuantum Physics (quant-ph)Computer Science::Formal Languages and Automata Theory

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.

yearjournalcountryeditionlanguage
2000-09-01
https://dx.doi.org/10.48550/arxiv.quant-ph/0009004