Events and Languages on Unary Quantum Automata

We prove that any unary regular language can be accepted with constant cut point and isolation by a MM-qfa with an amount of states which is linear in the size of the corresponding dfa. This gives a characterization of the recognition power of unary MM-qfa’s. We also single out families of unary languages for which the size of the accepting MM-qfa’s can be exponentially decreased. Then, we give an algorithm for testing the d-periodicity of the events induced by unary MM-qfa’s. Finally, we show how to compute the dimension of the “ergodic” and “transient” subspaces of unary MM-qfa’s. These algorithms run in polynomial time on unary MM-qfa’s having complex amplitudes with rational components.