2012/02/13 by Shenggen Zheng, Daowen Qiu, Zheng, Shenggen +7 · 1 citation
Computer Science · Physics and Astronomy · #FOS: Computer and information sciences #FOS: Physical sciences #Formal Languages and Automata Theory (cs.FL) #Machine Learning and Algorithms #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #cs.FL #quant-ph #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1202.2651
26pages, comments and suggestions are welcome
openalex publication_date 2012/02/13 · arxiv created 2012/05/23 · arxiv updated 2012/05/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
\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 m∈ ℤ+ and any ε<1/2, we show that: enumerate 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 O(log\frac1ε) 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, √logm, and √[3](log m)/b, respectively; there exists a language Ltwin(m)=\wcw| w∈\a,b\^*\ 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 O(log\frac1ε) classical states, whereas the sizes of the corresponding DFA, 2NFA and polynomial expected running time 2PFA are at least 2m, √(m), and √[3]m/b, respectively; enumerate where b is a constant.