量子计算及其应用

第２７甚第１期　２０３２年３月　广西大学学报ｔ自然科学版）　Ｊｏｕｒｎａｌ　ｏｆ　Ｇｕａｎｇｘｌ　Ｕｎｉｖｅｒｓｉｔｙ（Ｎａｔ　Ｓｃｉ　Ｅｄ）　Ｖｏ【２７．Ｎｏ　ｌ　Ｍａｒ．．２０６，２　文章编号：ｉ００１－７４４５（２００２）０１—００８３－０４　量子计算及其应用　钟诚　，陈国良　（１．广西大学计算机与信息工程学院．广西南宁５３０００４；２．中国科技大学计算机系，国家高性能计算中　Ｌ　安徽台肥２３００２７）　摘要：讨论量子计算机模型及其ｌ物理实现方案、量子计算过程、量子计算模型和量子并行算｝击，分析量子计算　的指数级存储容量和指数加速特征．并简述量子计算和量子信息技术在保密通信、密码系统、数据库搜索等重　要领域的应用　关键词：量子力学；量子计算机；量子信息；量子并行算法　中国分类号：ＴＰ３０１　文献标识码：Ａ　电子、计算机与信息技术发展一日千里．电子元器件日益微型化的结果是使得一个徽电子元件所包　含的原子数目可以达到一个或几个，一个逻辑操作的耗能将达到不可逆逻辑操作的热力学极限ＫＴ量　级．这使得经典计算机芯片内集成电子元件的数量受到很大的，ＣＰＵ速度的增长开始减缓．此种趋　势促使人们考虑研究遵循量子力学原理的量子计算机和量子计算技术．２０世纪后期以来科学家们在量　子计算机的研制、量子计算和量子通信技术等方面取得了令人鼓舞的成就．专家门预测，２ｌ世纪将是研　究、开发与应用“量子计算机”、“量子计算”和“量子通信”技术的新时代，相信在可预见的不久的将来量　子计算机将从实验室走向市场，量子信息技术将在科学研究、军事和国民经济各领域得到广泛应用．本　文从计算机科学的角度筒述量子计算的有关问题以及量子信息技术的应用，以期引起更多的读者对量　子计算和量子通信技术的关注．　１　量子计算机模型及其物理实现方案　目前提出的量子计算机模型主要有量子Ｔｕｒｉｎｇ机模型、量子门组线路模型和量子细胞自动机模型　等．量子Ｔｕｒｉｎｇ机模型可以用多项式大小的量子门组网络，或者用量子门组网络多项式大小的时间来　模拟．实现量子计算机的物理方案有离子阱（Ｉｏｎ　Ｔｒａｐ）、腔量子电动力学（腔ＱＥＤ）、核磁共振（ＮＲＭ）　和量子点（Ｑｕａｎｔｕｍ　Ｄｏｔ）等．离子阱方案的主要优点是阱中的超冷离子处于一个几乎与外界隔绝的空　间中，由环境引起的消相干效应非常小，因此使得量子计算的并行度较高；其主要缺点是时钟速度太慢，　用数目极大的激光束脉冲操作各个离子执行逻辑运算时，运算速度难以提高．腔量子电动力学方案的主　要优点是两个量子位之间相互作用的时间尺度大大小于离子阱方案，因此其可以在单位时间内完成更　多的操作步骤．利用核磁共振技术实现量子计算机较为成熟．而量子点方案的优点则是量子位可以是嵌　套在固体材料中的固态量子器件，这与经典计算机的大规模集成电路的设计相似　以前，研究量子计算机似乎只是物理学家感兴趣的事情．但是，自从１９９４年ＡＴ　．２Ｏ世纪９０年代　公司的科学家Ｐｅｔｅｒ　Ｓｈｏｒ发表震惊世界的大整数素因子分解量子算法（此论文于１　９９８年荣获世界数学家大会最高奖）以　来，立刻引起了越来越多的计算机科学家对量子计算的重视，在国际上进一步掀起量子信息技术的研究　热潮．截止到２０００年，美国已成功地建立４个量子位的离子阱量子计算机，同时美国和德国的科学家刺　收稿日期：２００１一ｌＯ　２５；修订日期：２００２—０１—１０　基金项目　国家９７３计划（Ｇｌ９９８船Ｏ４Ｏ３）　作者简介：神诫（１９６４一），男，广西桂平人＋广西大学教授，中国科技大学博士生　维普资讯 http://www.cqvip.com

广西大学学报（自爨科学版）　第２７卷　用核磁共振技术成功地建立５个量子位的量子计算系统，在中国则利用核磁共振技术成功地建立３个　量子位的量子计算机；据最新报道，２００１年日本利用核磁共振技术已研制出１　６个量子位的实验性量子　计算机原型．目前，各国正向建立更多量子位的、实用的量子计算机的目标努力，并不断取得新进展．　２量子计算过程　众所周知，经典的冯・诺依曼数字电子计算机是遵照图灵（Ｔｕｒｉｎｇ）计算模型设计和制造的．这是因　为从经典意义上而言，“计算”属于数学范畴，“计算”的理论与方法可以脱离具体的物理过程，依靠纯粹　的思辨和抽象的逻辑推理构造出来．但是，“计算”本质上可以看作是计算仪器的物理系统所执行的一个　物理过程．根据采用的计算设备的不同，这一物理过程也不尽不相同，它可以是人脑所完成的“计算”、算　盘操作的。计算”和电子计算机控制的“计算”，等等．不管采用何种计算设备，“计算”的一般过程是：首先　输入原始数据，从物理的角度看这可以解释为在计算系统中制备出一个初始物理态；然后执行计算．这　个过程实际是按照算法规定的步骤，将给定的初始物理态演化成对应输出物理态的过程：最后输出计算　结果，这可以看作对演化的物理末态进行测量得到所需信息的过程．量子计算机是一种遵循量子力学原　理完成计算任务的系统，它采用量子态编码信息，其存储量子信息的基本单元是称为量子位（ｑｕｂｉｔ）　的量子双态系统（或者说是一个二维Ｈｉｌｂｅｒｔ空间）．可以将量子计算机看成是由一系列量子门构成的　电路、假设该电路由　个逻辑门构成并作用在ｍ个量子位上、一个量子位是一个微观粒子构成的两基　态　０．１ｊ系统．一个量子位除了可以处于Ｏ态和１态之外，还可以处于它们的迭加态．量子位的迭加态　Ｉ　＞可表示如下：Ｊ　＞　Ｐ。ｆ　０＞４－Ｐ１　１＞．其中Ｐ。和Ｐ　均为复数，表示基态０和ｉ的振幅（概率幅），　Ｉ　Ｉ　和Ｉ户　Ｉ　分别表示系统处于基态０和１的概率，且满足归一化，即满足＞：ＡＩ　＝１．当对量子系统的　迭加态　＞进行测量时，量子寄存器的状态以－Ｐ　１　的概率处于１　０＞态，以１　Ｐ　１　的概率处于　１＞态．　与经典计算机的数据表示相似，量子计算机的数据用量子寄存器中所有量子位的共同量子状态来　表示．一般地，一个　位经典计算机的寄存器仅处于惟一的状态（Ｏ或ｉ）中，而一个　位的量子寄存器却　可以处于２　个基态的相干造加态Ｉ　＞中．迭加态Ｉ　＞和基态　＞的关系可表示如下：　＞一　∑户．Ｉ　．．　其中Ｐ．为复数，表示振幅（概率幅），ＩＰ．Ｉ　给出迭加态　＞在受到与量子计算系统相纠缠的仪器测　量发生散落时坍缩到基态ｌ　＞的概率，且满足　１Ｐ　ｌ。；１．量子寄存器用于存储量子位信息．量子　寄存器的状态描述量子计算机的状态．一个　个量子位的量子寄存器能够同时存储２　个状态信息（即２　个数据），因此，量子计算机具有经典计算机无可比拟的、指数级的海量存储能力．量子门对量子寄存器　进行操作，实现量子态的转换（即实现对量子寄存器中的数据进行计算、处理）．量子计算的过程是：首先　制备出处于选加、等振幅（等概率）的量子初态，然后按照算法需要对迭加态不断进行演化（量子门操　作，幺正变换），最后对最终的迭加态进行测量使其以接近于１的概率坍缩到所希望的态，从而得到所需　的计算结果．对于量子计算系统，因为可以制备出由各个互不相同的态迭加所形成的初始态，量子计算　机具有对这些初始态同时进行演化的能力，也即量子计算机可以沿着各条互不相同的路径同时演化初　始选加态，直至获得对应的输出的迭加态．对于一个　个量子位的量子寄存器，由于其屙时存储了２“个　状态信息（２　个数据），所以对量子寄存器进行一次量子门操作即可实现对２　个状态信息（２　个数据）进　行计算、处理．这说明量子计算机具有天然的并行性，极大地加快对海量信息处理的速度，使得大规模复　杂问题能够在有限的指定的时间内完成．量子计算系统这种指数级加速的“并行处理”特性使得它具有　比经典计算机更快速、更强大的信息处理能力，特别适合于求解一类ＮＰ完全问题　（参见：Ｋｅｖｉｎ　Ｍａｒｋ　Ｏｂｅｎｌａｎｄ．Ｕｓｉｎｇ　Ｓｉｍｕｌａｔｉｏｎ　ｔｏ　ＡＳＳｅＳＳ　ｔｈｅ　Ｆｅａｓｉｂｉｌｉｔｙ　ｏｆ　Ｑａａｎｔｕｍ　Ｃｏｍｐｕｔｉｎｇ．Ｐｈ．Ｄ　Ｄｉｓｓｅｒｔａｔｉ０ｎ，　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｓｏｕｔｈｅｒｎ　Ｃａｌｉｆｏｒｎｉａ，１９９８．８．）．　３　量子计算模型和量子并行算法　量子算法具有量子态相干迭加、量子并行、量子态纠缠和测量坍缩等特性．由于量子计算的过程是　维普资讯 http://www.cqvip.com

第１期　钟　诚等：量子计算及其应用　量子系统初态｛　＞经过与量子计算机控制系统的相互作用，随时间演化成所需束态ｌ　ｍ＞的过程，所　以假设量子计算机控制系统由量子门　（ｚ一１，２＋…．　）和量子门后的测量算符　到的中间结果用态矢序列｛　Ｍ　表述，演化计算得　∥　……　一　）表述，那么一个简化的量子计算模型可描述如下：　．……Ｍ　Ｕ２Ｍ１【　（　。＞）一Ｍ　ｕ　……ｌⅥ　Ｕ　Ｍ（１　１＞）一Ｍ　ｕ　……Ｍ：Ｕ　（１　＞）一一…＝　Ａｆ　（１　＞）一　＞．　＞）一　＞，在设计量子算法时可　用幺正变　对于上述量子计算模型中的每一次变换ｕＨ（１　换矩阵和态矢量相乘来实现．没有某个量子算法，，Ｕ，表示一个量子门完成的线性变换，当将ｕ，作用于　某个迭加态时，根据量子算法的并行性，它会同时作用到该迭加态的所有基态上，并将所有结果进行迭　加以产生一个新的迭加态．因此，为了计算函数，　），仅需应用一次　，操作即可并行计算出　取２　个　不同值的／　）的结果：　２　１　２　Ｕｊ（　Ｐ　ｊｚ＞１　０＞）一　ｊ　０　Ｐ．Ｕｊ１ｚ＞ｊ　０＞＝　＝０　Ｐ．１　＞Ｉｆ（ｘ）＞．　ｊ一０　其中．１　＞｛０＞表示系统由两个量子寄存器组成，第１个量子寄存器ｚ＞表示基态（存储自变量　．２－的值ｊ＋第２个量子寄存器ｌ　０＞用于存储计算ｆ（ｚ）的结果，其初始值为０．为了获取计算结果，需要对　量子寄存器进行测量．所谓测量是将系统的状态投影到某个基态上，提取出相应的概率幅．当测量第１　个量子寄存器时，会导致系统状态从迭加态坍缩到某个确定的基态｛ｚ＞上，由于第１个量于寄存器和　第２个量子寄存器是纠缠在一起的，所以第２个量子寄存器会关联坍缩到某个确定的结果态／【　）＞　上．为此＋在设计量子算法时需要确保最后得到的结果态的概率最大．例如，若希望得到　一１　０ｌ的结果　ｆｃｉ０１），那么量子算法的控制应使得基态｛１０１＞对应的概率幅最大，这样测量时第２个量子寄存器即　坍缩到态ｊ／（１０１）＞上．　４量子计算技术的应用　Ｃ１）量子信息保密通信．量子信息是用量子态编码的信息，量子态具有事先不可确定的特性，即量　子态是未知态．量子信息满足“量子态不可完全克隆（Ｎｏ—Ｃｌｏｎｉｎｇ）定理”，这样在量子信道上传输量子　信息过程中，即使窃听者截获了用量子态表示的密钥，他也不可能完垒恢复出原本的密钥信息，　而他　不能破译秘密信息，这是因为恢复密钥是破译密码系统的关键【６一、此外，Ａ．Ｋ．Ｐａｔｉ等人利用量子力学　的线性性证明任意未知量子态拷贝的完全删除也是不可能的，即密码攻击者不能破坏量子信息传输的　完整性．因此，在量子信道上可以实现量子信息的保密通信．目前，美国和英国已实现在４６ＫＭ的光纤　中进行点对点的量子密钥传送，而且美国还实现在１ＫＭ以远的自由空间传送量子密钥，瑞士则实现了　在水底光缆传送量子密钥．　（２）经典计算难题的量子算法．大整数素因子的分解问题是著名的公开密钥密码系统ＲＡＳ安全性　的基础．因为对于一个足够大的整数（比如５００位以上的整数），即使是用高性能超级并行计算机，要在　现实的可接受的有限时间内，分解出它是由哪两个素数相乘的是一件十分困难的工作，所以多年来人们　一直认为ＲＳＡ密码系统在计算上是安全的．然而，石破天惊，Ｐｅｔｅｒ　Ｓｈｏｒ于１９９４年发表的大整数素因　子分解量子算法（简称Ｓｈｏｒ算法）表明，在量子计算机上只要花费多项式的时间即可以接近于Ｊ的概率　成功分解出任意的大整数，这使得ＲＳＡ密码系统安全性极大地受到威胁．因此＋Ｓｈｏｒ算法的发现给量　子计算机的研究注入新活力，并引发了量子计算研究的热潮．　ｔ３）乱序数据库的　速搜索．我们都知道，要在经典计算机上从Ｎ个记录的无序的数据库中搜索　出指定的记录，算法的时间复杂性为０（Ⅳ）．因为搜索数据库是在外存进行的，所以当记录数Ⅳ亢分大　时，搜索工作犹如“在一大堆干草中搜寻出一根针”一样的烦与难．于是，人们另辟渠道．Ｉ　・Ｋ・Ｇｒｏｖｅｒ　于１　９９７年在物理学界鼎尖杂志￣；Ｐｈｙｓｉｃｓ　Ｒｅｖｉｅｗ　Ｌｅｔｔｅｒｓ》上发表了一个乱序数据库搜索的量子算法，其　时间复杂性为Ｏ（　Ⅳ）．此量子搜索算法与经典搜索算法相比达到＿／Ⅳ数量级的加速，特别适用于求解　那些需要用穷举法对付的ＮＰ类问题　维普资讯 http://www.cqvip.com

广西大学学子旺（自然科学版）　第２７卷　ｎ　ｈ鲳　５结束语　自从Ｓｈｏｒ算法发表以来，国际计算机科学界十分重视量子计算理论和技术的研究，并取得若于重　要的成果．我国计算机界从１　９９７年左右开始涉足此领域，这是一个良好的开端．虽然量子计算机目前　一．　　离实际应用尚有一段距离，但是量子计算和量子信息技术所展现出的前景是光辉、灿烂同．１盯　　涛对科学　研究、军事和国民经济建设产生巨大、深远的影响．Ｄ　　Ｋ　参考文献：　Ｌ１］ＶｌａｔｋｏＶｅｄｒａＩ，Ｍａｒｔｉｎ　Ｂ．Ｐｌｅｎｉｏ　Ｂａｓｉｃｓ　ｏｆＱｕａｎｔＧ　ｕｍ　Ｃｏｍｐｕｔａｔｉｏｎ．ＰｒｏｇｒｅｓｓｉｎＱｕａｎｔｏｍ　Ｅ１ｅｃｔｒｏ　ｉ　．１　９９８．２２　Ｑ　ｍ　［３：　Ｐａｏ］ｏ　Ｚａｎａｒｄｌ，Ｍａｒｌｏ　Ｒａｓｅｔｔｉ．Ｈｏｌｏｎｏｍｉｃ　Ｑｕａｎｔｍ　ｕｍ　Ｃｏｍｐｕｔａｔｉｏｎ￣Ｊ］Ｐｈｙｓｉｃｓ　Ｌｅｔｔｅｒｓ　Ａ，１９９９，２５４（２　３）．９４　９９．　Ｅ４３　Ｊｏｎｅ￣Ｊ　Ａ　ＮＭＲ　ｑｕａｎｔｕｍ　ｃｏｍｐｕｔａｔｉｏｎＥＪ￣．Ｐｒｏｇｒｅｓｓ　ｉｎ　Ｎｕｃｌｅａｒ　Ｍａｇｎｅｔｉｃ　Ｒｅｓｏｎａｎｃｅ　Ｓｐｅｃｔｒｏｓｃｏｐｙ，２００１，３８ｆ４）　３２９—３６０．　Ｅｓ］　Ｖｉｌｅｌａ　Ｍｅｎｄｅｓ　Ｒ，Ｒｉｃａｒｄｏ　Ｃｏｕｔｉｎｈｏ．Ｏｎ　ｔｈｅ　Ｃｏｍｐｕｔａｔｉｏｎ　ｏｆ　Ｑｕａｎｔｕｍ　Ｃｈａｒａｃｔｅｒｉｓｔｉｃ　ｅｘｐｏｎｅｎｔｓ［Ｊ　７．Ｐｈｙｓｉｃｓ　Ｌｅｔ　ｔｅ　ｓ　Ａ，１９９８，２３９（÷ｊ）：２３９　２４５．　Ｅ６１　陆向艳，钟诫密钥恢复技术分析＿Ｊ］广西大学学报（自然科学版）．２００１，２６（１）：３６—３９ｍ　　Ｑｕａｎｔｕｍ　ｃｏｍｐｕｔａｔｉｏｎ　ａｎｄ　ｉｔｓ　ａｐｐｌｉｃａｔｉｏｎｓ　ＺＨＯＮＧ　Ｃｈｅｎｇ　～，ＣＨＥＮ　Ｇｕｏ　ｌｉａｎｇ　（１　Ｃｏｌｌｅｇｅ　ｏｆ　Ｃｏｍｐｕｔｅｒ　ａｎｄ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｇｕａｎｇｘｉ　Ｕｎｉｖｅｒｓｉｔｙ，Ｎａｎｎｉｎｇ　５３０００４　ｅｒ　Ｓｃｉｅｎｃｅ，Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ　ｏｆ　Ｃｈｉｎａ．Ｈｅｆｅｉ　２３００２７．Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：ｉｎ　ｔｈｉｓ　ｐａｐｅｒ，ｔｈｅ　ｑｕａｎｔｕｍ　ｃｏｍｐｕｔｅｒ　ｍｏｄｅｌ　ａｎｄ　ｉｔｓ　ｐｈｙｓｉｃａｌ　ｉｍｐｌｅｍｅｎｔａｔｉｏｎ．ｑｕａｎｔｕｍ　ｃｏｍ　ｐｕｔａｔｉｏｎ　ｐｒｏｃｅｄｕｒｅ，ｑｕａｎｔｕｍ　ｃｏｍｐｕｔａｔｉｏｎ　ａｐｐｒｏａｃｈ，ｄｅｓｉｇｎ　ｏｆ　ｑｕａｎｔｕｍ　ｐａｒａｌｌｅｌ　ａｌｇｏｒｉｔｈｍｓ　ａｒｅ　ｄｉｓ—　ｃｕｓｓｅｄ，ａｎｄ　ｔｈｅ　ｃｈａｒａｃｔｅｒｉｓｔｉｃ　ｏｆ　ｅｘｐｏｎｅｎｔｉａｌ　ｓｔｏｒａｇｅ　ａｎｄ　ｓｐｅｅｄ　ｕｐ　ｏｆ　ｑｕａｎｔｕｍ　ａｌｇｏｒｉｔｈｍｓ　ｉｓ　ａｎａｌｙｚｅｄ．　Ｔｈｅ　ａｐｐｌｉｃａｔｉｏｎｓ　ｏｆ　ｑｕａｎｔｕｍ　ｃｏｍｐｕｔａｔｉｏｎ　ｔｅｃｈｎｏｌｏｇｉｅｓ　ｉｎ　ｓｅｃｒｅｔ　ｃｏｍｍｕｎｉｃａｔｉｏｎ，ｃｒｙｐｔｏｇｒａｐｈｙ　ｓｙｓｔｅｍ　ａｎｄ　ｄａｔａｂａｓｅ　ｓｅａｒｃｈｉｎｇ　ａｒｅ　ａｌｓｏ　ｄｉｓｃｕｓｓｅｄ．　Ｋｅｙ　ｗｏｒｄｓ；ｑｕａｎｔｕｍ　ｍｅｃｈａｎｉｃｓ；ｑｕａｎｔｕｍ　ｃｏｍｐｕｔｅｒ　ｑｕａｎｔｕｍ　ｉｎｆｏｒｍａｔｉｏｎ；ｑｕａｎｔｕｍ　ｐａｒａｌｌｅｌ　ａｌｇｏ　ｒｉｔｈｍｓ　（责任编辑唐汉民刘海涛张晓云）