In this paper, we introduce and explore a new model of quantum#N#finite automata (QFA). Namely, one-way finite automata with#N#quantum and classical states (1QCFA), a one way version of#N#two-way finite automata with quantum and classical states#N#(2QCFA) introduced by Ambainis and Watrous in 2002. First, we#N#prove that one-way probabilistic finite automata (1PFA) and#N#one-way quantum finite automata with control language (1QFACL),#N#as well as several other models of QFA, can be simulated by#N#1QCFA. Afterwards, we explore several closure properties for#N#the family of languages accepted by 1QCFA. Finally, the state#N#complexity of 1QCFA is explored and the main succinctness#N#result is derived. Namely, for any prime m and any \epsilon_{1}#N#> 0, there exists a language L_{m} that cannot be recognized by#N#any measure-many one-way quantum finite automata (MM-1QFA) with#N#bounded error 7/9+\epsilon_{1}, and any 1PFA recognizing it has#N#at last m states, but L_{m} can be recognized by a 1QCFA for#N#any error bound \epsilon > 0 with O(log(m)$ quantum states and#N#12 classical states.
['Shenggen Zheng', 'Daowen Qiu', 'Lvzhou Li', 'Jozef Gruska']
One-Way Finite Automata with Quantum and Classical States