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

Abstract

{\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\in {\mathbb{Z}}^{+}$ and any $\epsilon <1/2$, we show that: {enumerate} there is a promise problem $A^{eq}(m)$ which can be solved by a 2QCFA with one-sided error $\epsilon$ in a polynomial expected running time with a constant number (that depends neither on $m$ nor on $\epsilon$) of quantum states and $\mathbf{O}(\log \frac{1}{\epsilon })$ 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}$, respectively; there exists a language $L^{twin}(m)=\{wcw|w\in \{a,b{\}}^{\ast }\}$ over the alphabet $\Sigma =\{a,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 $\mathbf{O}(\log \frac{1}{\epsilon })$ 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}$, respectively; {enumerate} where $b$ is a constant.

26pages, comments and suggestions are welcome

References in corpus (5)

• Unbounded-error quantum computation with small space bounds
• Superiority of exact quantum automata for promise problems
• Exponentially more concise quantum recognition of non-RMM regular languages
• One-way finite automata with quantum and classical states
• Some Languages Recognized by Two-Way Finite Automata with Quantum and Classical States

Cited by in corpus (2)

• Potential of quantum finite automata with exact acceptance
• Time-space tradeoffs for two-way finite automata