State succinctness of two-way finite automata with quantum and classical states
| Authors | |
|---|---|
| Year of publication | 2013 |
| Type | Article in Periodical |
| Magazine / Source | Theoretical Computer Science |
| MU Faculty or unit | |
| Citation | |
| Doi | http://dx.doi.org/10.1016/j.tcs.2013.06.005 |
| Field | Informatics |
| Keywords | Computing models; Quantum finite automata; State complexity; Succinctness |
| Attached files | |
| Description | Two-way finite 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 from Z+ and any e<1/2, we show that: 1.there is a promise problem Aeq(m) which can be solved by a 2QCFA with one-sided error e in a polynomial expected running time with a constant number (that depends neither on m nor on eps) of quantum states and View the MathML source classical states, whereas the sizes of the corresponding deterministic finite automata (DFA), two-way nondeterministic finite automata (2NFA) and polynomial expected running time two-way probabilistic finite automata (2PFA) are at least 2m+2, View the MathML source, and View the MathML source, respectively; 2.there exists a language View the MathML source over the alphabet Sigma={a,b,c} which can be recognized by a 2QCFA with one-sided error e in an exponential expected running time with a constant number of quantum states and View the MathML source classical states, whereas the sizes of the corresponding DFA, 2NFA and polynomial expected running time 2PFA are at least 2m, View the MathML source, and View the MathML source, respectively; where b is a constant. |
| Related projects: |