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 is an element of Z(+) and any epsilon < 1/2, we show that: 1. there is a promise problem A(eq)(m) which can be solved by a 2QCFA with one-sided error is an element of in a polynomial expected running time with a constant number (that depends neither on m nor on epsilon) of quantum states and O(log1/epsilon) 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, root logm) and (3)root(logm)/b), respectively; 2. there exists a language L-twin(m) = {wcw vertical bar w is an element of {a, b}*, vertical bar w vertical bar = m} over the alphabet Sigma = b, c} which can be recognized by a 2QCFA with one-sided error epsilon in an exponential expected running time with a constant number of quantum states and O(log1/epsilon) classical states, whereas the sizes of the corresponding DFA, 2NFA and polynomial expected running time 2PFA are at least 2(m), root m and (3)root m/b respectively; where b is a constant. (C) 2013 Elsevier B.V. All rights reserved.