（计算机软件与理论专业论文）量子小波变换算法设计与应用研究.pdf

摘要摘要量子计算是数学、物理学和计算机科学相交叉的新近的研究领域，经过近二十年的研究历程，此研究领域已取得了迅猛的发展。量子计算的特性和功能被渐次发现、理解，正在转变成为推动它快速发展的动力。关于量子计算的研究主要集中于两个方面：一方面根据量子力学的基本原理设计的量子算法，典型的有大数因子分解( s h o r 算法) 、无序数据搜索( g r o v e r 算法) 以及量子系统的模拟等问题上提出了诸多量子算法。另一方面根据不同的量子计算实现方法提出了许多实现方案。仿真平台的实现为量子计算的仿真实现提供了平台的支撑，更是量子算法可行性验证。量子算法必须在量子计算机上执行才能真正体现其优越性。但目的量子计算机的研究还处于物理试验攻克阶段，其主要实现方案包括核磁共振、光量子、离子阱等试验方案。随着小波理论研究的深入，小波变换在信号分析等领域有了广泛的应用，小波变换在量子计算领域的研究也逐步受到重视。但目前量子小波变换的应用还不多。文章在量子傅立叶变换算法的基础上，运用幺f 变换理论给出量子h a a r小波变换和d a u b e c h i e s d ( 4 ) 小波变换的量子算法逻辑结构分解，同时分析三量子位小波变换过程得出量子小波变换的应用方法。运用m a t h e m a t i c a 仿真实现了量子小波变换算法，同时给出了量子小波变换算法在信号分析上的应用。最后结合量子计算机的结构和程序设计语言，通过基于随机存取量子计算机( q u a n t u mr a n d o m a c c e s sm a c h i n e ) 结构的q 1 a n g u a g e 描述了量子计算机上的小波变换算法及实现方法。第一章：介绍了量子计算的研究历程与现状，以及本文主要研究的方法、内容和意义。第二章：对量子计算进行整体概述，从量子位、量子逻辑门、量子并行计算等方面来介绍量子计算。第三章：详细介绍量子h a a r 小波变换及逻辑分解，对三个量子位h a a r 小波变换进行数学分析，同时分析得出了该算法的时间复杂度。第四章：详细介绍d a u b e c h i e s d ( 4 ) d x 波变换及逻辑分解，对三个量子位d a u b e c h i e s d ( 4 ) 小波变换进行数学分析，同时分析得出了该算法的时间复杂度。第五章：运用m a t h e m a t i c a l6 0 仿真实现量子小波变换算法，同时实现了其在信号分析中的应用。第六章：结合q r a m 量子计算机结构和基于此结构的q l a n g u a g e ：给出了量子小波变换算法和应用的q l a n g u a g e 描述。第七章：对量子算法的总结以及展望。关键词：量子计算，量子逻辑门分解，量子小波算法，量子小波变换仿真实现，量子随机存取机，量子小波算法应用a b s t r a c ta b s t r a c tq u a n t u mc o m p u t i n gi sar e c e n t l yd e v e l o p e ds u b j e c tc r o s s e db ym a t h 、p h y s i c sa n dc o m p u t e rs c i e n c e d e p e n d i n go nr e c e n tt w e n t yy e a r sr e s e a r c h ，s w i f ta n dv i o l e n td e v e l o p m e n th a sb e e ng o t t e ni ni t se x t e n s i o na n dm e a n i n g q u a n t u mc o m p u t i n g sc h a r a c t e r sa n df u n c t i o n sh a v eb e i n gf o u n da n dt r a n s f o r m e dt oi t s q u i c k l yd e v e l o p i n gp o w e r t h er e s e a r c ho fq u a n t u mc o m p u t i n gm a i n l yf o c u so nt w od i r e c t i o n s ：o n es i d e ，b a s e do nb a s i cq u a n t u mm e c h a n i c s t h e o r i e s ，al o to fq u a n t u ma l g o r i t h m sh a v eb e e nd e s i g n e d ，w h i c hi n c l u d i n gt h ei m p o r t a n tl a r g ep r i m ef a c t o r i z a t i o na l g o r i t h m ( s h o ra l g o r i t h m ) 、t h eu n s t r u c t u r e dd a t a b i a s es e a r c ha l g o r i t h m ( g r o v e ra l g o r i t h m ) a n dm a n ya l g o r i t h m sa b o u ts i m u l a t i n gq u a n t u ms y s t e m ；o nt h eo t h e rs i d e ，b a s e do nd i f f e r e n tw a y so fq u a n t u mc o m p u t i n g se s t a b l i s h m e n t ，an u m b e ro fe x p e r i m e n t a ls c h e m e sh a v eb e e np r o p o s e dw h i c hc o u l ds u p p o r tt h ee x e c u t i o no ft h e s ea l g o r i t h m s ，m o v i n gq u a n t u mc o m p u t a t i o nf r o mt h er e a l mo fs p e c u l a t i o nt or e a l i t y w i t hg r a d u a ld e e p e rr e s e a r c h w a v e l e tt r a n s f o r m sh a v eb e e nw i d e l yu s e di ns i g n a la n a l y s i sa n di m a g ep r o c e s s i n ga r e a w a v e l e tt r a n s f o r m si nq u a n t u mc o m p u t i n ga r e ah a v e b e e nr e c o n g n i z e dg r a d u a l l y i nt h eb e g i n n i n go ft h i sp a p e r , t h ea l g o r i t h m so fq u a n t u mh a a rw a v e l e ta n dq u a n t u md a u b e c h i e s - d ( 4 ) w a v e l e tt r a n s f o r ma r ei n t r o d u c e d ，w h i c ha r eb a s e do nt h eq u a n t u mf o u r i e rt r a n s f o r i l l t h e nq u a n t u mw a v e l e tt r a n s f o r m s l o g i c a lf a c t o r i z a t i o na r ep r o p o s e db yu s em u l t i p l e 。q u a n t u mo p e r a t o ra l g e b r aa n dd e n s i t ym a t r i xt r a n s f o r mt h e o r y t h i r d l y , w eu s em a t h e m a t i c a lt os i m u l a t et h eq u a n t u mw a v e l e tt r a n s f o r ma n de s t a b l i s hi t s a p p l i c a t i o n si ns i g n a la n a l y s i sa n di m a g ep r o c e s s i n g f i n a l l y , c o m b i n i n gw i t ht h er e s e a r c hc i r c u m s t a n c eo fq u a n t u mc o m p u t e ra n dq u a n t u mp r o g r a m m i n gl a n g u a g e ，w ed e s c r i b eq u a n t u mw a v e l e tt r a n s f o r ma l g o r i t h m sa n di t s a p p l i c a t i o nw a y sb yq - l a n g u a g ew h i c ha r eb a s e do nt h e q r a m ( q u a n t u mr a n d o ma c c e s sm o d u l e ) c h a p t e r1 ：w ei n t r o d u c et h eh i s t o r yo fq u a n t u mc o m p u t i n ga n di t ss t a t u st o d a y ,a n dd e s c r i b et h em e t h o d ，c o n t e n ta n dm e a n i n go fo u rr e s e a r c h c h a p t e r2 ：w es u m m a r i z eq u a n t u mc o m p u t i n g f r o ms e v e r a la s p e c t s ，s u c ha sq u b i t s ，q u a n t u m1 0 9 i cg a t e sa n dp a r a l l e lc o m p u t i n ge t c c h a p t e r3 ：w ei n t r o d u c et h eq u a n t u mw a v e l e th a a rt r a n s f o r i l la l g o r i t h m si nd e t a i l ，g i v et h ef u r t h e rd e c o m p o s i t i o no fq u a n t u mh a a rw a v e l e tt r a n s f o r r na n di t sc o m p l e x i t y , a n da n a l yt h ep r o c e s s i n go ft r a n s f o r m c h a p t e r4 ：w ei n t r o d u c et h eq u a n t u mw a v e l e td a u b e c h i e s d ( 4 ) t r a n s f o l l t l la l g o r i t h m si nd e t a i l ，g i v et h ef u r t h e rd e c o m p o s i t i o no fq u a n t u md ( 4 ) w a v e l e tt r a n s f o r ma n di t sc o m p l e x i t y , a n da n a l yt h ep r o c e s s i n go f t r a n s f o r m c h a p t e r5 ：w eu s et h em a t h e m a t i c a l 6 0s o f t w a r et os i m u l a t et w oq u a n t u mw a v e l e tt r a n s f o r ma l g o r i t h m sa n di t s a p p l i c a t i o n si ns i g n a la n a l y s i s c h a p t e r6 ：c o m b i n i n gw i t ht h er e s e a r c hc i r c u m s t a n c eo fq u a n t u mc o m p u t e ra r c h i t e c t u r ea n dq u a n t u mp r o g r a m m i n gl a n g u a g e ，w ed e s c r i b eq u a n t u mw a v e l e tt r a n s f o r ma l g o r i t h m sa n di t s a p p l i c a t i o nw a y sb yq - l a n g u a g ew h i c ha r eb a s e do nt h ena b s t r a c tq r a m ( q u a n t u mr a n d o ma c c e s sm o d u l e ) c h a p t e r7 ：s u m m a r i z ea n df o r e c a s tt h eq u a n t u mc o m p u t i n g k e y w o r d s ：q u a n t u mc o m p u t i n g ，t h ef a c t o r i z a t i o no fq u a n t u ml o g i cg a t e ，q u a n t u mw a v e l e tt r a n s f o r ma l g o r i t h m ，s i m u l a t i o no fq u a n t u mw a v e l e tt r a n s f o r m ，q u a n t u mr a n d o ma c c e s sm a c h i n e ，q u a n t u mw a v e l e tt r a n f o r m s a p p l i c a t i o ni i i独创生声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含本人为获得江南大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。期：- 0 0 9 年子目召日关于论文使用授权的说明本学位论文作者完全了解江南大学有关保留、使用学位论文的规定：江南大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文，并且本人电子文档的内容和纸质论文的内容相一致。保密的学位论文在解密后也遵守此规定签名：主丝苎盘导师签名：二弓l 日期：。坦进年驰丑l 一第一章绪论第一章绪论1 1 引言量子物理从普朗克提出量子的概念至今已经走了整整一百年的历程。在这一百年中，量子物理给人类的生活带来翻天覆地的变化，尤其是进入二十世纪后半叶，随着激光器的出现和半导体工业的突飞猛进，更彰显出科学的威力。但即便是这样成功的理论，围绕它的争论却从来不曾间断过。对其提出质疑的人当中不乏这一领域的开创者，如薛定谔、爱因斯坦等人，而拥护量子力学的则是以玻尔和海森伯等人为代表的哥本哈根学派。他们争论的焦点在于：量子力学描述的物理实在具有无法消除的随机性，而这是以爱因斯坦为代表的持经典决定论观点的物理学家所不能接受的，他们认为量子力学对物理世界的描述是不完备的，世界应该被更为基础的理论来支配。随着论战的升级，爱因斯坦等人提出了量子纠缠态的概念，进而引发了对量子力学基本原理的检验。虽然，迄今为止，绝大多数的证据显示了哥本哈根学派的胜利，似乎围绕这一科学问题的争论应告一段落，但正是由于这两股科学洪流的不断地砥砺和求索，人们更加深了对这门科学的认识，进而诞生了后来的量子信息学，其中包含了量子计算、量子通信、量子密码、量子传念、量子密集编码等。量子计算的发展源于1 9 8 2 年f e y n m a n 1 】指出按照量子力学原则建造的新型计算机对解某些问题可能比常规计算机更有效。在此基础上，1 9 8 5 年d e u t s c h指出利用量子念的相干叠加性( c o h e r e n ts u p e r p o s i t i o n ) 可以实现并行的量子计算【2 】o1 9 9 4 年s h o r 提出大数因子分解的量子算法：如果在量子计算机上计算，求一个n 位大数的两个质因子所需的时间只是n 的多项式，而在常规计算机上计算，所需的时间则为0 ( 1 3 2 ) 【3 】。当n 很大时，常规计算机变得无能为力。由于大数因子分解是难解问题( i n t r a c t a b l ep r o b l e m ) ，已广泛用于密码通信，如果实现了有现实意义的量子计算机，则大数因子分解对密码学将失去意义。自从大数因子分解量子算法提出以来，在国际物理学界掀起了研究量子计算的热潮。第一台电子计算机诞生于1 9 4 5 年。6 0 多年来几乎所有的电子计算机都是基于v o nn e u m a n n 体系结构，其计算模型是a l a nt u r i n g 于1 9 3 6 年提出的图灵机( t u r i n gm a e h i n e ) 模型。2 0 世纪6 0 年代丌始的数十年内，经典计算机硬件能力的发展近似地遵从m o o r e 定律；然而大多数观察家预言这将在2 l 世纪的前2 0年内结束。制造计算机的传统方法开始显得力不从心，当电子器件的尺度越来越小时，它的功能丌始受到量子效应的干扰。m o o r e 定律最终失效问题的一个可能解决办法是采用不同的计算模式。基于量子物理而非经典物理的量子计算由于其强大的并行计算能力和可以有效的模拟量子行为的能力而同益受到人们的关注。1 9 8 2 年，f e y n m a n 论证了用经典计算机模拟量子力学系统时，随输入( 粒子江南人学硕士学位论文数、自由度) 的增大其计算资源( 时间、空间) 消耗会指数增加。例如量子位态矢的h i l b e r t 空间，在n = 2 0 0 时是2 2 0 0 维矢量空间，要描述这个矢量空间中的一个典型态，将需要在经典计算机中记录2 2 0 0 1 个复数，这是任何经典计算机都不可能做到的。这一观察引起了f e y n m a n 推测，按照量子力学规律工作的计算机( 量子计算机) 可能可以避免这一困难，这就是最早的量子计算的思想。b e n i o f f 深入地研究了量子计算机是否比经典计算机更有效地问题，于19 8 2年定义了量子t u r i n g 机，描述了量子计算机的一般模型，研究了它的性质，说明了量子计算机的潜在能力【5 】。d e u t s c h 是第一个系统地表述了现在人们所理解的量子计算机模型。1 9 9 4 年，p e t e rs h o r 发现了第一个具体的量子算法，这个算法在设想的量子计算机上可以输入的多项式时间分解大数质因子，而求解大数质因子对经典计算机是个难题。这个问题对经典计算机是如此困难，以至于现在广泛使用的公开密码系统r s a 就是以这个问题的难解为基础的。1 9 9 6 年，g r o v e r 又发现了未加整理数据库数量级加速查询算法【6 】【”，而且用这种加速的查询算法有可能解决经典计算机上所谓的n p 难题，因而引起了人们的重视。早期的量子计算机实际上是用量子力学语言描述的经典计算机，并没有用到量子力学的本质特性，如量子态的叠加性和相干性。与经典计算机不同，量子计算机可以做任意的么正变换，在得到输出态之后，进行测量得出计算结果。因此，量子计算对经典计算做了极大的扩充，在数学形式上，经典计算可看作是一类特殊的量子计算。量子计算机对每一个叠加分量进行变换，所有这些变换同时完成，并按一定的概率幅叠加起来，给出结果。这种计算称作量子并行计算。除了进行并行计算以外，量子计算机的另一个重要用途是模拟量子系统，这项工作足经典计算机无法胜任的。从量子计算提出至今，在研究中经历过高潮期也经历过低谷。上世纪8 0 年代，从f e y n m a n 指出按照量子力学原则建造的新型计算机对求解某些问题可能比常规计算机更有效到d e u t s c h 指出利用量子念的相干叠加，| 生- ( c o h e r e n ts u p e r p o si t i o n ) 可以实现并行的量子计算可以说是量子计算的第一次研究高峰。上世纪9 0年代，随着s h o r 算法、g r o v e r 算法相继提出，量子计算经历了有史以来的第二次高潮。目前欧美等国都加大投入进行量反对子计算机硬件实现的研究工作。1 2 本课题的研究意义以及研究方法量子计算机( q u a n t u mc o m p u t e r ，q c ) 是一类遵循量子力学规律进行高速数学和逻辑运算、存储及处理量子信息的物理装置。当某个装置处理和计算的是量子信息，运行的是量子算法时，它就是量子计算。无论量子并行计算还是量子模拟计算，本质上都是利用了量子相干性。但是，在实际系统中量子相干性很难保持。在量子计算机中，量子位不是一个孤立的系统，它会与外部环境发生相互作用，导致量子相干性的衰减，即消相干。因此，要使量子计算成为现实，一个核心问题就是克服消相干。至今为止，世界2第一章绪论上还没有真正意义上的量子计算机。但是，世界各地的许多实验室正在以巨大的热情来追寻着这个梦想。目前关于量子算法的研究基本是在理论研究的基础上，结合相应的量子计算仿真器。研究量子计算机的目的并不是要用它来代替经典的计算机。量子计算机使得计算机的概念焕然一新，它也不同于其他计算机如光计算机核生物计算机等等，量子计算机要解决的问题也不是局限于一些经典计算机无法解决的问题。在传统的信息论中，通用计算机能用几个等价的模型表示。对应于不同的学科，说法也不同。例如，从数学角度看，一个通用的计算机是一个能够计算机局部递归功能的机器。计算机科学家会用“图灵机 模型。电子工程师可能更喜欢用逻辑线路来代替。而程序员可能更喜欢用通用的程序语言。对于量子计算仿真程序设计语言，首先需要建立量子计算语言和传统计算之间的对应关系。在一台传统的经典计算机上模拟量子计算机是个难题。它所需要的资源随着被模拟的量子内存数量增加呈指数增长，以至于连模拟一台只有几十个量子位的量子计算机也远远超过了现在能够制造的任何一台计算机的能力范围。量子计算机仿真器只是模拟非常小的量子计算机。但是，它的效率已经足够展示量子计算机算法背后的一些概念。因此，在量子计算机进入实用之前，在经典计算机上用量子计算机仿真器验证量子算法就显的特别重要了。因此，用经典计算机实现量子计算的仿真，具有重要的科研价值。1 3 本课题研究的主要内容在理论计算机科学的研究中，许多问题的解答都可归纳为只需要回答“是”或“非 的判定问题。一个判定问题如果能用多项式时问算法求解，那么它被称为p 类问题。人们已经发现有一大类问题至今还没有找到它的多项式时间求解，但并未证明它没有多项式时间算法，此类问题称为n p 类问题。量子计算机是服从量子力学规律的计算机，在量子计算机中求n p 难题，有可能得到多项式算法，其中最具代表性的成果是s h o r 提出的大数质因子分解算法。在量子计算机中，它能以多项式时间内分解得到一个大数的质因子。还有一些量子算法不是把指数算法变成多项式算法，而只是把一个需要n 步的计算缩小为步，例如g r o v e r 未整理数据搜索的量子算法。本文讨论利用量子计算机的独特性质来求解传统的n p 难题，量子傅立叶变换和量子小波变换。在量子计算中，量子f o 嘶e 肢换有着广泛的应用，在s h o r 算法和g r o v e r 算法中都应用了量子f o u r i e r 变换，而在时域和频域局部化性质方面都优于f o u r i e r变换的变换小波变换在量子计算上的研究仅限于h o y e r ，f i j a n y ，w i l l i a m s ，k l a p p e n e c h e 的工作。h o y e r 最早给出了h a a r 小波的量子电路。f i j a n y 和w i l l i a m s 1 2 】给出y h a a r d 、波和d a u b e c h i e s d ( 4 ) 小波的电路图。k l a p p e n e c k e d l 3 】研究了小波包的量子实现。但目前量子小波变换的应用却不多见。文章在量子h a a r 、d a u b e c h i e s d 4 d 波变换逻辑实现的基础上给出了其进一3江南大学硕十学位论文步的逻辑分解，同时对3 个量子位的量子h a a r 、d a u b e c h i e s - d 4 d s 波变换的过程进行了数学分析，计算得出量子h a a r d , 波变换算法的时间复杂度为0 ( r 1 2 ) ；量子d a u b e c h i e s d 4 d , 波变换算法的时间复杂度为0 ( n 2 ) 。而后运用m a t h e m a t i c a6 0仿真实现了上述两个量子小波变换算法，给出了其在信号的断点检测上的应用。最后结合q r a m 结构的量子计算机模型3 以及基于此结构的语言q 1 a n g u a g e ，将n位的量子h a a r d , 波变换用q 1 a n g u a g e 语言进行了算法描述。1 4 本章小结本章主要讨论了量子计算以及仿真实现在国内外的研究现状及其发展，讨论了量子计算这个新兴研究领域的相关问题，提出了量子计算及其仿真的实际意义和理论意义，最后简单的介绍了一下本课题的研究的主要内容。4第二章量子计算概述第二章量子计算概述2 1 引言任一孤立的物理系统都有系统状态空问( 复内积向量空间) ，系统完全由状态向量描述。量子力学系统的状态i 鼢随时间的演化由酉变换来刻画。即系统在时刻t 的状态i 奶 和系统在乙的状态ig t e 可以通过一个仅依赖于时问岛、岛的酉算子u 相联系：i 沙2 ) = u l y l ) )( 2 1 )量子系统在连续时间上的演化遵循s c h r 6 d i n g e r 方程【8 】：坊型：j i ( 2 2 )西一其中，是一个封闭系统的h a m i l t o n 量的固定的h e r m i t e 算子，壳为普朗克常量，其值由实验确定。解出( 2 2 ) 式得到：l 沙o ) ) = e - t h t h l 缈( o ) ) = u i 沙( o ) )( 2 3 )其中，u 为量子变换算符，i 矽( o ) 为原始输入数据，i ( 幻 为测量前的输出数据，式( 2 3 ) 是量子算法执行的基本表述。量子算法的优越性主要体现在计算过程中量子态的叠加( s u p e r p o s i t i o n ) 和量子纠缠( e n t a n g l e m e n t ) 上，许多量子计算上的优势如量子并行( q u a n t u mp a r a l l e l i s m ) 、量子非局域性( n o n 1 0 c a l i t y ) 、量子隐形传输( t e l e p o r t a t i o n ) 等皆是由此产生的。以下分别介绍有关概念。2 2 量子位( q u b it )2 2 1 单量子位在常规计算机中，信息单元用二进制的1 个位来表示，它不是处于“0 ”态就是处于“1 态。在二进制量子计算机中，信息单元称为量子位( q u b i t ) ，它除了处于“0 ”态或“1 ”态，还可处于叠加念( s u p e r p o s e ds t a t e ) 。叠加态是“0 念和“1 态的任意线性叠加，它既可以是“0 ”态又可以是“1 ”态，“o ”态和“l ”态各以一定的概率同时存在。通过测量或与其它物体发生相互作用而呈现出“0 态或“l 态。例如氢原子中的电子的基念( g r o u n ds t a t e ) 不h 第l 激发念( f i r s te x c i t e ds t a t e ) 、质子自旋在任意方向的+ 1 2 分量和1 2 分量、圆偏振光的左旋和右旋等。为了便于表示和运算d i r a c 提出用符号i 来表示量子态，i 是一个列向量称为k e t ；它的共轭转置( c o n j u g a t et r a n s p o s e ) 用 矽l 表示， 态和i1 ) 态的概率，且f 白i2 + f 白i2 = 1 。这表明i 奶是单位向量，也称i 鼢是规一化的( n o m a l i z e d ) 。在常规计算机中，一个数位的态是确定性的，而在量子计算机中，量子位的叠加念不是确定性的，而足概率性的。2 2 2 多量子位设有两个量子位，对两个经典位而占，共有四种可能状态：0 0 ，0 1 ，1 0 和11 。相应地，一个双量子位的四个基态，记做 0 0 ，f0 1 ，l1 0 ，i11 。一对量子位也可以处于这四个基态地叠加，因而双量子位的量子状态包含相应基态的复系数，有时称为幅度( 概率幅a m p l i t u d e ) 。这样描述双量子比特的状态向量为：i y ) = c o o l o o ) + c 。，1 0 1 ) + c 。1 1 0 ) + c ，。1 1 1 )更一般地，考虑n 量子位系统：i ) = c ，l x )其中川2 = 1( 2 4 )n 量子位系统的基态为l x ) ，量子状念由2 ”个幅度所确定。g = 5 0 0 时，这个数就超过了整个宇宙原子的估算总数。在任何传统计算机上存储所有这些复数都是不可想象的。h i l b e r t 空问的确是个巨大的空间，这样巨大的计算潜力使得量子计算变得更有吸引力。2 3 量子位的测量2 3 1 单量子位的测量对于单量子位的叠加态，当f 奶对j0 方向投影时，i 鼢变成了f 奶。= 白io ，这相当于在lo 方向对i 进行测量；当i 奶对1 方向投影时，l 变成了i 矽6第二章量子计算概述 ，= 白! l ，这相当于在j1 方向对j 鼢进行测量。对处于叠加态的量子位进行观察或测量时，叠加态将受到干扰并发生变化，这种变化称为坍缩。对于上述测量叠加态坍缩为基本态b o 。通过量子计算，由叠加念j 奶获得坍缩态i 鼢。、l 鼢。步骤：首先设两个基本量子态lo 、li ) ，其共轭态分别为 0i = 10 、 ( o l = 三翻，l 。) ( i = 三暑 ，i ) ( 。i = ；习，l - ) ( ，i = 三o c 2 5 )运用量子算符求l 鼢的坍缩态：f o ) ( o l o 沙) ) = l 三苫f g 。 o ) + c t f l ) ) = c 。l o ) ( l o y ) ) = 三? g 。l 。) + c 。l ) ) = c 。i )( 2 6 )式2 6 说明：10 ) 作用在l 奶上是将其中属于io 的成分取出，也就是说1o 投影，相当于在lo 方向上测量l 鼢。同样，j1 ，1 投影，即在i l 方向测量i 鼢。2 3 2 多量子位的测量对于两个量子位i y ) = c 0 0 10 0 ) + c 。10 1 ) + c 。1 1 0 ) + c 。1 1 1 ) 的情况，测量结果x ( = 0 0 ，0 1 ，1 0 或1 1 ) 出现的概率是jc ，l2 测量后，量子位处于ix 状态。概率和为1 的归一化条件可以表示为：，。 0 。) ：l c ，1 2 = 1 ，其中 o ，1 ) 2 意味着长度为2 ，每个字母从0 和1 中任取的符号串的集合。对于一个双量子位系统，可以只测量其中一个量子位，譬如第一个。单独测量第一个量子位，得到0 ，1 的概率分别为：l 锄i2 + 1 锄l2 ，1o 。l2 + i 白而测量第一个量子位的状态为o ，1 得到量子并行态分别为：lo o a - - 方io o + l11 ) ，i 伊 口2 方i0 1 + l1o ) ，i 伊 c 2 老lo o + i0 1 )测量l 妒 。时，测量一个量子位的态，将使另一个量子位的念与之相同：测量l 矽 厅时，测量一个量子位的态将使另一个量子位的态与之相反，但测量l 缈 f7江南大学硕+ 学位论文时，对右边那位的态不管如何测量，左边那位的态总是为10 。这就是量子理论中最具非直观特性的一个现象量子纠缠。2 4 基本量子运算2 4 1 并行量子位与k r o n e c k e r 内积并行的n 个量子位的有序集合称为n 位量子寄存器，它的系统态是n 个量子位态的k r o n e c k e r 积，用符号。表示，k r o n e c k e r 积表达式如下：设么= 2a q 0 。1 j 1 ，曰= 乏2 1 1 则：a 。b ：卜艿a r a bi ：【口l o b 口1 l b ja o o b o la 0 0 b l la l o b o la l o b l la o l b o la o l b l la l l b 0 1a l l b l l( 2 6 )因此，对于1 1 位量子寄存器，其叠加态位：i 沙) = j 纯一，纯一：) = i c p , , - i ) i 纯一：) o 圆l )( 2 7 )因此，在量子计算机中，处于叠加态的n 位量子寄存器中的数是从0 到2 ”一1的所有数，它们各以一定的概率同时存在。在常规计算机中，1 个n 位的寄存器只能保存1 个n 位二进制数；而在量子计算机中，1 个n 位的量子寄存器可以保存2 ”个n 位二进制数。量子寄存器位数的线性增长使存储空间指数增长，这是量予计算机的一个基本特点。2 4 2 受控量子位与k r o n e c k e r 和并行的n 个量子位的有序集合，当由其中一个或多个量子位( 控制量子位)的当日l 状态决定在另一个或多个量子位( 目标量子位) 上的量子门电路是否进行作用时，该操作称为量子控制操作。它的系统状态是目标量子位上的量子操作门电路状态与控制量子位的状态的k r o n e c k e r 和，用符号。表示，k r o n e c k e r 和表达式如下：设彳= 三：三o ： ，b = 三o 贝u ：彳。曰= 苫三 =a o o 口o l0 0a l oa l l0 00ol0ooo1其中彳是目标量子位上的量子操作门状态，口是控制量子位的状态。2 5 量子逻辑门任意一个单量子比特门的酉变换矩阵可以分解为【8 】：8( 2 8 )第二章量子计算概述tp 一滞u = e 懈i 。10l，2y- 一2p - f 黟1( 2 9 )0e7 其中口、y 和万是实数。第二个矩阵是普通的旋转矩阵，第一个和最后一个矩阵可以理解为在不同平面内的旋转。我们不需要考虑任意的口、y 和艿，但可以用它们的某些特殊的固定值任意逼近这些门，为此量子计算中定义了常用的基本量子逻辑门，要求这些门电路在物理上是易实现的。以下是基本的量子逻辑门介绍。2 5 1 量子非门经典计算机线路由连线及逻辑门构成。连线用于在线路间传送信息，而逻辑门负责处理信息，把信息从一种形式转换为另一种。例如，考虑一个经典位逻辑门，唯一的不平凡成员是非门，非门的操作由真值表定义：其中o 专1 ，l 专0 ，即将0 ，1 状态交换。量子非门的定义实际是把状态io 和l1 互换的过程，在1o 和i1 状态上定义量子非门的作用是io ) 一1 1 ) ，1 1 ) 专lo ) ；而o 和l1 之间的叠加念会发生什么，实际上，量子非门的作用是线性的，即把状态口10 + i1 变到io 和il 状态角色互换的新状态口l o ) + p1 ) 一口1 1 ) + p o ) 。事实上，这一线性行为是量子力学的一般属性。在量子力学中，量子非门是可以用p a u l i 矩阵形式表示。x ：l0 1l( 2 1 0 )l 1 o j量子非门作用于量子叠加态l y ) = 口lo ) + 纠1 ) 表示为：x f y ) = x c 口f 0 ) + l ，) ，= x 荔 = 耋c 2 ，因此，单量子位的量子门可以由2 2 矩阵给出。回顾归一化条件，要求量子状态口lo + i1 满足l 口1 2 + l 1 2 = 1 ，这对量子门作用后得到状态c , o = 口1 0 + l l 也是适用的。表示单量子位门的相应矩阵要满足幺正性( u n i t a r y ) 的条件，即u u = i ，其中u + 是u 的共轭转置，是2 2 的单位矩阵。对于非门来说，可以验证：x + x = ，。幺正性质是对量子门的唯一限制，每个幺正矩阵都定义了一个有效的量子门。和只有一种不平凡单位门非门的经典情形不同，有很多不平凡单位量子门。2 5 2w a ls h - h a d a m a r d 门对一个量子位进行的一种比较常见的变换是w a l s h - - h a d a m a r d 变换，对应的门电路为w a l s h - - h a d a m a r d ，即：9l10，_1y一2，一，-卫2y 一2r ；疵；宝一c口os1jo 枷江南大学硕士学位论文形= 黜二。i仫w - h 作用与j o 和11 分别为：形l o ) = 去( | o ) + 1 1 ) ) ，形1 1 ) = 去( i o ) 一1 1 ) ) 。、，二v 二形l0 相当于将o 顺时针方向旋转4 5 。，形1 1 相当于将l1 逆时针旋转1 3 5 。因为形+ 缈= ，所以w 变换是幺正变换。因为w = w t ，所以w 变换是厄米变换，w变换是可测量的。令1 石 = lx n - i x 。一2 x o ，则( w 圆w 圆w ) iz = wf 毛一1 i 一2 p owlx o 。若n = 2 ，毛= x o = l0 ，则( w w ) l0 0 - - 去( 10 0 + io l + i1 0 + i1 1 ) 。可以看出，对10 0 的每一位分别进行w h 变换可产生2 个量子位的2 2 个基本态叠加，即o o ，0 l ，1 0 和1 1 同时存在，每个存在的概率均为1 4 。同样对于n 个量子位，( wewe ew ) lo o 峙方驴九所以，当量子寄存器中的n 个原始数位全为0 时，对每一位分别进行w - h变换可产生2 ”个基本态的叠加，即产生从0 到2 ”一1 的所有二进制数，它们同时存在，存在概率均为l 2 ”。2 5 3 一位旋转门对一个量子位可以进行旋转变换r ：r = l 三0l( 2 1 3 )从上式可以看出r0 - - - - l0 ，r1 - - - - e 肇i1 。因为r + r = ，所以r 变换是幺正变换。由于可在0 与2 万之间连续变化，w - h 门与旋转门结合起来，可以实现一个量子位的任意幺正变换，旋转变换只是使l 矽 转动一个角度，没有逻辑意义，但在量子计算中会起到重要作用。2 5 4 量子受控非门受控非门是一个2 量子位的系统。这个门有两个输入量子位，分别足控制量子位和目标量子位。该门的作用可以表述如下：如果控制量子位置为0 ，则目标量子位将保持不变。如果控制量子位被置为1 ，目标量子位将翻转。其作用形式可表示为：l0 0 一10 0 ，l0 l 专l0 1 ，l10 _ l1 1 ，l1 1h i1 0 ( 2 1 4 )另一种描述受控非门的方法是将其视为经典异或门的推广，因为该门的作用可以总结为：i x ，y 哼i x ，x o 少 ，其中。为模2 加法，而这正是异或运算所做的。也就是说，控制量子位和目标量子位做异或运算，并将结果保存在目标量子位中。l o第二章量子计算概述受控j l - - f - j 的矩阵表示：u c =loo1o oo oo000o11o( 2 1 5 )容易验证的第一列表示对10 0 的变换，第二、第三和第四y , j n 分别表示对0 1 ， 1 0 和 11 的变换。因为嘛= i ，所以致w 是幺正矩阵，也即受控非门是幺正变换。除了受控非门之外还有许多其他重要的量子门，不过由于任意的多量子位门都可由受控非门和单量子位门组合而成，因此，从某种意义上说，受控非门和单量子位门是所有其他门的原型。2 6 量子并行性量子并行性是许多量子算法的一个基本特征【2 l 】。简言之，量子并行性使量子计算机可以同时计算函数f ( x ) 在许多不同的x 处的值。设f ( x ) ： o ，1 ) _ 0 ，1 是具有一位定义域和值域的函数。在量子计算机上，计算该函数的一个简单办法是：考虑初态为ix ，y 的双量子位的量子计算机。通过适当的逻辑门序列可以把这个状念变换为ix ，yof ( x ) ，这里。表示模2 加法，第一个寄存器称为数据寄存器，第二个称为目标寄存器，映射x ，y - - - ix ，ye bf ( x ) 叫做u s ，容易证明它是幺正的。如果y = 0 ，则第二个量子位的最终状态就是f ( x ) 的值。考虑图的线路，把u i 加到计算基以外的一个输入。数据寄存器中是叠加态( 10 + i1 ) 2 ，这可由w 一1 1 门作用到io 上得到。于是应用u ，得到状态：l q ：! q ! 三兰! ! ：乏! ! ! 三( 2 1 6 )2这是一个值得注意的状态，不同的项同时包含f ( 0 ) 和f ( 1 ) ，看起来似乎同时对x的两个值计算了f ( x ) 。与经典的并行不同，那罩多重f ( x ) 电路同时运行，而这里，利用了量子计算机处于不同状态的叠加念的能力，单个f ( x ) 线路用来同时计算多个x 的函数值。利用w h 变换，这个过程很容易推广到任意数目的量子位上的函数。该变换就是n 个w - hf - j 同时作用到n 个量子位上。例如图是n = 2 ，初态全为10 的情况，输出则是：( 与笋) ( 与笋) = 坠业掣堕业汜m我们用形。2 表示两个w - h 门的并行作用。更一般的，n 重量子位上的w h 变换从全io 出发，得到：_ 7 lx( 2 1 8 )江南人学硕十学何论文其中求和是对x 的所有可能取值，并用形鼽表示这个作用。可见，w - h 变换产生了对所有计算基态的平衡叠加( e q u a ls u p e r p o s i t i o n ) ，而且，它的效率非常高，仅用r 1 个门就产生了2 ”个状态的叠加。可以采用下述方法进行n 位输入x 和单位输出厂 ) 函数的量子