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

Varování

Publikace nespadá pod Ekonomicko-správní fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

ZHENG Shenggen QIU Daowen GRUSKA Jozef LI Lvzhou MATEUS Paulo

Rok publikování 2013
Druh Článek v odborném periodiku
Časopis / Zdroj Theoretical Computer Science
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
Doi http://dx.doi.org/10.1016/j.tcs.2013.06.005
Obor Informatika
Klíčová slova Computing models; Quantum finite automata; State complexity; Succinctness
Přiložené soubory
Popis 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.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.