Some formal tools for analyzing quantum automata

Results in the area of compact monoids and groups are useful in the analysis of quantum automata (1qfa's). In this paper: We settle isolated cut point Rabin's theorem in the context of compact monoids, and we prove a lower bound on the state complexity of 1qfa's accepting regular languages.We use a method pointed out by Blondel et al. [Decidable and undecidable problems about quantum automata, Technical Report RR2003-24, LIP, ENS Lyon, 2003] based on compact groups theory to design an algorithm for testing whether a Formula Not Shown -tuple of 1qfa's is a classifier of words in Formula Not Shown ; this problem turns out to be undecidable if the completeness of the classifier is required.In the unary case, we give an exponential time algorithm for computing the descriptional complexity of periodic languages. Moreover, we present a probabilistic method to construct 1qfa's exponentially succinct in the period and polynomially succinct in the inverse of the bounded error.