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

ISCAS OpenIR

	State succinctness of two-way finite automata with quantum and classical states
	Zheng, Shenggen (1); Qiu, Daowen (1); Gruska, Jozef (3); Li, Lvzhou (1); Mateus, Paulo (2); Qiu, D.(issqdw@mail.sysu.edu.cn)
	2013
发表期刊	Theoretical Computer Science
ISSN	3043975
卷号	499 页码:98-112
摘要	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 √³(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 √³m/b, respectively; where b is a constant. © 2013 Elsevier B.V.; 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 √³(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 √³m/b, respectively; where b is a constant. © 2013 Elsevier B.V.
收录类别	SCI ; EI
关键词	Computing Models Quantum Finite Automata State Complexity Succinctness
部门归属	(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
语种	英语
WOS记录号	WOS:000323809200007
引用统计
内容类型	期刊论文
URI标识	http://ir.iscas.ac.cn/handle/311060/16918
专题	中国科学院软件研究所
通讯作者	Qiu, D.(issqdw@mail.sysu.edu.cn)
推荐引用方式 GB/T 7714	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,499:98-112.
APA	Zheng, Shenggen ,Qiu, Daowen ,Gruska, Jozef ,Li, Lvzhou ,Mateus, Paulo ,&Qiu, D..(2013).State succinctness of two-way finite automata with quantum and classical states.Theoretical Computer Science,499,98-112.
MLA	Zheng, Shenggen ,et al."State succinctness of two-way finite automata with quantum and classical states".Theoretical Computer Science 499(2013):98-112.