Lower bounds on the size of semi-quantum finite automata

In the literature, there exist several interesting hybrid models of finite automata which have both quantum and classical states. We call them semi-quantum finite automata. In this paper, we compare the descriptional power of these models and DFA. Specifically, we present a uniform method that gives a lower bound on the size of the three existing main models of semi-quantum finite automata, and this bound shows that semi-quantum finite automata can be at most exponentially more concise than DFA. Compared with a recent work [4], our method has the following two advantages: (i) it is much more concise; and (ii) it is universal, since it is applicable to the three existing main models of semi-quantum finite automata, instead of only one specific model.