State succinctness of two-way finite automata with quantum and classical states

Two-way finite automata with quantum and classical states (2QCFA) were introduced by Ambainis and Watrous in 2002. In this paper we study state succinctness of 2QCFA. For any m∈Z+ and any ϵ<1/2, we show that:1.there is a promise problem Aeq(m) which can be solved by a 2QCFA with one-sided error ϵ in a polynomial expected running time with a constant number (that depends neither on m nor on ε) of quantum states and classical states, whereas the sizes of the corresponding deterministic finite automata (DFA), two-way nondeterministic finite automata (2NFA) and polynomial expected running time two-way probabilistic finite automata (2PFA) are at least 2m+2, , and , respectively;2.there exists a language over the alphabet Σ={a,b,c} which can be recognized by a 2QCFA with one-sided error ϵ in an exponential expected running time with a constant number of quantum states and classical states, whereas the sizes of the corresponding DFA, 2NFA and polynomial expected running time 2PFA are at least 2m, , and , respectively; where b is a constant.