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

Author: Zheng, Shenggen (1)
; Qiu, Daowen (1)
; Gruska, Jozef (3)
; Li, Lvzhou (1)
; Mateus, Paulo (2)
Corresponding Author: Qiu, D.(issqdw@mail.sysu.edu.cn)
Keyword: Computing models
; Quantum finite automata
; State complexity
; Succinctness
Source: Theoretical Computer Science
Issued Date: 2013
Volume: 499, Pages: 98-112 Indexed Type: SCI
; EI
Department: (1) Department of Computer Science, Sun Yat-sen University, Guangzhou 510006, China; (2) Departamento de Matemática, Instituto Superior Técnico, Technical University of Lisbon, Av. Rovisco Pais 1049-001, Lisbon, Portugal; (3) Faculty of Informatics, Masaryk University, Brno, Czech Republic; (4) State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing 100080, China
Abstract: 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ΕZ^{+} and any ∈<1/2, we show that:there is a promise problem A^{eq} (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(log1/∈) 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, √logm, and √^{3} (logm)/b, respectively;there exists a language L^{twin} (m)={wcw|wΕ{ a,b}^{*} ,|w|=m} 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(log1/∈) classical states, whereas the sizes of the corresponding DFA, 2NFA and polynomial expected running time 2PFA are at least 2^{m} , √m, and √^{3} m/b, respectively; where b is a constant. © 2013 Elsevier B.V.
English Abstract: 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ΕZ^{+} and any ∈<1/2, we show that:there is a promise problem A^{eq} (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(log1/∈) 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, √logm, and √^{3} (logm)/b, respectively;there exists a language L^{twin} (m)={wcw|wΕ{ a,b}^{*} ,|w|=m} 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(log1/∈) classical states, whereas the sizes of the corresponding DFA, 2NFA and polynomial expected running time 2PFA are at least 2^{m} , √m, and √^{3} m/b, respectively; where b is a constant. © 2013 Elsevier B.V.
Language: 英语
WOS ID: WOS:000323809200007
Citation statistics:

Content Type: 期刊论文
URI: http://ir.iscas.ac.cn/handle/311060/16918
Appears in Collections: 软件所图书馆_期刊论文

There are no files associated with this item.

Recommended Citation:
Zheng, Shenggen ,Qiu, Daowen ,Gruska, Jozef ,et al. State succinctness of two-way finite automata with quantum and classical states[J]. Theoretical Computer Science,2013-01-01,499:98-112.