1202.2651 (Shenggen Zheng et al.)

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

Shenggen Zheng, Daowen Qiu, Lvzhou Li

{\it Two-way quantum 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 fix $m\in {\mathbb{Z}}^+$, we show that i) there is a promise problem
$A^{meq}$ which can be solved by 2QCFA in polynomial expected running time with
one-sided error with constant numbers of quantum and classical states, whereas
the sizes of the corresponding {\it deterministic finite automata} (DFA), {\it
two-way nondeterministic finite automata} (2NFA) and polynomial expected
running time {\it two-way probabilistic finite automata} (2PFA) are at least
$2m+2$, $\sqrt{\log{m}}$ and $\sqrt[3]{(\log m)/b}$; ii) there exists a
language $L^{mtwin}$ which can be recognized by 2QCFA in exponential expected
running time with one-sided error with constant numbers of quantum and
classical states, whereas the sizes of the corresponding DFA, 2NFA and
polynomial expected running time 2PFA are at least $2^m$, $\sqrt{m}$ and
$\sqrt[3]{m/b}$; where b is a constant number.

View original: http://arxiv.org/abs/1202.2651