核磁共振量子计算机与并行量子计算

１２物理与工程Ｖ０１．１３Ｎｏ．３２００３核磁共振量子计算机与并行量子计算龙桂鲁１’２’３肖丽１‘？

（１清华大学物理系，北京１０００８４）

（２量子信息与测量教育部重点实验室，北京１０００８４）（３中国科学院理论物理所，北京１０００８３）（收稿日期：２００３—４—２９）

ＮＵＣＬＥＡＲＭＡＧＮＥＴＩＣＲＥＳＯＮＡＮＣＥＱＵＡＮＴＵＭＣＯＭＰＵＴＥＲＡＮＤＰＡＲＡＬＬＥＬＱＵＡＮＴＵＭ

ＣＯＭＰＵＴＩＮＧ

ＬｏｎｇＧｕｉｌｕｌ＇２ＸｉａｏＬｉｌ’２（１ＤｅｐａｒｔｍｅｎｔｏｆＰｈｙｓｉｃｓ，ＴｓｉｎｇｈｕａＵｎｉｖｅｒｓｉｔｙ，Ｂｅｉｊｉｎｇ１０００８４）

（２ＫｅｙＬａｂｏｒａｔｏｒｙｆｏｒＱｕａｎｔｕｍＩｎｆｏｒｍａｔｉｏｎａｎｄＭｅａｓｕｒｅｍｅｎｔｓ，ＭｉｎｉｓｔｒｙｏｆＥｄｕｃａｔｉｏｎ，ＴｓｉｎｇｈｕａＵｎｉｖｅｒｓｉｔｙ，Ｂｅｉｊｉｎｇ１０００８４）

摘要在本文，我们首先回顾了量子计算的发展历史，阐述了核磁共振量子计算的原理．在叙述了利用有效纯态方法进行核磁共振量子计算之后，我们阐述了利用混合态进行核磁共振的量子计算的方法．首先是刘维尔量子计算方法，它是由Ｍａｄｉ，Ｂｒｕｓｈｗｅｉｌｅｒ，Ｅｒｎｓｔ等人１９９８年提出的，在这一模式ｅｅ，可以对搜索算法进行加速算法，Ｂｒｕｓｈｗｅｉｌｅｒ提出了一个指数速度的搜索算法．我们在３个比特的量子计算机中实现了这一搜索算法．我们在这一模式中提出了一个只需要一次搜索即可找标记物的直接拿取算法，并且在７个比特的核磁共振的量子计算机中实现了这一直接拿取算法．本文提出了在一个核磁共振量子计算机，或者更一般地一个系统量子计算机中实现多个量子计算机的并行计算．我们着重对量子搜索算法和Ｓｈｏｒ的大数分解算法进行了并行实现．在并行量子计算中，一部分量子比特处在纯态，一部分量子比特处在混合态．如果所有的量子比特都处在纯态上，则就是有效纯态量子计算，如果所有的量子比特都处在混合态上，则就是刘维尔量子计算．在这两个极限中间，相当于２个到Ｎ／２个量子计算机的并行计算．量子搜索方法可以很有效地进行并行计算，而Ｓｈｏｒ算法则只能在小的范围内进行并行计算．

１量子计算１．１为什么要研究量子计算机计算机在短短的四五十年里，已经在世

界家喻户晓，深人人们的工作和生活的方方面面，取得了巨大的成功．但是，现在为什么人们又开始研究其他种类的计算机呢？例如ＤＮＡ计算机及量子计算机等．我们从电子计

万方数据物理与工程Ｖ０１．１３Ｎｏ．３２００３１３

算机的发展，以及量子计算机的特点来回答这个问题．原因１随着科学技术的发展，电子计算机的集成化程度越来越高，集成片的尺度越来越小，计算能力是越来越强．根据Ｍｏｏｒ定律［１］，计算机芯片的集成化度，每１８个月增长一倍，也就是说，相同尺寸的存储器上的存储单元数目每过１８个月就增加一倍．按照这个趋势，到２０２０年左右，将发展到用单个原子的尺度．到那时，经典物理规律将不起作用，系统将受量子规律支配，表现出波粒二相性，电子计算机将无法工作．原因２芯片集成化速度的飞跃发展，电子计算机的运算功能比其初期提高了数百万倍，但由于其运行速度不断增快，晶体管间距离愈来愈近，将必然导致热力学问题的产生．这一问题产生于计算过程中的不可逆操作［２］，要解决这一问题自然需要进入量子力学的领域．因为量子计算机是可逆的［３￣６］．量子计算机的可逆还意味着可以从输入得到输出，同时可以从输出推出输入．原因３费曼的研究表明［６］，经典计算机不能有效地模拟量子体系．但是，对于大量的量子体系，能够精确求解的量子体系并不多，所以人们希望能够用计算机来模拟真实量子体系．量子计算机或量子模拟器［７’８３是量子体系的有效模拟工具，用量子计算机来模拟量子体系的演化［９］，验证量子物理规律，是量子物理学本身发展的迫切需要的技术支持．量子计算机的概念早在２０世纪８０年代初就由于费曼提出口１量子力学和计算机结合而萌芽；后来，Ｂｅｎｉｏｆｆ［３“１提出量子图灵机的概念；１９８５年，Ｄｅｕｔｓｃｈ［１阳提出量子计算机的具体概念．１９９２年，Ｂｒａｓｓａｒｄ和Ｂｅｒｔｈｉａ－ｕｍｅ［１１’１２］证明了量子图灵机理论上比经典图灵机快．虽然早已有量子计算机的概念，但是由于没有可以操作的实例进一步显示量子计算机在解决实际问题时的实际功能，故在很长一段时间它的发展很慢．１９９４年，Ｐ．ＳｈｏｒＥｌ３３利用量子纠缠性和叠加性提出著名的大数因子分解的量子算法——Ｓｈｏｒ算法，使得公开ＲＳＡ密钥系统受到巨大挑战，激发了人们研究量子计算机的高潮．１９９６年，Ｇｒｏｖｅｒ［１４３提出了在无序库中搜索某些满足特定条件的项目的算法——Ｇｒｏｖｅｒ量子搜索算法，使得从没有排序的Ｎ个数据中搜索一个确定的数据，只需Ｏ（￣／Ｎ）次运算，而利用经典计算机平均需用Ｎ／２次运算．１．２量子计算机的原理和特点量子计算机是相对经典计算机而言的，量子计算机并不是在通常的计算问题上取代传统的电子计算机，而是针对特定问题完成经典计算机难以胜任的高难度计算工作．它是以量子力学为基础，实现量子计算的机器．量子理论是物理世界的数学模型，从量子假设及实验结果可以得出许多奇特的性质．利用这些奇特的量子特性，量子计算机具有比经典计算机更强大的功能．量子力学的基本假设：（１）微观系统的物理状态由希尔伯特空间的一个矢量来描述．（２）微观系统的物理量由希尔伯特空间的厄米矩阵描述；物理量所能取的值，是相应矩阵的本征值；物理量Ａ在状态ｌ驴＞中取各值ａｉ的概率，与态矢量Ｉ妒＞按Ａ的归一化本征矢量｛ｌａ。））的展开式中Ｉ口ｉ）的系数的复平方成

正比．即与下式中Ｃ；的复平方成正比：Ｉ妒＞一芝：ｃｉａｉ＞，ｆｉ一（ａｆＩ驴＞

（３）微观系统的状态Ｉ妒（￡）＞随时间的变化规律由薛定谔方程来描述：ｉｈ丢ｌ如））一Ｈｌ她））

式中哈密顿量Ｈ为Ｐ，ｑ的矩阵函数（有如经典力学中哈密顿量Ｈ为Ｐ，ｑ变量的函数）．或者可以认为：

Ｉ妒（￡））一ｒ｝Ｉ妒（０）＞即体系的状态变化由己，矩阵ｅ－亡胁来刻画．（４）测量与塌缩：假定体系处于力学量万方数据１４物理与工程Ｖ０１．１３Ｎｏ．３２００３Ａ的本征矢ｆ口。＞和｝口。＞的叠加态Ｃ。｝ａ，＞＋ｆ。Ｉａ。＞，Ｉｃ。ｌ２＋１Ｃ。Ｉ２—１，然后我们对力学量Ａ进行测量，以ｉｃ。Ｉ２，ｆＣ。ｆ２的概率获得结果ａ，，ａ：，但是，一旦我们获得了确定的结果，体系的状态也就确定为ｆａ。＞或１ａ。），而不再是两者的叠加了．量子计算机的特点：（１）线性叠加性与经典计算机相对应，量子计算机也由存储器和运算器组成，其中运算器又由逻辑门网络组成．但是量子计算机的存储内容和逻辑门与经典计算机却有所不同．在经典计算机中，信息或者数据由二进制数据表示，每一个二进制数据位的０或１由电平的高低决定，在经典计算机中，每个数据位要么是０，要么是１，两者必居其一．量子计算机则不同，它的二进制数据位（我们称之为量子位（ｑｕｂｉｔ））的０或１由电子或原子的自旋状态或二能级系统的基态和激发态决定，由于量子力学中有叠加态（ｓｕｐｅｒｐｏｓｉｔｉｏｎ）的存在（从基本假设（１）可以得到），所以数据位可能是０，也可能是１，还可能同时是０或者１，即量子计算机的二进制数据位是０和１的任意叠加态，正因为如此，对于九个数据位的存储器，经典计算机只能存储一个托位二进制数，而量子计算机能同时存储２”个咒位二进制数．同样，对经典计算机来说，每一次操作只能对一个咒位二进制数实行处理，而量子计算机能同时对２”个二进制数进行处理．正是由于量子力学叠加态的存在，大大提高了量子计算的效率，实现了连续变量和真正意义上的并行计算．虽然经典计算机也可以利用并行性作用来减少某些算法所需要的时间，但若要使所需要的时间呈指数量级地减少，必须要指数量级地增加操作用的计算机数目，相应地，所需的物理空间指数量级增加．而在量子体系中，随着体系尺度的线性增加，并行量则指数增加，即量子体系中并行量的指数增加仅使物理空间线性增加，这是量子并行与经典并行之间的差别．（２）干涉性量子干涉性可直接从态叠加原理中推导出来．对于挖个量子位，量子计算机的叠加态可以表示为

这种叠加不是简单的几率相加，而是几率幅相加，故量子态有相对位相差，在演化过程中会出现干涉相长或相消，这是经典布尔态所不具备的．干涉性在量子超快算法中被应用．（３）纠缠性在量子体系中，不同的体系间可以存在量子纠缠．量子纠缠是一种没有经典对应的关联，它不是一种动力学效应，而完全是一种量子效应．建立纠缠时需要相互作用，但一旦量子纠缠建立了，撤消相互作用，量子纠缠仍然保持．量子纠缠在量子通信［１５￣１８］中有着举足轻重的作用．（４）不可克隆性由于量子力学的态叠加原理和系统态的演化遵从么正变换，使得任何量子体系的任意未知量子态无法被完全复制［１９’２０］．即无法在不破坏原来未知态的情况下对之进行观察和测量．我们无法克隆不可知的量子态是我们进行密码通信的基础．量子计算除了并行性的特点外，还有另一个特点就是量子计算的随机性［２８１．量子计算机是一个真正意义上的随机计算机．Ｗｉｌｌｉａｍｓ［２９］认为利用量子的随机性产生随机数进行编码，可以在密码通信中加以利用．另外，在某些算法中加入一些随机性，可以得到更有效的算法［３０］．１．３量子计算的基本概念量子力学用于计算科学，产生了新的基本概念，在前面涉及到量子位（ｑｕｂｉｔ）和量子逻辑门（１０９ｉｃｇａｔｅ）的概念．在此，将稍加详细的进行讨论．（１）量子位量子位是量子信息的一个基本单位Ⅲ３，任何一个两态的体系如自旋为１／２的核和两能级原子都可以作为一个量子位．量子位和经典位的区别在于：一个经典（下转第２０页）

万方数据