（计算机软件与理论专业论文）多量子位量子小波变换算法及其仿真实现.pdf

摘要摘要量子计算是新近发展起来的，利用量子力学原理进行信息处理的前沿学科。随着理论与技术的成熟及更多专家和学者加入该领域的研究，量子计算得到突飞猛进的发展，对计算机科学的发展和进步起到巨大的推动作用，将来人类社会会步入量子信息时代。近2 0 年来的量子计算理论研究表明了量子计算在很多方面比经典计算优越得多，特别是在量子系统的模拟和大数因子分解等问题上尤为突出并且提出了诸多量子算法。同时，随着小波理论研究的深入，以及小波分析在信号分析和图缘处理等领域的广泛应用，小波分析在量子计算领域中也越来越受到重视。本文是在量子傅立叶变换算法的基础上，给出量子h a a r 小波变换和d a u b e c h i e s d 小波变换的量子算法，然后通过对多量子算符代数理论和核磁共振( n m r ) 技术的理解和应用，来设计出完整的用n m r 物理技术实现3 量子位h a a r 小波和d a u b e c h i e sd 小波变换量子算法的脉冲序列，并利用量子计算仿真器进行模拟验证所设计的脉冲序列的正确性、合理性及可行性。在整个设计过程中，主要足运用多量子算符代数理论，将量子小波算法相应的么正变换矩阵转化为1 位和2 位量子逻辑门的组合序列，特别是将自旋核之间的耦合作用分解成一系列单量子逻辑门和双量子受控a l q 的有序乘积。第一章：介绍了量子计算的来源及现状，以及本文主要研究的方法、内容和意义。第二章：对量子计算进行整体概述，从量子位、量子逻辑门和并行计算等方面来介绍量子计算。第三章：详细介绍了量子小波算法，并且给出了三量子位h a m 小波和d a u b e c h i e s d ”小波变换的量子线路图和算法复杂度。第四章：介绍了多量子算符代数理论，详细阐述了么正变换的分解，提出了基本量子线路的性质。第五章：介绍了n m r 技术，提出了n m r 进行量子计算的系统和基本理论方法。第六章：提出了l 位量子逻辑门和2 位c n o t 门的n m r 脉冲序列设计，在此基础上，提出了3 量子位h a a r 小波和d a u b e c h i e s d 小波变换算法的n m r 脉冲序列设计，并利用量子计算仿真器对其进行了仿真。第七章：对量子算泫的总结以及展望。关键词：量子计算，量子小波算法，量子逻辑门，核磁共振，多量子算符代数理论，脉冲序列，量子计算仿真器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 t i tc a l ld e a lw i t hi n f o r m a t i o nt e c h n o l o g yu s i n gq u a n t u mm e c h a n i c s w i t ht h eg r o w t ho ft h et h e o r ya n dt h et e c h n o l o g y , m o r ee x p e r t sa n ds c h o l a r si o i ni nt h er e s e a r c ho ft h ef i e l d ；a tt h es a m et i m e ，q u a n t u mc o m p u t i n gg r o w sr a p i d l ya n dp r o m o t e st h ed e v e l o p m e n ta n dt h ep r o g r e s so ft h ec o m p u t e rs c i e n c e i nt h en o t f a rf u t u r e ，o u rs o c i e t yw i l ls t e pi n t oq u a n t u mi n f o r m a t i o nt i m e s f o rt h er e c e n t2 0y e a r s ，q u a n t u mc o m p u t i n gt h e o r yh a ss h o w nt h a ti ti sm u c hs u p e r i o rt oc l a s s i cc o m p u t i n gi nm a n yw a y s e s p e c i a l l y , t h es u p e r i o r i t yi sm o r ee v i d e n ti ns o m es i m u l a t i o no fq u a n t u ms y s t e ma n dl a r g en u m b e rf a c t o r i n gp r o b l e m se t c m e a n t i m e ，m a n yq u a n t u ma l g o r i t h m sa r ep r e s e n t e d a tt h eo t h e rh a n d ，w i t ht h ed e v e l o p m e n to ft h et h e o r yo fw a v e l e tr e s e a r c ha n de x t e n s i v ea p p l i c a t i o no fw a v e l e ta n a l y s i si nt h ef i e l do fs 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 ，w a v e l e ta n a l y s i sh a sb e e nt h o u g h tm o r ea n dm o r ei m p o r t a n ti nt h ef i e l do fq u a n t u mc o m p u t i n g i nt h i sp a p e r , w ei n t r o d u c et 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 sd w a v e l e tt r a n s f o 珊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 i t n w ep r e s e n tt h ed e s i g no f3 - q u b i tp u l s es e q u e n c e so fq u a n t u mw a v e l e tt r a n s f o r me m p l o y i n gt h en m rp h y s i c a lt e c h n o l o g yw i t ht h ea p p r e h e n d i n ga n da p p l y i n gt h 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 as p a c e sa n dt h en m rt e c h n o l o g y f u r t h e r m o r e ，w ev e i l f yw h e t h e ro u rd e s i g ni st r u e ，r e a s o n a b l ea n df e a s i b l eu s i n gq c e i nt h et o t a lc o u r s eo fd e s i g n i n gn m rp u l s es e q u e n c e s ，t h ek e yt op r o b l e m sl i e si nh o wt ot r a n s l a t eu n i t a r yt r a n s f o r m a t i o nc o r r e s p o n d i n gt 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 si n t oas e r i e so f1 - q u b i ta n d2 - q u b i tq u a n t u mg a t e sp r o d u c t s ，i np a r t i c u l a r ,h o wt oe x a c t l yd e c o m p o s et h ei n t e r n u c l e a ri n t e r a c t i o na sas e q u e n c eo fal i m i t e dn u m b e ro fo n e a n dt w o q u b i tg a t e s c h a p t e r1 ：i nt h eb e g i n n i n go ft h ep a p e r , 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 dw ed 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 ei n t r o d u c eq u a n t u mc o m p u t i n g 。f r o ms e v e r a lf a c e t s ，s u c ha sq u b i t s ，q u a n t u ml o g 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 ，w ep r e s e n tq u a n t u mc o m p u t m g c h a p t e r3 ：w ed i s c u s st h 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 s ，a n dw ep r e s e n tt h e i r3 - q u b i tq u a n t u ml o g i c a lc i r c u i ta n dt h ec o m p l e x i t y c h a p t e r4 ：w ei n t r o d u c et h 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 as p a c e s w ed e s c r i b et h ed e c o m p o s i t i o no fu n i t a r yt r a n s f o r m a t i o na n da n a l y s i st h ef e a t u r eo ft h ee l e m e n t a r yq u a n t u mc i r c u i t s c h a p t e r5 ：w ei n t r o d u c et h en m rt e c h n o l o g yi nd e t a i l ，a n db r i n gf o r w a r dt h es y s t e ma n db a s i ct h e o r ym e t h o d so fq u a n t u mc o m p u t i n g c h a p t e r6 ：w ep r e s e n tt h en m rp u l s es e q u e n c ed e s i g no f1 - q u b i tq u a n t u ml o g i c a lg a t e sa n d2 - q u b i tc n o tg a t e t h e nw ep r o v i d et h enm rp u l s es e q u e n c ed e s i g no f3 - q u b i tq 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 sd w a v e l e tt r a n s f o 舯a l g o r i t h m s a tl a s tw es i m u l a t et h e mw i t hq c 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 q u a n t u mw a v e l e ta l g o r i t h m ，q u a n t u ml o g i c a lg a t e ，a b s t r a c tn m r ，m 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 as p a c e s ，p u l s es e q u e n c e ，q c e独创性声明本人声明所呈交的学位论文是苯人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含本人为获得江南大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。签名：一日期：j 瑚1 ，如关于论文使用授权的说明本学位论文作者完全了解江南大学有关保留、使用学位论文的规定：江南大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文，并且本人电子文档的内容和纸质论文的内容相一致。保密的学位论文在解密后也遵守此规定。签名：导师签名：! 圭笪! 垄碰日期：8 名、e l ,第一章绪论第一章绪论1 1 引言在论述量子计算理论之前，我们先回顾一下量子计算的由来。1 9 3 6 年a l a nt u f i n g发表的一篇具有划时代意义的论文宣告了现代计算机科学的形成。t u f i n g 的论文发表不久，世界上第一台电子计算机建成。在1 9 4 7 年晶体管发明之后，计算机硬件能力以惊人的速度发展，后来g o r d o nm o o r e 把这种成长概括为m o o r e 定律，即计算机的能力以固定的速率成长，大约每两年增加一倍。从2 0 世纪6 0 年代开始，m o o r e 定律在几十年问都近似成立。但是，大多数观察家认为这个定律将在2 1 世纪的前2 0 年结束，因为制造计算机的传统方法在解决规模上的困难时开始显得力不从心。当电子器件越做越小时，它的功能开始受到量子效应的干扰。m o o r e 定律最终失败的一个可能解决办法是采用不同的计算模式，量子计算理论就是这类模式的一种，量子计算基于量子力学而非经典物理学的思想进行计算。由此量子计算的概念诞生了。量子计算和量子计算机概念起源于著名的物理学家f e y n m a n i m i li ，他在1 9 8 2 年研究用经典计算机模拟量子力学系统时提出的。1 9 8 2 年，f e y n m a n 论证了用经典计算机模拟量子力学系统时，随输入( 粒子数、自由度) 的增大其计算资源( 时间、空间) 消耗会指数增加。例如量子位态矢的h i l b e r t 空间，在r m 2 0 0 时是2 2 0 0 维矢量空间，要描述这个矢量空间中的一个典型态，将需要在经典计算机中记录2 2 0 0 一1 个复数，这是任何经典计算机都不可能做到的。这一观察引起了f e y n m a n 推测，按照量子力学规律工作的计算机( 量子计算机) 可能可以避免这一困难，这就是最早的量子计算的思想。1 9 8 2 年，b e n i o f f 深入地研究了量子计算机是否比经典计算机更有效地问题，他定义了量子t u f i n g 机，描述了量子计算机地一般模型1 3 j ，研究了它的性质，说明了量子计算机的潜在能力。d e u t s c h 第一个系统地表述了现在人们所理解的量子计算机模型1 4 j 。1 9 9 4 年，p e t e rs h o r 发现了第一个具体的量子算法1 5 】，这个算法在设想的量子计算机上可以输入的多项式时间分解大数质因子，而求解人数质因子对经典计算机是个难题。这个问题对经典计算机是如此困难，以至于现在广泛使用的公开密码系统r s a 就是以这个问题的难解为基础的。1 9 9 6 年，g r o v e r 又发现了未加整理数据库数量级加速查询算法【6 1 1 。7 1 ，而且用这种加速的查询算法有可能解决经典计算机上所谓的n p 难题，因而引起了人们的重视。早期的量子计算机实际上是用量子力学语言描述的经典计算机，并没有用到量子力学的本质特性，如量子态的叠加性和相干性。与经典计算机不同，量子计算机可以做任意的么正变换，在得到输出态之后，进行测量得出计算结果。凶此，量子计算对经典计算做了极大的扩充，在数学形式上，经典计算可看作是一类特殊的量子计算。量子计算机对每一个叠加分量进行变换，所有这些变换同时完成，并按一定的概率幅叠加起来，给出结果。这种计算称作量子并行计算。除了进行并行计算以外，量子计算机的另一个重要用途是模拟量子系统，这项工作是经典计算机无法胜任的。江南大学硕士学位论文近年来，国外已有大量的研究人员开始了对量子计算机的研究工作，同时产生了门新兴科学量子信息学。量子信息学是量子力学与信息学相结合的产物，是量子力学建立起来之后的第二次研究与应用。量子信息学包括：量子计算机、量子密码术、量子通信、量子测量和量子神经计算等等。最近几年，有关量子计算的学术论文和报告已发表很多，对量子仿真器的研究也不少。国外有些学者在进行这方面的研究。网上还出现了关于量子计算机仿真器的网站悼j 。这些仿真器都为实现一定的目的而设计。其中，功能较为全面的有维也纳工业大学毕业的研究生b e r n h a r do m e r 的硕士、博士学位论文就是在做这方面的研究【9 】1 1 0 】。但是其实是用结构来代替对象，而且代码也比较初步，并未体现量子并行的概念。还有荷兰的学者k r i s t e lm i c h i e l s e n 和h a n sd er a e d t 等开发的量子仿真器作为一个学习量子计算机和量子算法的交互教育软件进行发布，采用了图形交互界面，而且能够在w i n d o w s 平台下运行。是一个模拟核磁共振实验的量子仿真器】【i2 1 ，这个仿真器允许研究人员自由设计脉冲序列来实现量子算法，是一个比较完善的量子计算仿真器，本文对量子算法的仿真实现就是在这个量子仿真器上实现的。1 2 本课题的研究意义以及研究方法量子计算机( q u a n t u mc o m p u t e r ，q c ) 是一类遵循量子力学规律进行高速数学和逻辑运算、存储及处理量子信息的物理装置。当某个装置处理和计算的是量子信息，运行的是量子算法时，它就是量子计算。无论是量子并行计算还是量子模拟计算，本质上都是利用了量子相干性。但是，在实际系统中量子相干性很难保持。在量子计算机中，量子位不是一个孤立的系统，它会与外部环境发生相互作用，导致量子相干性的衰减，即消相干。因此，要使量子计算成为现实，一个核心问题就是克服消相干。至今为止，世界上还没有真正意义上的量子计算机。但是，世界各地的许多实验室正在以巨大的热情来追寻着这个梦想。如何实现量子计算，方案并不少。只是问题在实验上实现对微观量子态的操纵的确太困难了。目前已经提出的方案主要利用了原子和光腔相互作用、离子阱束缚离子、电子或核自旋共振、量子点操纵、超导量子干涉等。研究量子计算机的目的并不是要用它来代替经典的计算机。量子计算机使计算机的概念焕然一新，它也不同于其他计算机如光计算机核生物计算机等等，量子计算机要解决的问题也不是局限于一些经典计算机无法解决的问题。在传统的信息论中，通用计算机能用几个等价的模型表示。对应于不同的学科，说法也不同。例如，从数学角度看，一个通用的计算机是一个能够计算局部递归功能的机器。计算机科学家会用“图灵机”模型。电子工程师可能更喜欢用逻辑线路来代替。而程序员可能更喜欢用通用的程序语言。对于量子计算仿真程序语言，首先需要建立量子计算语言和传统计算之间的对应关系，如表卜1 所示。合理的定义有利于模型和算法的设计与实明。第一章绪论表卜1量子计算语言和传统计算之间的对应关系t a b 1 1c o m p a r is o nb e t w e e nt h et r a d i t i o nm o d u l ea n dq u a n t u mm o d u i e模型经典计算量子计算数学角度局部递归功能么正操作机理图灵机量子图灵机线路逻辑电路量子门算法通用程序语言量子计算语言在一台传统的经典计算机上模拟量子计算机是个难题。它所需要的资源随着被模拟的量子内存数量增加呈指数增长，以至于连模拟一台只有几十个量子位的量子计算机也远远超过了现在能够制造的任何一台计算机的能力范围。量子计算仿真器只是模拟非常小的量子计算机。但是，它的效率已经足够展示量子计算机算法背后的一些概念。因此，在量子计算机进入实用之前，在经典计算机上用量子计算仿真器验证量子算法就显的特别重要了。因此，用经典计算机实现量子计算的仿真，具有重要的科研价值。1 3 本课题研究的主要内容在理论计算机科学的研究中，许多问题的解答都可归纳为只需要回答“是”或“非”的判定问题。一个判定问题如果能用多项式时间算法求解，那么它被称为p 类问题。人们已经发现有一大类问题至今还没有找到它的多项式时间求解，但并未证明它没有多项式时间算法，此类问题称为n p 类问题。量子计算机是服从量子力学规律的计算机，在量子计算机中求n p 难题，有可能得到多项式算法，其中最具代表性的成果是s h o r 提出的大数质因子分解算法l5 1 。在量子计算机中，它能以多项式时间内分解得到一个大数的质因子。还有一些量子算法不是把指数算法变成多项式算法，而只是把一个需要n 步的计算缩小为步，例如g r o v e r 未整理数据搜索的量子算法。本文讨论利用量子计算机的独特性质来求解传统的n p 难题，如量子傅立叶变换和量子小波变换。核磁共振( n m r ) 实验技术来实现量子计算1 1 3 】1 1 4 】，是当前各种验证量子算法最为有效的方法之一，但这个方法首先必须把量子算法编译成在现代超导核磁共振谱仪上能够执行的n m r 脉冲序列，也就是n m r 量子计算程序。在n m r 技术中通常只要施加合适的射频脉冲，就可以达到使核自旋翻转以实现某种逻辑功能。本文讨论如何设计n m r脉冲序列来实现基本的量子逻辑门，如量子受控非门等等。本文还应用多量子算符代数理论【1 5 1 来设计多量子位的量子傅立叶、量子h a a r 和量子d a u b e c h i e s d 小波变换算法的n m r 实验脉冲序列，并用量子计算仿真器来验证多量子位的量子傅立叶、量子h a a r 小波和量子d a u b e c h i e s d m 小波算法的量子计算程序。1 4 本章小结本章主要讨论了量子计算以及仿真实现的研究现状及其发展，讨论了量子计算这个新兴研究领域的相关问题，提出了量子计算及其仿真的实际意义和理论意义，最后简单的介绍了一下本课题的研究的主要内容。江南大学硕十学位论文第二章量子计算的理论概述2 1 引言量子理论的核心在于揭示原子级、亚原子级微观粒子( 如电子、光子等) 运动规律，不过量子理论中的一些基本原理和概念具有非直观( c o u n t e r i n t u i t i v e ) 的特性，与经典物理理论存在着很大的区别。h e i s e n b e r g 不确定性原理认为，一个粒子的位置和动量不可能同时被测量，这是因为在测量过程中外界必定对该粒子注入能量，比如说由测量激光发射出的光子打在粒子上，光子的能量会被粒子吸收，并将其送入其他的运行轨道。这样，倘若测量时能够确定该粒子的位置，那么此时粒子的动量己被测量环境所改变。另外，在量子力学中有一个著名的t h o m a sy o n g 双缝实验1 1 6 】，由光子枪发射出光子，通过屏幕上的两个窄缝打在接收屏上，如果控制两个窄缝的开、关状况，就能得到一个奇特的现象。当只有一个缝开启时，光子会穿过它在接收屏上得到一个分离的概率分布模式，靠近窄缝一侧概率大，但是当两个缝同时打开时，接收屏上所得到的并不是两个模式的简单叠加，而是更为复杂的模式，这个现象根本无法用经典物理理论来解释。在量子力学中，经常使用h i l b e r t 空间中的波函数来描述微观粒子的运动状态，波函数的形式1 1 7 j 为：i甲( ，) = ae x p ( - 三一日)(1)_py2仃其中，而为普朗克常量，e 为粒子能量，p 为粒子动量。显然，如此的波动函数不再是经典意义上的波函数，它体现了微观粒子的波粒二象性( w a v e p a r t i c l ed u a l i t y ) 。量子计算与传统物理意义上的计算有着质的不同，它的特点主要体现在量子态的叠加( 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 ) 1 1 8 j 上，许多量子计算上的优势如量子并行( 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 )位( b i t ) 是经典计算和经典信息中的概念，它是用二进制中的1 个位来表示，0 或者1 状态。在数字计算机中，一个电容器极板之间的电压可表示信息位，有电荷代表1 ，无电荷代表0 。而量子计算是建立在类似的概念一一量子位( q u a n t u mb i t 或q u b i t ) 1 1 9 l基础上的。和经典位一样，量子位也有一个状态，量子位的两个可能状态分别为10 和1 ，这分别对应了经典位的状态0 和状态1 。记号“ 称为d i r a c 记号。量子计算机是用二态的量子力学系统来描述量子位信息的，比如，光子的两个偏振方向1 个) 和i 寸) ，。磁场中电子自旋或者核自旋向上和向下的两个方向，原子中电子的两个能级态等。量子计算机进行量子计算的过程就是这螳量予力学系统的量子念的演化过程。量予位和经典位的区别在于，量子位的状态可以落在0 和：1 之问，量了位可以是状念的线性组合，一般称为替加念，例如：第二苹量了汁算的理论概述t p 一a0 + l1 ( 2 2 )其中口和是复数。也就是说，量子位的状态是二维复向量空间中的向量。特殊的jo 和i1 状态称为计算基态( c o m p u t a t i o n a lb a s i ss t a t e ) ，是构成这个向量空问的一组正交基。在经典计算机中，我们可以通过检查一个位，来确定它是处于0 状态还是1 状态，如计算机每次从内存中存取内容时，做的就是这件事情。但是对于量子位，我们不能检查它的量子位来确定它的量子状态，也就是口和的值。相反，量子力学告诉我们，只能得到关于量子状态的有限信息。也就是，在测量量子位的时候，我们得到1o 的概率是l 口1 2 ，得到11 的概率是i 1 2 ，而i 口1 2 + i 1 2 = 1 ( 概率总和为1 ) 。从几何意义上看，是要求量子位的状态归一化到长度1 。量子位的不可观测状态和我们能够进行观测的差别在量子计算的研究中处于中心位置。在我们建立的现实世界中的大多数抽象模型当中，抽象和模型之间存在着直接的对应关系，没有这种直接的对应关系，使得从直观上解释量子系统的行为变得非常困难。不过好在存在一种间接关系，因为量子位的状态可以被处理和变换，按照状态的不同属性，产生可区分的测量结果，因此，这些量子态具有真实的、实验可验证的效应，这些效应对于量子计算的功能来说是非常重要的。量子位的叠加态的可能性在我们的现实生活中是无法想象的，因为它与我们身边的常识相矛盾，但是量子位的确是真实的，它们的存在和行为已经被大量实验所证实。在原子模型中，电子可能处在基态，也可能处在激发态，分别用io t u ；1 来表示。用光照射该原子，如果能量合适，并且时间足够长，可以使电子在io 和l1 的状态之间移动。但更有趣的是，缩短光照时间，开始处在10 的电子可以移到从1o 到il 的中途，即进入i + 的状态。当对处于叠加态的量子位进行测量和观察时，叠加态将会受到干扰，并产生变化，这种变化被称为坍缩( c o l l a p s i n g ) ，这个过程也叫消相干。对于式( 2 2 ) 的测量，叠加态将坍缩为基本态，将以一定的概率得到一个确定的量。令x o ，1 ) ，在二维h i l b e r t 空间，i x 是具有两个分量的向量，令l o ：，1 1 ：( 2 3 )l o ll 的共轭，它是具有两个分量的行向量，即 0i = ( 1 ，0 ) ， 1i - ( 0 1 ) 。令y o ，1 ) ， 则称为内积，它是一个标量。 = = 1 ， = = 0 。ix ) 2i6 云j ( 订io + 61 ) = 口lo 2 4 上式说明：10 上是将其中属于10 的成分取出，也就是说10 对l0 投影，相当于在l0 方向上测量l 缈 。同样，i1 ) = b1 ，i1 对i1 投影，即在l1 方向测量i 缈 。江南人学硕士学位论文2 2 1 多量子位假设有两个量子位，对两个经典位而言，共有四种可能状态：0 0 ，0 1 ，1 0 和1 1 。相应地，一个双量子位的四个基态，记做10 0 ，! o l ，i1 0 ，i1 1 。一对量子位也可以处于这四个基态的叠加，因而双量子位的量子状态包含相应基态的复系数，有时称为幅度( 概率幅a m p l ir u d e ) 。这样描述双量子比特的状态向量为：i 妒 - a 0 00 0 + 口0 10 1 + 口】o1 0 + 口l li11 ( 2 5 )类似于单量子位的情形，测量结果为x ( = 0 0 ，0 1 ，1 0 或1 1 ) 出现的概率是i 口。1 2 ，测量后，量子位处于ix 状态。概率和为l 的归一化条件可以表示为：州o 1 l ：i 哎1 2 = 1( 2 6 )其中 0 ，1 ) 2 意味着长度为2 ，每个字母从0 和1 中任取的符号串的集合。对于一个双量子位系统，可以只测量其中一个量子位，譬如第一个。单独测量第一个量子位，得到0 的概率为i 1 2 + i ，1 2 ，而测量后的状态为：眵k 丝兰业( 2 7 )l 1 2 + l l1 2测量后的状态因子| f 2 + i 。1 2 重新归一化后，仍然满足归一化条件，正像我们对一个标准的量子位期待的那样。更一般地，可以考虑刀量子位系统，这个系统的基态形如l 五叠一 ，并且量子状态由2 ”个幅度所确定。门= 5 0 0 时，这个数就超过了整个宇宙原子的估算总数。在任何传统计算机上存储所有这些复数都是不可想象的。h i l b e r t 空间的确是个巨大的空间，这样巨大的计算潜力使得量子计算变得更有吸引力。2 3 量子寄存器刀个量子位的有序集合称为刀位量子寄存器1 2 0 1 f 2 i 】，它的系统态是胛个量子位态的张量积，用符号。表示，它的表达式如下：爿= l a ：1 1 ，b = ( 乏象： ，贝u ：彳 b =。岛。口l 。a l o 岛o6 06 1q o b o0 1 06 la ，臼l6 0 0b l oa ob o oa 。6 l oa l6 06 16 06 l因此，对于刀位量子寄存器，其叠加念位：l = 1 一l 纯- 2 一 = i 纯一2 0i 甄y 是2 ”维h i1b e r t 空问的单位向量，它有2 ”个相互正交的基本态。2 ”一l2 ”一il = qx ，式中，iq1 2 = 16( 2 8 )( 2 9 )( 2 1 0 )第二章量了计算的理论概述因此，在量子计算机中，处于叠加态的刀位量子寄存器中的数是从o 到2 ”一1 的所有数，它们各以一定的概率同时存在。在常规计算机中，1 个 位的寄存器只能保存1 个玎位二进制数：而在量子计算机中，1 个 位的量子寄存器可以保存2 ”个刀位二进制数。量子寄存器位数的线性增长使存储空间指数增长，这是量子计算机的一个基本特点。量子寄存器中态的测量可以通过测量寄存器中的各个量子位的态来完成，每个量子位的态的测量都是对各自基本态进行的。在测量量子寄存器的态时，其叠加态坍缩。门位量子寄存器虽然可以存储2 ”个，位数，但在测量时，只i i i ! i 量某一个以位数。当多个量子位的态如果不能表示位张量积，而是表达为系统中态的某种纠缠形式。例如：i 缈 爿= 去( i0 0 + l1 l ) 或i 缈 b = 去( 1o l + il o ) 为纠缠态，而i 缈 c = 亡( i0 0 - i - i0 1 ) 则不为纠缠态，因为i 缈 c 可写成如下的张量积：v z老( 10 0 + i0 1 ) - | o 老“0 1 + | 1 0 ) 。量子位的纠缠态对量子计算十分重要 当多个量子位处于纠缠态时，对部分量子位的态的测量将影响其他量子位的态的测量。例如测量i 缈 _ 时，测量一个量子位的念，将使另一个量子位的态与之相同；测量i 缈 口时，测量一个量子位的态将使另一个量子位的态与之相反，但测量i 妒 r 时，对右边那位的态不管如何测量，左边那位的态总是为lo 。这就是量子理论中最具非直观特性的一个现象一一量子纠缠。2 4 量子逻辑门2 4 1 量子非门经典计算机线路由连线及逻辑门构成。连线用于在线路问传送信息，而逻辑门负责处理信息，把信息从一种形式转换为另一种。例如，考虑一个经典位逻辑门，唯一的不平凡成员是j 1 1 2 ，非门的操作由真值表定义：其中0j1 ，l 一0 ，即将0 ，1 状态交换。类似的可以定义量子非门。如果某个过程把状态lo 和 1 交换，但是在io 和i1 状态上定义门的作用无法确定io 和f1 之问的叠加态会发生什么。实际上，量子非门的作用是线性的，即把状态口l0 + i1 变到l0 和i1 状态角色互换的新状态：口il + 卢l0 。事实上，这一线性行为是量子力学的一般属性，也非常符合经验。非线性行为会导致许多佯谬，如时间旅行、超光速通信、违反热力学第二定律等2 。基于线性的性质，量子非门可以用矩阵形式表示。定义一个x 矩阵来表示非门如下：x ：f 1( 2 11 )l10 若把量子态口10 + i1 写成向量形式：一项对应；1 的幅度，那么量子非门就是：7其中上面一项对应o 的幅度，而下面江南大学硕士学位论文x = ( 2 1 2 )因此，单量子位的量子门可以由2 2 矩阵给出。回顾归一化条件，要求量子状态口j0 + l1 满足l 口1 2 + l 1 2 = 1 ，这对量子门作用后得到状态眵 _ 口10 + 。i1 也是适用的。表示单量子位门的相应矩阵u 要满足的条件是么正性( u n i t a r y ) ，即u u = ，其中u + 是u 的共轭转置，j 是2 2 的单位矩阵。对于非门来说，可以验证：x x = ，。么正性质是对量子门的唯一限制，每个么正矩阵都定义了一个有效的量子门。和只有一种不平凡单位门一一非门一一的经典情形不同，有很多不平凡单位量子门。2 4 2w - t t 门对一个量子位进行的一种比较常见的变换是w a l s h - - h a d a m a r d 变换，简称w - h 变换。即：= 拭二。 w h 作用与l 。 和l1 分别为：wo 一万1 ( i 。 + i1 ) ，i1 万1 ( 1 。 一l1 ) 。矿i 。 相当于将 0 顺时针方向旋转4 5 。，肜i1 相当丁将i1 逆时针旋转1 3 5 。因为+ w = j ，所以形变换是么正变换。因为w = + ，所以形变换是厄米变换，变换是可测量的。令x - - 4 矗一l 矗掣而 ，则( 圆o i v ) lx = wi 矗一l 0 i 一2 0 o ix o 。若n = 2 ，x i = x o = 10 ，则( ) i0 0 = 去( i0 0 + l0 1 + ilo + f1l ) 。可以看出，对lo o 的每一位分别进行w - h 变换可产生2 个量子位的2 2 个基本态叠加，即o o ，0 1 ，1 0 和1 l 同时存在，每个存在的概率均为1 4 。同样对于刀个量子位，( o ) i0 0 0 = - 7 导ix 。2 ”蒿所以，当量子寄存器中的 个原始数位全为0 时，对每一位分别进行w - h 变换可产生2 ”个基本态的叠加，即产生从0 到2 ”一1 的所有二进制数，它们同时存在，存在概率均为1 2 玎。2 4 3 一位旋转门对一个量二子位可以进行旋转变换尼即：尺：f ，1o ( 2 1 4 )肚i o j他1 4 从上式可以看出月10 寸j0 ，rl 寸e 91 。因为j r + r = ，所以r 变换是么正变换。由于可在0 与2 7 r 之间连续变化，w h 门与旋转门结合起来，可以实现一个量子位的任意么f 变换，旋转变换只是使i 缈 转动一个角度，没有逻辑意义，但在量子计算中会起到重要作用。第二章量r 计算的理论概述2 4 4 量子受控非门受控非门是一个2 量子位的系统。这个门有两个输入量子位，分别是控制量子位和目标量子位。该门的作用可以表述如下：如果控制量子位被置为o ，则目标量子位将保持不变。如果控制量子位被置为1 ，目标量子位将翻转。用方程形式可表示为：0 0 叫0 0 ，i0 1 一10 1 ，i1 0 叫1 1 ，l1 1 专i10 ( 2 1 5 )另二种描述受控t e f - i 的方法是将其视为经典异或门的推广，因为该门的作用可以总结为：lx ，y - - - lx ，x ( 9y ，其中0 为模2 加法，而这正是异或运算所做的。也就是说，控制量子位和目标量子位做异或运算，并将结果保存在目标量子位中。受控非门也能用矩阵来表示，即：u c n210010 00 o0 00 00110( 2 1 6 )容易验证。的第- - n 表示对 0 0 的变换，第二、第三和第四列则分别表示对l0 1 ，l1 0 和111 的变换。因为= ，所以u c n ；是z , - t e 矩阵，也即受控非f 是- - , t 变换。除了受控非门之外还有许多其他重要的量子门，不过由于任意的多量子位门都可由受控t e f - 和单量子位门组合而成2 ，因此，从某种意义上说，受控非门和单量子位门是所有其他门的原型。2 5 量子并行性量子并行性是许多量子算法的一个基本特征1 2 1 1 。简言之，量子并行性使量子计算机可以同时计算函数厂( x ) 在许多不同的x 处的值。设f ( x ) ： o ，1 ) 专 o ，1 ) 是具有一位定义域和值域的函数。在量子计算机上，计算该函数的一个简单办法是：考虑初态为i 五y 的双量子位的量子计算机。通过适当的逻辑门序列可以把这个状态变换为i x ，y ( g f ( x ) ，这里。表示模2 加法，第一个寄存器称为数据寄存器，第二个称为目标寄存器，映射ix ，y 一ix ，y 0f ( x ) 叫做u ，容易证明它是么正的。如果y = 0 ，则第二个量子位的最终状态就是厂( x ) 的值。数据寄存器经过w h 变换，再把u ，加到计算基以外的个输入。这样数据寄存器中是叠加态( io + l1 ) 4 z ，这可由w h 门作用到i0 上得到。于是应用u ，得到状态：9 ：! q 2 三兰! ! ：! 1 2 三( 2 17 )2这是一个值得注意的状态，不同的项同时包含f ( 0 ) 和f ( 1 ) ，看起来似乎同时对x 的两个值计算了f ( x ) 。与经典的并行不同，那单多重f ( x ) 电路同时运行，而这哩，利用了量子计算机处于不同状态的叠加念的能力，单个f ( x ) 线路用来同时计算多个x 的函数值。利用w h 变换，这个过程很容易推广到任意数目的量子位上的两数。该变换就是刀9江南人学硕十学位论文个w - h 门同时作用到刀个量子位上。例如n = 2 ，初态全为l0 的情况，输出则是：( 警) ( 警) = 坠业半( 2 1 8 )我们用。2 表示两个w - h 门的并行作用。更一般的，? 重量子位上的w - h 变换从全0 出发，得到：专ix( 2 1 9 )其中求和是对j f 的所有可能取值，并用勘表示这个作用。可见，w h 变换产生了对所有计算基态的平衡叠加( e q u a ls u p e r p o s i t i o n ) ，而且，它的效率非常高，仅用疗个门就产生了2 ”个状态的叠加。可以采用下述方法进行刀位输入x 和单位输出f ( x ) 函数的量子并行计算。制备n + l量子位的状态f0 锄l0 ，对前聍位应用w - h 变换，并连接实现u ，的量子线路。这就产生状态：古沙 m ，( 2 2 0 )在某种意义上，表面上似乎只进行了一次厂计算，量子并行性却使厂的所有可能值同时计算了出来。然而，这种并行性并不是直接就有用。对单量子位，测量状态得到l0 ，f ( o ) 或i1 ，厂( 1 ) 中的一个。一般而言，测量状态ix ，厂( x ) 也类似的只给出对某个单个x 的jf ( x ) 值。经典计算机很容易可以做到这一点。为了真正有用，量子计算要求的不仅仅是量子并行性，它要求比从叠加态lx ，厂( x ) 中得到一个f ( x ) 值更高的信息抽取能力，j而这就是量子算法所要完成的任务。2 6 量子算法量子计算机是遵循量子力学规律的计算机，它可以支持新型的量子算法。任何量子算法的核心都是研究如何处理量子并行计算，使得以较高的概率测量我们所期望的计算结果。量子算法类似于概率算法，系统的所有可能的量子念由一个叠加的量子态表示，其中的每一个量子基态有不同的概率幅，计算对应于量子态的迁移。在数学上使用相应的么正矩阵来表示。完成量子并行计算后，需要对量子系统进行测量以得到计算结果。但是一旦进行测量之后，系统的量子态将根据各个量子基态的概率幅大小随机塌陷为其中一个量子基态。为了在量子计算中软得正确的结果，就要通过适当的量子变换提高期望输出量予基态被测量得到的概率。量子计算机可以在以下三方面超出经典计算机。1 指数加速，如s h o r 的人数质因子分解的量子算法可以实现指数加速。2 非指数加速，如g r o v e r 的搜索最予算法可以实现的加速。“相对”指数加速，如求解函数周期的s i m o n 问题的“量子黑盒”可获得指数加速。1 0第二章量子计算的理论概述2 7 算法复杂性理论算法复杂性是衡量算法难易程度的尺度【2 2 1 。一个算法是难的，意味着用这种算法去解具体的问题将伴随着大量的计算资源消耗；反过来，如果不需要消耗太多的计算资源就可求出问题的解答，这样的算法就可认为是容易的。在算法复杂性理论中，有容易的“多项式时间算法”与难的“指数时间算法”之分。当我们用力表示需要输入的信息量大小时，解这个问题的算