中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 软件所图书馆  > 期刊论文
Subject: Computer Science
Title:
characterizations of one-way general quantum finite automata
Author: Lvzhou Li ; Daowen Qiu ; Xiangfu Zou ; Lvjun Li ; Lihua Wu ; Paulo Mateus
Keyword: Formal languages ; Quantum finite automata ; Regular languages ; Equivalence
Source: Theoretical Computer Science
Issued Date: 2011
Volume: 419, Pages:-
Indexed Type: SCIENCEDIRECT ; EI
Department: aDepartment of Computer Science Sun Yat-sen University Guangzhou 510006 China; bSQIG–Instituto de Telecomunicações Departamento de Matemática Instituto Superior Técnico Universidade Técnica de Lisboa Av. Rovisco Pais 1049-001 Lisbon Portugal; cThe State Key Laboratory of Computer Science Institute of Software Chinese Academy of Sciences Beijing 100080 China
Sponsorship: 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
Abstract: 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.
English Abstract: 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.
Language: 英语
WOS ID: WOS:000300534900006
Citation statistics:
Content Type: 期刊论文
URI: http://ir.iscas.ac.cn/handle/311060/16015
Appears in Collections:软件所图书馆_期刊论文

Files in This Item:

There are no files associated with this item.


Recommended Citation:
Lvzhou Li,Daowen Qiu,Xiangfu Zou,et al. characterizations of one-way general quantum finite automata[J]. Theoretical Computer Science,2011-01-01,419:-.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[Lvzhou Li]'s Articles
[Daowen Qiu]'s Articles
[Xiangfu Zou]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[Lvzhou Li]‘s Articles
[Daowen Qiu]‘s Articles
[Xiangfu Zou]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2019  中国科学院软件研究所 - Feedback
Powered by CSpace