Abstract
In this paper, we introduce and explore a new model of quantum finite
automata (QFA). Namely, one-way finite automata with quantum and
classical states (1QCFA), a one way version of two-way finite automata
with quantum and classical states (2QCFA) introduced by Ambainis and Watrous
in 2002 AJ. First, we prove that one-way probabilistic finite
automata (1PFA) AP and one-way quantum finite automata with
control language (1QFACL) ACB as well as several other models of QFA,
can be simulated by 1QCFA. Afterwards, we explore several closure properties
for the family of languages accepted by 1QCFA. Finally, the state complexity of
1QCFA is explored and the main succinctness result is derived. Namely, for any
prime $m$ and any $\epsilon_1>0$, there exists a language $L_m$ that cannot
be recognized by any measure-many one-way quantum finite automata
(MM-1QFA) Kon97 with bounded error $7/9+\epsilon_1$, and any 1PFA
recognizing it has at last $m$ states, but $L_m$ can be recognized by a 1QCFA
for any error bound $\epsilon>0$ with $O(m)$ quantum states and 12
classical states.
Users
Please
log in to take part in the discussion (add own reviews or comments).