（计算机软件与理论专业论文）量子计算模型的等价性判定及量子通信中的若干基本问题.pdf

量子计算模型的等价性判定及量子通信中的若干基本问题 专业：计算机软件与理论 博士生：李绿周 指导老师：邱道文教授 摘要 量子计算与量子信息是近二十多年来发展起来的一门新兴学科，具有广阔 的发展前景。量子计算模型是量子计算的一个重要研究分支，目前已有多种量 子计算模型被提出并得到广泛而深入的研究。另一方面，量子通信是量子信息 中的一个重要研究方向，其中有很多基本问题有待解决。量子计算模型和量子 通信是存在一定联系的，例如文献f 1 ，2 ，3 】中曾用量子通信中的一些方法和结论 处理量子有限自动机的状态复杂性问题。本文研究量子计算模型的等价性判定 以及量子通信中的几个基本问题。 计算模型的等价性判定一直是经典计算领域的重要问题，而对量子计算模 型的等价性进行讨论有助于澄清经典与量子计算模型的本质差别，并且是进一 步研究量子计算模型的基础。关于这方面的研究，本文有以下主要工作： 给出两个量子时序机( q s m ) 等价的充分必要条件，并设计多项式时间的等 价性判定算法。另外，从q s m 的角度，进一步考虑测量一次的单向量子有 限自动机( m o - 1 q f a ) 的等价性。 给出两个带控制语言的单向量子有限自动机( c l - 1 q f a ) 等价的充分必要 条件，并讨论其等价性判定算法。 解决1 9 9 6 年i e e e 计算机学会先驱奖获得者、国际著名学者j o z e fg r u s k a 教 授= 2 0 0 0 年提出的关于测量多次的单向量子有限自动机( m m - 1 q f a ) 的等 价性问题，给出两个m m 一1 q f a 等价的充分必要条件，并指出存在多项式 时间的等价性判定算法。 量子计算模型的等价性判定及量子通信中的若干基本问题 量子通信中一个基础性问题是量子状态的区分，而量子运算的区分是量 子状态区分的进一步延伸。量子通信中另一重要问题是超密编码( s u p e r d e n s e c o d i n g ) 和隐形传态( t e l e p o r t a t i o n ) 。它们是量子通信有趣性和优越性的重要表 现，其中起关键作用的是作为共享资源的纠缠态。近来以、肌态作为超密编码和 隐形传态的共享资源也得到了人们的关注。考虑到这些问题，本文有以下主要 研究工作： 证明作用在dod 系统上的任何两个不同的二体酉变换，只要它们存 在有限多个拷贝，则可在局域操作和经典通信( l o c c ) 限制下对它 们进行精确区分，并且该过程中不需要使用任何纠缠。在某种程度 上，这是对z h o u ，z h a n g 和g u o 【p h y s r e v l e t t ，9 9 ，1 7 0 4 0 1 ( 2 0 0 7 ) 】以 及d u a n ，f e n g 和y i n g 【p h y s r e v l e t t ，1 0 0 ，0 2 0 5 0 3 ( 2 0 0 s ) 】中结论的新突 破，因为在这两个工作中，二体酉变换以l o c c 方式精确区分必须用到多 体纠缠态。 讨论作用在单量子比特系统上的两个量子运算的有歧区分( a m b i g u o u s d i s c r i m i n a t i o n ) ，给出它们有歧区分的最小出错概率的计算方法。另外，也 考虑两个量子运算可精确区分的条件。 考虑、u 态作为超密编码和隐形传态的共享资源，解决印度学者p a t i 等 毛e p h y s r e v a ，7 4 ，0 6 2 3 2 0 ( 2 0 0 6 ) 中提出的一些问题，给出、矶态可用来 实现精确超密编码和隐形传态的充分必要条件，并把一些有趣的w 态推 广到多粒子情形。 关键词：量子计算，量子自动机，等价性，量子运算的区分，、- 态 d e t e r m i n a t i o no fe q u i v a l e n c eb e t w e e nq u a n t u m c o m p u t i n gm o d e l sa n ds o m eb a s i cp r o b l e m si n q u a n t u mc o m m u n i c a t i o n m a j o r ： n a m e ： s u p e r v i s o r ： c o m p u t e rs o f t w a r ea n dt h e o r y l v z h o ul i p r o f e s s o rd a o w e nq i u a b s t r a c t q u a n t u mc o m p u t a t i o na n dq u a n t u mi n f o r m a t i o ni sab u r g e o n i n ga n dp r o m i s i n g f i e l dd e v e l o p e di nt h ep a s tt w od e c a d e s ，w h i c hh a saw i d ep r o s p e c t t h es u b j e c t o fq u a n t u mc o m p u t i n gm o d e l si so n eo ft h em a j o rb r a n c h e si nq u a n t u mc o i n - p u t a t i o n s of a r ，v a r i a n tq u a n t u mc o m p u t i n gm o d e l sh a v eb e e np r o p o s e d ，a n d t h e yh a v eb e e ns t u d i e de x t e n s i v e l ya n di n t e n s i v e l yb yr e s e a r c h e r s o nt h eo t h e r h a n d ，q u a n t u mc o m m u n i c a t i o ni sa ni m p o r t a n tr e s e a r c hd i r e c t i o no fq u a n t u m i n f o r m a t i o n ，i nw h i c hm a n yb a s i cp r o b l e m ss t i l ln e e dt ob es o l v e d i ti sw o r t h p o i n t i n go u tt h a tt h e r ea l s oe x i s t sc l o s ec o n n e c t i o nb e t w e e nq u a n t u mc o m p u t i n g m o d e l sa n dq u a n t u mc o m m u n i c a t i o n f o re x a m p l e ，r e f 【1 ，2 ，3 】u s e ds o m e m e t h o d sa n dc o n c l u s i o n si nq u a n t u mc o m m u n i c a t i o nt oa d d r e s st h es t a t ec o i n - p l e x i t yp r o b l e mo fq u a n t u mf i n i t ea u t o m a t a ( q f a ) i nt h i sd i s s e r t a t i o n ，w et r y t os t u d yt h ee q u i v a l e n c ep r o b l e mo fs o m eq u a n t u mc o m p u t i n gm o d e l sa n ds o m e b a s i cp r o b l e m si nq u a n t u mc o m m u n i c a t i o n d e t e r m i n i n gt h ee q u i v a l e n c eb e t w e e nc o m p u t i n gm o d e l si so fi m p o r t a n c ei n t h et h e o r yo fc l a s s i c a lc o m p u t a t i o n a ss u c h ，d i s c u s s i n gt h ee q u i v a l e n c eo fq u a n - t u mc o m p u t i n gm o d e l sr e d o u n d st oc l a r i 匆i n gt h ee s s e n t i a ld i f f e r e n c eb e t w e e n c l a s s i c a la n dq u a n t u mc o m p u t i n gm o d e l s ，a n dm i g h tf o r mab a s ef o rt h ef u r t h e r s t u d yc o n c e r n i n gq u a n t u mc o m p u t i n gm o d e l s t h em a i nc o n t r i b u t i o n so ft h i s d i s s e r t a t i o na r ea sf o h o w s l v 量子计算模型的等价性判定及量子通信中的若干基本问题 w eg i v eas u f f i c i e n ta n dn e c e s s a r yc o n d i t i o nf o rt w oq u a n t u ms e q u e n t i a lm a c h i n e s ( q s m ) t ob ee q u i v a l e n t f u r t h e r m o r e ，w ep r e s e n tap o l y n o m i a l - t i m e a l g o r i t h mt od e t e r m i n ew h e t h e rt w oq s ma r ee q u i v a l e n t a d d i t i o n a l l y , f r o mt h ev i e w p o i n to fq s m ，w ed i s c u s s f u r t h e rt h ee q u i v a l e n c ep r o b l e mo f m e a s u r e d 扎c eo n e w a yq u a n t u mf i n i t ea u t o m a t a ( m o i q f a ) w e g i v eas u f f i c i e n ta n dn e c e s s a r yc o n d i t i o nf o rt w oo n e w a yq u a n t u mf i n i t e a u t o m a t aw i t hc o n t r o ll a n g u a g e s ( c l 一1 q f a ) t ob ee q u i v a l e n t ，a n da l s ow e d i s c u s st h ee q u i v a l e n c e d e t e r m i n a t i o na l g o r i t h mf o rc l - i q f a i n2 0 0 0 ，p r o f e s s o rj o z e fg r u s k a ，t h ew i n n e ro f “c o m p u t e rp i o n e e ra w a r d o fi e e e ( 1 9 9 6 ) ”，p r o p o s e dap r o b l e mo nt h ee q u i v a l e n c eo fm e a s u r e m a n y o n e w a yq u a n t u mf i n i t ea u t o m a t a ( m m 一1 q f a ) w ea d d r e s st h i sp r o b l e m i nt h i sd i s s e r t a t i o n s p e c i f i c a l l y , w eg i v eas u f f i c i e n ta n dn e c e s s a r yc o n d i t i o nf o rt w om m - 1 q f at ob ee q u i v a l e n t a n dp o i n to u tt h a tt h e r ee x i s t sa p o l y n o m i a l - t i m ea l g o r i t h mt od e t e r m i n ew h e t h e rt w om m - 1 q f aa x ee q u i v - a l e n t af u n d a m e n t a lp r o b l e mi nq u a n t u mc o m m u n i c a t i o ni st h ed i s c r i m i n a t i o no f q u a n t u ms t a t e s a n o t h e ri m p o r t a n ts u b j e c ti nq u a n t u mc o m m u n i c a t i o ni st h e s t u d yo ns u p e r d e n s ec o d i n ga n dt e l e p o r t a t i o n e x a c t l y , s u p e r d e n s ec o d i n ga n d t e l e p o r t a t i o ne x h i b i tt h ei n t e r e s t i n g n e s sa n ds u p e r i o r i t yo fq u a n t u mc o m m u n i c a - t i o n i nw h i c he n t a n g l e dq u a n t u ms t a t e sp l a yac r u c i a lr o l ea ss h a r e dr e s o u r c e s r e c e n t l y , w - s t a t e sh a v ea t t r a c t e ds o m ea t t e n t i o nf r o mr e s e a r c h e r sa n dt h e ya r e t h o u g h to fa st h es h a r e dr e s o u r c e sf o rs u p e r d e n s ec o d i n ga n dt e l e p o r t a t i o n r e - g a r d i n gt h e s ep r o b l e m s ，t h em a i nc o n t r i b u t i o n so ft h i sd i s s e r t a t i o na r ea sf o l l o w s w ep r o v et h a ta n yt w od i f f e r e n tb i p a r t i t eu n i t a r yo p e r a t i o n sa c t i n go nd0d s y s t e m s ，a l l o w e dw i t haf i n i t en u m b e ro fc o p i e s ，c a l la l w a y sb ep e r f e c t l yd i s - c r i m i n a t e db yl o c a lo p e r a t i o n sa n dc l a s s i c a lc o m m u n i c a t i o n ( l o c c ) w i t h - o u te x p l o i t i n ga n ye n t a n g l e m e n t t oac e r t a i ne x t e n t ，t h i sc a nb e t h o u g h to fa u sab r e a k t h r o u g hf o rt h ew o r kb yz h o u ，z h a n ga n dg u o 【p h y s r e v l e t t ，9 9 ，1 7 0 4 0 1 ( 2 0 0 7 ) 】a n dt h ew o r kb yd u a n ，f e n ga n dy i n g 【p h y s r e v l e t t ，1 0 0 ，0 2 0 5 0 3 ( 2 0 0 8 ) 1 ，w h e r eam u l t i p a r t i t ee n t a n g l e d v s t a t ei sr e q u i r e df o rt h ep e r f e c td i s c r i m i n a t i o nb e t w e e nt w ob i p a r t i t eu n i - t a r yo p e r a t i o n sb yl o c c w ed i s c u s sa m b i g u o u sd i s c r i m i n a t i o no fq u a n t u mo p e r a t i o n sa c t i n go n s i n g l e q u b i ts y s t e m s ，a n dg i v eam e t h o dt oc a l c u l a t et h em i n i m u m - e r r o r p r o b a b i l i t yf o rt h ea m b i g u o u sd i s c r i m i n a t i o nb e t w e e n t w o s i n g l e - q u b i tq u a n - t u r no p e r a t i o n s a l s o ，w ec o n s i d e rt h ec o n d i t i o nf o rt w oq u a n t u mo p e r a - t i o u st ob ep e r f e c t l yd i s t i n g u i s h a b l e c o n s i d e r i n gw - s t a t e sa u ss h a r e dr e s o u r c e sf o rs u p e r d e n s ec o d i n ga n d t e l e - p o r t a t i o n ，w ea d d r e s ss o m ep e n d i n gp r o b l e m si na g r a w a la n dp a t i p h y s r e v a ，7 4 ，0 6 2 3 2 0 ( 2 0 0 6 ) s p e c i f i c a l l y , w eg i v ean e c e s s a r ya n d s u f f i - c i e n tc o n d i t i o nf o raw - s t a t eb e i n gs u i t a b l ef o rp e r f e c ts u p e r d e n s ec o d i n g a n dt e l e p o r t a t i o n ，a n de x t e n ds o m ei n t e r e s t i n gw - s t a t e st om u l t i p a r t i t e s y s t e m s k e y w o r d s ：q u a n t u mc o m p u t a t i o n ，q u a n t u ma u t o m a t a ，e q u i v a l e n c e ，d i s - c r i m i n a t i o no fq u a n t u mo p e r a t i o n s ，w - s t a t e s 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个 人或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和 集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人 承担。 学位论文作者签名： 日褥：硼年 其弓i b 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将 学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室 被查阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩 印或其他方法保存学位 学位论文作者签名导师签 日期勿。7 年，月弓日 日期 弓l e l 第一章引言 本章对本文所研究问题的背景和现状进行比较全面的介绍，并简要介绍本 文所研究的问题和结论。下面的内容将从量子计算模型和量子通信的几个基本 问题两方面进行阐述。 首先注意到计算模型和通信是相互联系的，这在经典领域里表现比较 明显。例如通信协议的描述和验证通常是基于有限自动机模型的 4 ，5 ，6 】。 另一方面，利用通信复杂性1 可求有限自动机识别给定语言的状态数的下 界。早在1 9 8 6 年，h r o m k o v i 6 7 就指出单向通信协议的复杂性和确定有限自动 机( d f a ) 的状态数之间存在一定关系。之后，文献8 ，9 ，1 0 ，1 1 ，1 2 进一步利用通 信复杂性与有限自动机状态数之间的关系讨论了非确定有限自动机( n f a ) ，概 率自动机，以及双向有限自动机的状态复杂性问题。h r o m k o v i 芒在其关于通信复 杂性和并行计算的专著 1 3 】中有一章专门用来论述通信协议和有限自动机以及 图灵机之间的关系。特别地，文献 1 3 】中指出利用通信复杂性的相关方法和结论 可求有限自动机状态复杂性的下界，并且也可用来求图灵机的时间和空间复杂 性。 量子计算模型和量子通信分别是在它们对应的经典理论上建立起来的， 因此两者之间也是存在联系的。例如k l a u c k 在文献【1 就用量子通信中求通信 复杂性下界的方法给出量子有限自动机的状态数下界，表明量子有限自动机 以l a sv e g a s 2 方式接受语言时不能比d f a 的状态数多项式少。a m b a i n i s 等【2 】以 及n a y a k 3 用量子通信中关于编码的方法讨论了量子有限自动机的状态复杂性 问题，证明接受语言l m = w 0 1 w o ，1 ) + ，i w i m ) 的量子有限自动机比接受 该语言的d f a 的状态数指数性增加。另一方面，或许也可以考虑基于量子有限 自动机的通信协议的描述和验证，甚至可以考虑更多的量子自动机到其它方面 的应用。例如n i s l l i m u r a 和y a l i n a l 【a l m i 1 4 1 就考虑了量子有限自动机到量子交互式 证明系统( q u a n t u mi n t e r a c t i v ep r o o fs y s t e m s ) 的应用。有关量子计算模型和量 1 通信复杂性是关于通信的一个重要研究方向，它关注的是通信协议中通信双方相互交换信息的多少。 2 具有概率行为的计算模型m 以l 笛榉方式接受语言l 是指识别l 时不会出错，但可以以一定概 率e 输出“不知道”。更具体地，当z l 时，m 以大于1 一e 的概率接受z ，以小于e 的概率输出“不知道”； 当ogl 时，m 以大于1 一e 的概率拒绝z ，以小于e 的概率输出“不知道” 2 量子计算模型的等价性判定及量子通信中的若干基本问题 子通信更深层次的联系，值得我们进一步探索。 本文所研究的量子计算模型是指量子计算的理论模型，而非物理实现模型。 对量子计算模型的研究是从理论上对量子计算的能力和局限性进行探索，并且 通过与对应经典计算模型进行比较，进一步认识量子计算的本质。 通信一直是信息科学研究的一个核心内容。近二十来，量子力学与信息科 学的交叉产生一个新兴的学科一量子信息学。自然地，人们把量子力学的特性 引入到通信理论里面来，期待二者的结合能产生一种更加强大的通信方式。从 而，量子通信作为量子信息的一个重要分支，日益受到学术界的关注。量子通 信【1 5 ，1 6 ，17 范围之广不是本文所能全面涉及的，因此本文将重点讨论其中的 两个基本问题：量子运算的区分以及用、- 态作为超密编码和隐形传态的共享资 源。 量子运算的区分属于量子信息分辨的范畴。量子信息分辨讨论的是如何对 量子信息进行区分，它是量子通信的基础性问题。其中量子状态的区分是信息 分辨的基本形式，而量子运算的区分是状态区分的进一步延伸，是量子信息分 辨的重要形式。量子通信中另一个基本问题是关于超密编码和隐形传态的研究。 超密编码和隐形传态作为两个重要的量子通信模型关系紧密，人们经常把它们 放在一起讨论。它们是量子通信与经典通信相比有趣性和优越性的重要表现， 对它们的研究吸引了众多学者。在超密编码和隐形传态中起关键作用的是量子 纠缠态，而用、u 态作为超密编码和隐形传态的共享资源近来也引起了人们不少 关注。 下面分别从量子计算模型，量子运算的区分，以及、v - 态作为超密编码和隐 形传态的共享资源几个方面作更详细的介绍。 1 1 量子计算模型 在过去的近二十年，量子计算引起了学术界的广泛注意f 1 8 ，1 9 1 。在一定 程度上，量子计算的思想来源于物理和计算的关联性f 1 8 ，1 9 1 。我们简要回顾 一下该领域的一些相关工作。由于量子物理的可逆性，b e n n e t t 2 0 在1 9 7 3 年证 明任意给定的图灵机都可由一个可逆图灵机有效模拟。1 9 8 0 年，b e n i o f f 2 1 首 先考虑基于量子力学的计算设备可能和经典计算机计算能力一样强。然 后，f e y 眦a n f 2 2 】指出在经典计算机上不能有效模拟量子力学系统，并且 他提出基于量子力学规律的计算机可能可以有效实现上述模拟。在这之 第一章引言 3 后，d e u t s c h 2 3 把b e n i o f f 和f e y n m a n 的思想形式化，于1 9 8 5 年重新分析了c h u r c h - t u r i n g 命题，并定义了量子图灵机( q t m ) 。1 9 9 3 年，y a o 2 4 h 正明了量子图灵机 和量子电路之间的等价性。特别地，1 9 9 4 年s h o r 2 5 发现了基于量子计算机的多 项式时间的大数因子分解算法，并且之后g r o v e r 2 6 发现了在无序数据库寻找特 定目标的平方根时间算法。从这之后，量子计算激起了越来越多人的兴趣。 经典自动机在计算理论中扮演着十分重要的角色【2 7 1 。而量子自动机，作为 一种重要的计算设备，可看作量子计算的理论模型。因此，从理论角度来看，对 量子自动机的探索有助于对量子计算的能力和局限性的深刻理解，有助于澄清 量子计算机的优点和缺点。 如经典自动机一样，量子自动机也涉及到多种不同类型，包括量子有 限自动机( q f a ) 2 ，2 8 ，2 9 ，3 0 ，3 1 ，3 2 ，3 3 ，量子时序机( q s m ) 3 4 ，3 5 ，量子 下推机( q p d a ) 3 6 ，3 7 ，3 8 】，量子图灵机( q t m ) 2 3 ，3 9 ，4 0 】，量子细胞自动 机( q u a n t u mc e l l u l a ra u t o m a t a ) 【1 8 ，4 1 ，4 2 】，以及基于量子逻辑的自动机理 论一正交模格值有限自动机( 1 - v f a ) 4 3 ，4 4 ，4 5 ，4 6 ，4 7 ，4 8 ，4 9 等。顺便提一下， 量子细胞自动机【5 0 】作为一种重要的量子计算模型吸引了物理界和计算机界众 多学者的关注。量子自动机的转移函数必须服从量子力学运动规律，因而具有 酉性( 可逆性) ，并且计算结果要通过测量以一定的概率得到。 本文主要讨论量子有限自动机和量子时序机，其它一些计算模型虽被提及， 但不作详细讨论。这方面的综述性文献也可参考f 5 1 1 。 有限自动机作为经典计算理论中一种最基本的计算模型得到了深入而广泛 的研究，文献f 27 1 中对此有系统的介绍。因此，作为有限自动机的一种量子化形 式，量子有限自动机( q f a ) 被提出来，并在学术界得到了广泛关注。量子有限自 动机首先f l j m o o r e 和c r u t c h f i e l d 2 8 1 以及k o n d a c s 和w a t r o u s 2 9 分别以不同形式 提出来，然后得到其他学者的进一步研究。大体上，量子有限自动机可分为两 类：单向量子有限自动机( i q f a ) 和双向量子有限自动机( 2 q f a ) 。i q f a d p 每读 入一个字符时，带头必须往右移动一格，而2 q f a h b 每读入一个字符时，带头可 左移一格，右移一格或者不动。另外，注意 ! l j a m a n o 和1 w a m a 3 3 处理了一种称 为1 5 向量子有限自动机( 1 5 q f a ) 的模型，其中带头只能右移或者不动。特别地， 文献 3 3 1 证明空问题对1 5 q f a 是不可判的。所谓空问题即判断一个计算模型接 受的语言是否为空，它是自动机理论中的基本问题之一。 单向量子有限自动机( 1 q f a ) 中有两个重要的子类：测量一次的i q f a ( m o 4 量子计算模型的等价性判定及量子通信中的若干基本问题 i q f a ) 2 8 和测量多次的i q f a ( m m 一1 q f a ) 2 9 】。在m o 一1 q f a 和m m - 1 q f a 中测 量是用来决定机器是否接受或者拒绝的。我们知道，测量操作是量子计算中的 一个重要步骤，是提取信息的必要手段。因此，在文献2 ，3 2 ，5 2 中一些更具一 般性的量子有限自动机模型被提出，其中任意的投影测量都可以作为计算的中 间步骤。特别地，b e r t o n i 等在文献3 2 1 中刻画了一种称为带控制语言的单向量子 有限自动机( c l - 1 q f a ) ，总体上它也属于单向量子有限自动机。 到目前为止，关于量子有限自动机( q f a ) 的研究工作主要集中在对其语 言识别能力3 的刻画。下面对这方面已有主要工作作简要回顾。m o 一1 q f a 识 别的语言正好等价于群自动机( 一种特殊的有限自动机) 识别的语言3 0 1 ，因而 属于正则语言的真子集。m m - 1 q f a 作为m o 1 q f a 的更一般形式，不仅可识 别m o 1 q f a 所能识别的所有语言，也能识别m o 1 q f a 所不能识别的语言，例 如a + b + f 3 1 】。但是，m m - 1 q f a 所能识别的语言也只是正则语言的真子集【2 9 】， 例如不能识别正则语言 o ，6 ) + a 2 9 】。c l - 1 q f a 所识别的语言正好等价于正则语 言【3 2 ，5 3 】。 与1 q f a 相比，2 q f a 的语言识别能力显著增强。k o n d a c s 和w a t r o u s 2 9 证 明2 q f a 不仅能识别所有正则语言，还能在线性时间内识别非正则语言l = a 佗b 1 f n o ，而2 q f a 的经典对应模型一双向概率自动机不可能达到同 样的效果 5 4 ，5 5 ，5 6 】。另外，考虑至u 2 q f a 2 9 】的带头是量子的、不易实现， 在文献【5 7 】中a m b a i n i s 和w a t r o u s 进一步提出了带经典状态的量子有限自动 机( 2 q c f a ) ，其中带头是经典的，并且证明2 q c f a 不仅能在多项式时间内识 别厶叼= a n 扩i 礼n 】，还能识别回文语言l 叫= 【z a ，6 州z = z r ) ( 指数 时间内) 。值得指出的是，双向概率自动机在任意时间内都无法识别回文语 言l 州【5 8 】o 上述几种主要量子有限自动机模型可识别的语言关系可用图1 1 形象 地表示出来。 关于量子有限自动( q f a ) 另一个值得讨论的问题是状态复杂性问题。经 典有限自动机状态复杂性问题包括几个方面，有关这方面的详细介绍可参 考y u 5 9 。目前对q f a 状态复杂性的研究主要是考虑：给定一个语言，找出状态 数尽可能少的q f a 接受它。这方面的文献可见【2 ，3 ，3 1 ，6 0 ，6 1 ，6 2 ，6 3 ，6 4 ，6 5 。 有趣的是，与经典有限自动机的状态复杂性相比，量子有限自动机的状态复杂 性有时更优，有时更差。例如文献【3 1 】中证明对语言厶= n i ：i , - 被素数p 整除1 ， 3 本文中，称一个q f a 接受( 识别) 语言l 通常是指以有界误差方式接受【3 0 】 第一章引言 5 图1 1 ：其中m 0 1 q f a ，m m 1 q f a ，c l 一1 q f a ，2 q f a 分别表示它们所代表的模 型以有界误差方式识别的语言类，r l 和n r l 分别表示正则语言和非正则语 言。它们之间有如下关系：m o 一1 q f a c m m - 1 q f a c c l i q f a = r l c 2 q f a ，并 且2 q f a d n r l # d 。 存在一个m m - 1 q f a 接受该语言，其状态数要比任何接受该语言的经典有限自 动机的状态数指数性减少。另一方面，文献【2 ，3 】证明接受语言l m = w o l w o ，1 ) ，l w i m i 拘m m - 1 q f a 将比接受该语言的d f a 的状态数指数性增加。 关于量子有限自动机( q f a ) 的另一个重要问题是其等价性的讨论。我们 知道，在经典计算理论中有两个重要问题分别是有限自动机的等价性和最小 化。这两个问题是紧密相关的，通常等价性判定是最小化的基础。文献 2 7 】中 对两个d f a 是否等价构造了有效的判定算法，并且以此为基础给出了寻找最 小d f a 的算法。文献 6 6 】中讨论了概率自动机的等价性，给出了两个概率自动机 等价的充分必要条件，之后文献【6 7 1 中给出了多项式时间的等价性判定算法。关 于量子计算模型的等价性同样是一个值得考虑的重要问题。目前这方面的工作 主要集中在量子有限自动机( q f a ) 和量子时序( q s m ) 两方面。下面就此作简要 回顾。 6 量子计算模型的等价性判定及量子通信中的若干基本问题 量子时序机( q s m ) 作为随机时序机f 6 6 1 的量子化形式于2 0 0 0 年由美国学 者g u d d e r 3 4 提出，并_ 且g u d d e r 在文献f 3 4 1 中提出了一个关于量子时序机等价性 的问题。其后，邱道文教授在文献【3 5 】中对该问题进行了部分解答。近来，李绿 周和邱道文教授在文献f 6 8 ，6 9 中完全解决了该问题。更为具体地，给出了两个 量子时序机等价的充分必要条件，并构造了多项式时间的等价性判定算法。 关于m o 一1 q f a 的等价性问题首先在文献3 0 】给出了主要解决思路，然后文 献 7 0 】对此做了细化处理。在文献 6 9 】中，从q s m 的角度对m o 一1 q f a 的等价性问 题作了进一步讨论。2 0 0 0 年，国际著名学者g r u s k a 教授在文献7 1 1 中提出：是否 可判定两个m m 一1 q f a 的等价性? 其后，对该问题虽然有一些讨论【7 0 1 ，但是后 来被发现是错误的。直n 2 0 0 s 年，李绿周和邱道文教授在文献f 7 2 1 中正确地解决 了该问题，给出了两个m m 一1 q f a 等价的充分必要条件，并说明了存在多项式时 间的等价性判定算法。在文献1 7 2 中，作者也给出了两个c l - 1 q f a 等价的充分必 要条件。最近，中山大学邱道文教授和加拿大西安大略大学s h e n gy u 教授在文 献 7 3 】中考虑了多字符量子有限自动机的等价性问题，给出了输入字母表只有 一个元素时两个多字符量子有限自动机等价的充分必要条件。进一步，邱道文 教授等在文献【7 4 】中考虑了输入字母表为一般的情形，给出了两个多字符量子 有限自动机等价的充分必要条件，并给出了多项式时间的等价性判定算法。 1 2 量子运算的区分 量子通信中一个基础性问题是量子信息的分辨，它可包括量子状态的区分， 量子运算的区分，以及量子测量的区分。量子状态的区分是量子信息分辨的基 本形式。只有对量子状态有所区分，才可能获取状态所携带的信息。可以说量 子状态的区分是量子通信中一切问题的基础。正因为其重要性，量子状态的区 分吸引了众多学者，关于这方面的研究存在大量工作，例如f 7 5 ，7 6 】，并且目前 仍然不断有新的研究成果出现。 量子测量的区分以及量子运算的区分是对量子状态区分的进一步延伸。量 子测量的区分首先在文献【7 7 】中提出，关于这方面的研究工作不多。本文主要关 注量子运算的区分。量子运算是对开放量子系统运动规律的刻画。形象地，可以 把量子运算当作一台具有输入和输出端口的物理设备。现在有两台这样的物理 设备以及它们的功能说明书，由于标签丢失需要对它们重新进行确认，或者说 需要重新把功能说明书贴到对应的设备上。一个自然的做法是给它们相同的输 第一章引言 7 入，然后通过观测它们不同的输出来对其进行身份识别。在这过程中，可以多 次使用这些设备，也可借助其它辅助设备。所谓“多次使用”严格来说应指“存 在多个拷贝”，即存在多台一样的设备。另外，这些设备还可能是多体的( 被多 方共享的) ，即每台设备有多组输入输出端口，其中某几组输入输出端口被一方 控制，另几组输入输出端口被另一方控制。这时要对它们进行区分，通常要求 只能采用局域操作和经典通信，简称为l o o c 4 操作。 从一般形式上讨论量子运算的区分是比较困难的，因此人们首先从其特 殊情形一酉变换的区分开始讨论。酉变换作为量子运算的特殊情况结构比较 简单，具有较好的性质，因此关于这方面的研究工作比较深入。有关酉变换区 分的主要文献有【7 8 ，7 9 ，8 0 ，8 1 ，8 2 ，8 3 】，其中大体上可以分成两类：全局区分 和l o c c 区分。 所谓酉变换的全局区分是指待区分的酉变换完全被一个操作者所拥 有，因而他可以随意地选择输入态，并且可以做任何物理上可允许的操作。 在2 0 0 1 年，a c f n 7 8 和d a r i a n o 等 7 9 的研究工作表明：任意两个不同的酉变 换u 和y 在只有一个拷贝的前提下可被精确区分，当且仅当有o ( u t v ) 7 r ，其 中e ( u ) 表示在单位圆上包含u 的所有特征值的最小弧长。然而，当待区分的酉 变换存在多个拷贝时，情况大不相同。具体地，a d n 7 8 和d a r i a n o 等 7 9 1 各自独 立地证明任意两个不同的酉变换在有多个拷贝的条件下都可精确区分。但是， 在这过程中必须使用一个多体纠缠态作为输入，而纠缠态作为一种宝贵的物理 资源通常是很难制备的。因此，2 0 0 7 年d u a n 等8 0 1 进一步考虑了该问题，设计了 一个新的区分方案，证明任意两个不同的酉变换在有多个拷贝的条件下可不借 助纠缠态精确区分。 关于多体酉变换的l o c c 区分，分别在2 0 0 7 年和2 0 0 8 年，z h o u 等8 1 1 以及d u a n 等 8 2 】各自独立地证明任意两个不同的多体酉变换在有多个拷贝的条件下可以 以l o c c 方式精确区分。但是为了达到精确区分的目的，在文献 8 1 ，8 2 】中要求 有一方必须使用多体纠缠态作为输入5 ，本文称这种被一方所控制但被多个子 系统共享的纠缠态为局域纠缠。文献【8 1 ，8 2 】的研究工作似乎表明这种局域纠缠 对酉变换的l o c c 精确区分是必要的。有趣的是，2 0 0 8 年李绿周和邱道文教授 在文献【8 3 】中证明了作用在d 圆d 系统上的任意两个不同的酉变换在有多个拷贝 4 “l o c a lo p e r a t i o n sa n dc l a s s i c a lc o m m u n i c a t i o n ”的缩写。 5 这里需要多体纠缠态并不是因为待区分的酉变换是多体的，而是由区分方案本身所决定的。换句话 说，即使要区分的是二体酉变换，同样需要多体纠缠态作为输入。 8 量子计算模型的等价性判定及量子通信中的若干基本问题 存在的条件下，可不借助任何纠缠地以l o c c 方式精确区分。因此说明酉变换 的l o c c 精确区