量子计算及其应用

第27卷第1期广西大学学报(自然科学版)Journal of guangxi UniversitatEd)M:,202文章编号:1001-7445(2002)01-0083-04量子计算及其应用钟诚2,陈国良(1.广西大学计算机与信息工程学院,广西南宁530004;2.中国科技大学计箅机系,国家高性能计算中安徽合肥230027)摘要:讨论量子计算杋模型及其物理实现方案、量子计算过程、量子计算模型和量子并行算法,分析量子计算的指数级存储容量和指数加速特征,并简述量子计算和量子信息技术在保密通信、密码系统、数据库搜索等重要领域的应用关键词:量子力学;量子计算机;量子信息;量子并行算法中图分类号:TP301文献标识码:A电子、计算机与信息技术发展一日千里.电子元器件日益微型化的结果是使得一个微电子元件所包含的原子数目可以达到一个或几个,一个逻辑操作的耗能将达到不可逆逻辑操作的热力学极限KT量级.这使得经典计算机芯片內集成电子元件的数量受到很大的限制,CPU速度的增长开始减缓.此种趋势促使人们考虑研究遵循量子力学原理的量子计算机和量子计算技术.20世纪后期以来科学家们在量子计算机的研制、量子计算和量子通信技术等方面取得了令人鼓舞的成就.专家门预测,21世纪将是研究、开发与应用“量子计算机”、“量子计算”和“量子通信”技术的新时代,相信在可预见的不久的将来量子计算机将从实验室走向市场,量子信息技术将在科学研究、军事和国民经济各领域得到广泛应用.本文从计算机科学的角度简述量子计算的有关问题以及量子信息技术的应用,以期引起更多的读者对量子计算和量子通信技术的关注1量子计算机模型及其物理实现方案前提岀的量子计算机模型主要有量子 Turing机模型、量子门组线路模型和量子细胞自动机模型等.量子 Turing机模型可以用多项式大小的量子门组网络,或者用量子门组网络多项式大小的时间来模拟.实现量子计算杋的物理方案有离子阱( (lon Trap)、腔量子电动力学(腔QED)、核磁共振(NRM)和量子点( Quantum Dot)等.离子阱方案的主要优点是阱中的超冷离子处于一个几乎与外界隔绝的空间中,由环境引起的消相干效应非常小,因此使得量子计算的并行度较高;其主要缺点是时钟速度太慢用数目极大的激光束脉冲操作各个离子执行逻辑运算时,运算速度难以提高.腔量子电动力学方案的主要优点是两个量子位之间相互作用的时间尺度大大小于离子阱方案,因此其可以在单位时间内完成更多的操作步骤.利用核磁共振技术实现量子计算机较为成熟.而量子点方案的优点则是量子位可以是嵌套在固体材料中的固态量子器件,这与经典计算机的大规模集成电路的设计相似1-4.20世纪90年代以前,研究量子计算机似乎只是物理学家感兴趣的事情.但是,自从1994年AT8T公司的科学家 PeterShor发表震惊世界的大整数素因子分解量子算法(此中国煤化工数学家大会最高奖)以来,立刻引起了越来越多的计算机科学家对量子计算的CNMHG量子信息技术的研究热潮截止到2000年,美国已成功地建立4个量子位的离子阱量子计算机,同时美国和德国的科学家利收稿日期:2001-10-25;修订日期:2002-01-10基金项目:国家973计划(G1998030403)作者简介:钟诚(1964-),男,广西桂平人,广西大学教授,中国科技大学博士生84广西大学学报(自然科学版)第27卷用核磁共振技术成功地建立5个量子位的量子计算系统,在中国则利用核磁共振技术成功地建立3个量子位的量子计算机;据最新报道,2001年日本利用核磁共振技术已研制出16个量子位的实验性量子计算机原型.目前,各国正向建立更多量子位的、实用的量子计算机的目标努力,并不断取得新进展2量子计算过程众所周知经典的冯·诺依曼数字电子计算机是遵照图灵( Turing)计算模型设计和制造的.这是因为从经典意义上而言,“计算”属于数学范畴,“计算”的理论与方法可以脱离具体的物理过程,依靠纯粹的思辨和抽象的逻辑推理构造岀来.但是,“计算”本质上可以看作是计算仪器的物理系统所执行的一个物理过程.根据采用的计算设备的不同,这一物理过程也不尽不相同,它可以是人脑所完成的“计算”、算盘操作的“计算”和电子计算机控制的“计算”,等等.不管采用何种计算设备,“计算”的一般过程是:首先输入原始数据,从物理的角度看这可以解释为在计算系统中制备岀一个初始物理态;然后执行计算,这过程实际是按照算法规定的步骤,将给定的初始物理态演化成对应输岀物理态的过程;最后输岀计箅结果,这可以看作对演化的物理末态进行测量得到所需信息的过程.量子计算机是一种遵循量子力学原理完成计算仼务的系统,它采用量子态编码信息,其存储量子信息的基本单元是称为量子位( qubit的量子双态系统(或者说是一个二维 Hilbert空间).可以将量子计算机看成是由一系列量子门构成的电路.假设该电路由n个逻辑门构成并作用在m个量子位上.一个量子位是一个微观粒子构成的两基态{0,1}系统.一个量子位除了可以处于0态和1态之外,还可以处于它们的迭加态.量子位的迭加态φ>可表示如下:φ>=p。10>十p11>.其中υ和p均为复数,表示基态0和1的振幅(概率幅)p|和|p1|2分别表示系统处于基态0和的概率,且满足归化,即满足>||2=1.当对量子系统的迭加态|ψ>进行测量时,量子寄存器的状态以|p。|2的概率处于|0>态,以|p1|2的概率处于>态与经典计算机的数据表示相似,量子计算机的数据用量子寄存器中所有量子位的共同量子状态来表示,一般地,一个n位经典计算机的寄存器仅处于惟一的状态(0或1)中,而一个n位的量子寄存器却可以处于2"个基态的相干迭加态|ψ>中.迭加态|y>和基态;>的关系可表示如下:y>=p,②其中为复数,表示振幅(概率幅),p|2给出迭加态|ψ>在受到与量子计算系统相纠缠的仪器测量发生散落时坍缩到基态|,>的概率且满足>P12=1.量子寄存器用于存储量子位信息量子寄存器的状态描述量子计算机的状态.一个n个量子位的量子寄存器能够同时存储2″个状态信息(即2个数据),因此,量子计算机具有经典计算机无可比拟的、指数级的海量存储能力.量子门对量子寄存器进行操作,实现量子态的转换(即实现对量子寄存器中的数据进行计算、处理)量子计算的过程是:首先制备岀处于迭加、等振幅(等概率)的量子初态,然后按照算法需要对迭加态不断进行演化(量子门操作,幺正变换),最后对最终的迭加态进行测量使其以接近于1的概率坍缩到所希望的态,从而得到所需的计算结果.对于量子计算系统,因为可以制备出由各个互不相同的态迭加所形成的初始态,量子计算机具有对这些初始态同时进行演化的能力,也即量子计算机可以沿着各条互不相同的路径同时演化初始迭加态,直至荻得对应的输出的迭加态.对于一个n个量子位的量子寄存器,由于其同时存储了2状态信息(2个数据),所以对量子寄存器进行一次量子门操作即可实现对2个状态信息(2个数据)进行计算、处理这说眀量子计算机具有天然的并行性极大地加快对海量信息处理的速度,使得大规模复杂问题能够在有限的指定的时间内完成.量子计算系统中国煤化工处理”特性使得它具有比经典计算机更快速、更强大的信息处理能力,特别适CNMHG(参见: Kevin markObenland Using Simulation to Assess the Feasibility ot Quantum Computing. Ph.D.DissertationUniversity of Southern California, 1998.8.)3量子计算模型和量子并行算法量子算法具有量子态相干迭加、量子并行、量子态纠缠和测量坍缩等特性.由于量子计算的过程是1期钟诚等:量子计算及其应用量子系统初态φ>经过与量子计算机控制系统的相互作用,随时间演化成所需末态丨φ灬>的过程,所以假设量子计算机控制系统由量子门U,(i=1,2,…,m)和量子门后的测量算符M,表述,演化计算得到的中间结果用态矢序列{φ'ψφ'ψ……φ-ψn-1}表述,那么一个简化的量子计算模型可描述如下MnUm……M2U2M1U1(|y>)=MnUm……M2U2M1(|y1>)=MnCm……MU2(|y1>)对于上述量子计算模型中的每一次变换U-1(|ψ-1>)→|ψ>,在设计量子算法时可以用幺正变换矩阵和态矢量相乘来实现.设有某个量子算法∫,U′表示一个量子门完成的线性变换,当将U/作用于某个迭加态时,根据量子算法的并行性,它会同时作用到该迭加态的所有基态上,并将所有结果进行迭加以产生一个新的迭加态.因此,为了计算函数∫(x),仅需应用一次U’操作即可并行计算出x取2个不同值的f(x)的结果其中,x>10>表示系统由两个量子寄存器组成,第1个量子寄存器|x>表示基态(存储自变量α的值),第2个量子寄存器⑩>用于存储计算∫(x)的结果,其初始值为O.为了获取计算结果,需要对量子寄存器进行测量.所谓测量是将系统的状态投影到某个基态上,提取岀相应的概率幅.当测量第1个量子寄存器时,会导致系统状态从迭加态坍缩到某个确定的基态|x>上,由于第1个量子寄存器和第2个量子寄存器是纠缠在一起的,所以第2个量子寄存器会关联坍缩到某个确定的结果态‖f(x)>上,为此,在设计量子算法时需要确保最后得到的结果态的概率最大.例如,若希望得到x=101的结果∫(101),那么量子算法的控制应使得基态101>对应的概率幅最大,这样测量时第2个量子寄存器即坍缩到态|f(101)>上4量子计算技术的应用1)量子信息保密通信.量子信息是用量子态编码的信息,量子态具有事先不可确定的特性,即量子态是未知态,量子信息满足“量子态不可完全克隆(No- Cloning)定理”,这样在量子信道上传输量子信息过程中,即使窃听者截获了用量子态表示的密钥,他也不可能完全恢复出原本的密钥信息,从而他不能破译秘密信息,这是因为恢复密钥是破译密码系统的关键θ.此外,A.K.Pati等人利用量子力学的线性性证明仼意未知量子态拷贝的完全删除也是不可能的,即密码攻击者不能破坏量子信息传输的完整性.因此,在量子信道上可以实现量子信息的保密通信.目前,美国和英国已实现在46KM的光纤中进行点对点的量子密钥传送,而且美国还实现在1KM以远的自由空间传送量子密钥,瑞士则实现了在水底光缆传送量子密钥(2)经典计算难题的量子算法.大整数素因子的分解问题是著名的公开密钥密码系统RAS安全性的基础.因为对于一个足够大的整数(比如500位以上的整数),即使是用高性能超级并行计算机,要在现实的可接受的有限时间內,分解岀它是由哪两个素数相乘的是一件十分困难的工作,所以多年来人们直认为RSA密码系统在计算上是安全的.然而,石破天惊, Peter Shor于1994年发表的大整数素因子分解量子算法(简称Shor算法)表明,在量子计算机上只要花费多项式的时间即可以接近于1的概率成功分解岀任意的大整数,这使得RSA密码系统安全性极大地受到威胁.因此,Shor算法的发现给量子计算机的研究注入新活力,并引发了量子计算研究的(3)乱序数据库的快速搜索.我们都知道,要在经典中国煤化工勺无序的数据库中搜索出指定的记录,算法的时间复杂性为O(N).因为搜索数,,以当记录数N充分大时,搜索工作犹如“在一大堆干草中搜寻出一根针”一样的烦与难.于是,人们另辟渠道.L·K· Grover于1997年在物理学界鼎尖杂志《 Physics Review Letters》上发表了一个乱序数据库搜索的量子算法,其时间复杂性为O(√N).此量子搜索算法与经典搜索算法相比达到√N数量级的加速,特别适用于求解那些需要用穷举法对付的NP类问题广西大学学报(自然科学版)第27卷5结束语自从Shor算法发表以来,国际计算机科学界十分重视量子计算理论和技术的研究,并取得若干重要的成果.我国计算机界从1997年左右开始涉足此领域,这是一个良好的开端.虽然量子计算机目前离实际应用尚有一段距离但是量子计算和量子信息技术所展现出的前景是光辉、灿烂的,它将对科学研究、军事和国民经济建设产生巨大、深远的影响参考文献[1] Vlatko Vedral, Martin B Plenio. Basics of Quantum Computation. Progress in Quantum Electronics[J].1998,22[2 Privman V, Vagner I D, Kventsel G. Quantum computation in quantum-Hall systems J. Physics Letters A, 1998239(3):141-146[3 Paolo Zanardi. Mario Rasetti Holonomic Quantum Computation[J]. Physics Letters A,1999.264(2-3):94-99[4 Jones J A NMR quantum computation[J]. Progress in Nuclear Magnetic Resonance Spectroscopy, 2001, 38(4)325-360[5 Vilela Mendes R, Ricardo Coutinho. On the Computation of Quantum Characteristic exponents[J. Physics Letters A,1998,239(4-5):239-245.[6]陆向艳,钟诚.密钥恢复技术分析[J].广西大学学报(自然科学版),2001,26(1):36-39.Quantum computation and its applicationsZHONG Cheng.2, CHEN Guo-liang(1. College of Computer and Information Engineering, Guangxi University, Nanning 530004, China: 2. Dept Of Computer Science, University of Science and Technology of China, Hefei 230027. ChinaAbstract: In this paper, the quantum computer model and its physical implementation, quantum com-putation procedure, quantum computation approach, design of quantum parallel algorithms are discussed, and the characteristic of exponential storage and speed-up of quantum algorithms is analyzedThe applications of quantum computation technologies in secret communication, cryptography systemand database searching are also discussedKey words quantum mechanics; quantum computer; quantum information; quantum parallel algorithms(责任编辑唐汉民刘海涛张晓云)中国煤化工CNMHG