Size lower bounds for quantum automata

• We analyze the descriptional power of Quantum Finite Automata with control language.
• We show an exponential size cost conversion from QFAs with control language to DFAs.
• We simulate Latvian QFAs by QFAs with control languages.
• We obtain size lower bounds for several models of QFAs.

We compare the descriptional power of quantum finite automata with control language (qfcs) and deterministic finite automata (dfas). By suitably adapting Rabin's technique, we show how to convert any given qfc to an equivalent dfa, incurring in an at most exponential size increase. This enables us to state a lower bound on the size of qfcs, which is logarithmic in the size of equivalent minimal dfas. In turn, this result yields analogous size lower bounds for several models of quantum finite automata in the literature.