characterizations of one-way general quantum finite automata
文献类型：期刊论文
| 作者 | Lvzhou Li ; Daowen Qiu ; Xiangfu Zou ; Lvjun Li ; Lihua Wu ; Paulo Mateus |
| 刊名 | Theoretical Computer Science
 |
| 出版日期 | 2011 |
| 卷号 | 419页码:- |
| 关键词 | Formal languages Quantum finite automata Regular languages Equivalence |
| ISSN号 | 0304-3975 |
| 中文摘要 | Generally, unitary transformations limit the computational power of quantum finite automata (QFA). In this paper we study a generalized model named one-way general quantum finite automata (1gQFA), in which each symbol in the input alphabet induces a trace-preserving quantum operation, instead of a unitary transformation. Two different kinds of 1gQFA will be studied: measure-once one-way general quantum finite automata (MO-1gQFA) where a measurement deciding to accept or reject is performed at the end of a computation, and measure-many one-way general quantum finite automata (MM-1gQFA) where a similar measurement is performed after each trace-preserving quantum operation on reading each input symbol. We characterize the measure-once model from three aspects: the closure property, the language recognition power, and the equivalence problem. We prove that MO-1gQFA recognize, with bounded error, precisely the set of all regular languages. Our results imply that some models of quantum finite automata proposed in the literature, which were expected to be more powerful, still cannot recognize non-regular languages. We prove that MM-1gQFA also recognize only regular languages with bounded error. Thus, MM-1gQFA and MO-1gQFA have the same language recognition power, in sharp contrast with traditional MO-1QFA and MM-1QFA, the former being strictly less powerful than the latter. Finally, we present a necessary and sufficient condition for two MM-1gQFA to be equivalent. |
| 英文摘要 | Generally, unitary transformations limit the computational power of quantum finite automata (QFA). In this paper we study a generalized model named one-way general quantum finite automata (1gQFA), in which each symbol in the input alphabet induces a trace-preserving quantum operation, instead of a unitary transformation. Two different kinds of 1gQFA will be studied: measure-once one-way general quantum finite automata (MO-1gQFA) where a measurement deciding to accept or reject is performed at the end of a computation, and measure-many one-way general quantum finite automata (MM-1gQFA) where a similar measurement is performed after each trace-preserving quantum operation on reading each input symbol. We characterize the measure-once model from three aspects: the closure property, the language recognition power, and the equivalence problem. We prove that MO-1gQFA recognize, with bounded error, precisely the set of all regular languages. Our results imply that some models of quantum finite automata proposed in the literature, which were expected to be more powerful, still cannot recognize non-regular languages. We prove that MM-1gQFA also recognize only regular languages with bounded error. Thus, MM-1gQFA and MO-1gQFA have the same language recognition power, in sharp contrast with traditional MO-1QFA and MM-1QFA, the former being strictly less powerful than the latter. Finally, we present a necessary and sufficient condition for two MM-1gQFA to be equivalent. |
| 学科主题 | Computer Science |
| 收录类别 | SCIENCEDIRECT ; EI |
| 资助信息 | National Natural Science Foundation 60873055, 61073054, 61100001; Natural Science Foundation of Guangdong Province of China 10251027501000004; Fundamental Research Funds for the Central Universities 10lgzd12, 11lgpy36; Research Foundation for the Doctoral Program of Higher School of Ministry of Education of China 20100171110042, 20100171120051; China Postdoctoral Science Foundation 20090460808, 201003375; SQIG at IT; FCT; EU Quantlog POCI/MAT/55796/2004, QSec PTDC/EIA/67661/2006; IT Project QuantTel; NoE Euro-NF; SQIG LAP initiative |
| 语种 | 英语 |
| WOS记录号 | WOS:000300534900006 |
| 公开日期 | 2013-10-08 |
| 源URL | [http://ir.iscas.ac.cn/handle/311060/16015]  |
| 专题 | 软件研究所_软件所图书馆_期刊论文 |
| 推荐引用方式 GB/T 7714 | Lvzhou Li,Daowen Qiu,Xiangfu Zou,et al. characterizations of one-way general quantum finite automata[J]. Theoretical Computer Science,2011,419:-. |
| APA | Lvzhou Li,Daowen Qiu,Xiangfu Zou,Lvjun Li,Lihua Wu,&Paulo Mateus.(2011).characterizations of one-way general quantum finite automata.Theoretical Computer Science,419,-. |
| MLA | Lvzhou Li,et al."characterizations of one-way general quantum finite automata".Theoretical Computer Science 419(2011):-. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。