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

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

ZHENG Shenggen QIU Daowen GRUSKA Jozef LI Lvzhou MATEUS Paulo

Year of publication 2013
Type Article in Periodical
Magazine / Source Theoretical Computer Science
MU Faculty or unit

Faculty of Informatics

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:

You are running an old browser version. We recommend updating your browser to its latest version.