量子信息基础与量子算法

1、专题报道Cover Features Communications of CCF 2008/7 14量子信息基础与量子算法龙桂鲁引言量子信息学是涉及量子力学、信息论、计算机科学的交叉学科，诞生于20世纪70年代末，在20世纪90年代中期得到迅速发展。量子信息学的研究内容包括量子计算、量子通信。本文主要介绍量子信息学基础、量子力学基础、量子通信以及几种典型的量子算法。量子计算机这个现在经常被人提起的名词诞生在18年前。它是沿着两条不同的发展路线发展的：一条路线是可逆计算机，可以极大地减少量子计算机热耗。贝尼奥夫（Benioff ）首先利用量子力学理论构造了这种量子计算机1；另一条路线是需求（对量

2、子体系模拟的需求），费曼（Feynman ）指出，对一个量子力学体系进行模拟，所需的计算量与体系大小成指数函数关系，经典计算机是无法满足模拟需要。对量子体系的模拟，必须使用以量子迭加态进行计算的量子计算机2。早期对量子计算机的研究非常少，全世界大约只有10位科学家涉猎此类工作。1995年，肖尔（Shor ）构造了大数质因子分解的量子算法3，显示出量子计算机超越经典计算机的强大潜能，引起了美国国防和安全部门的重视。这极大地推动了量子计算机研究，使量子计算机成为学术研究前沿和战略目标。大约在量子计算机提出的同一时期，威斯纳（Wiesner ）提出了利用量子力学制备不可复制的钞票的方案，但是因为过于

3、超前和脱离现实，被审稿人否定。1984年，班内特（Bennett ）和布拉萨德（Brassard ）两人将威斯纳的思想用于通信4，证明量子力学原理可以保证通信的安全性，从此诞生了量子通信。1992年，班内特等6人一起提出了一个量子通信方案：利用量子纠缠，不需要传递实物粒子就可以把一个量子物体的状态转移到遥远地方的另一个粒子上，这就是量子隐形传态5。本文着重介绍基础性知识和一些新的发展方向，如需要比较详细系统的阅读，请参考文献6,7。一些新的进展请参考文献8-11。量子力学简介量子力学基本假设有关量子力学的教科书请参阅文献12-14。量子力学有五个基本假设：1量子系统的状态可以用希尔伯特（Hil

4、bert ）空间中的态矢量 来描述。2量子系统的所有力学量都对应希尔伯特空间中的线性厄米算符或厄米矩阵。3对处在状态 的量子力学体系测量力学量 ，测量得到的结果只能是算符 的本征值，测得本征值 的概率正比于 测量之后的瞬间，体系的波函数突变到测得的本征值 所对应的本征函数 上。测量带来的波函数突变叫做波函数的塌缩，又叫做冯诺依曼（Von Neumann ）约化（Reduction ）。4孤立量子系统的态矢量 随时间演化遵从薛定谔（Schrödinger）方程：Communications of CCF 2008/7 15， （1）其中 是系统的哈密顿量。5描述全同粒子系统的态矢量，对

5、于任意一对粒子进行交换，是对称或反对称的。服从前者的粒子称为玻色子，服从后者的粒子称为费米子。量子态迭加原理如果 是量子系统所有可能的态，那么它们的任意线性迭加态（2）仍然是此量子系统的一个可能的态。量子态迭加原理与经典的态迭加原理的本质区别体现在测量上。对经典物理的迭加态进行测量，我们得到的结果是处在迭加态中各个子态的中间情况。例如测量经典的自旋为1/2的粒子的自旋向上和向下的态的等幅迭加态的自旋第三分量，我们得到为零。而对于处在量子力学迭加态的粒子做同样的测量，我们只能得到向上或者向下的结果，不可能得到自旋为零的结果。经典物理中的迭加是几率的迭加，而量子物理中的迭加是几率幅的迭加，是同一个

6、量子体系各个可能状态的线性迭加，迭加后的态是此量子体系的一个新态，具有新的特性。测不准原理简单地说，不可能对一个物理体系同时测准两个不相容的物理量。不相容的物理量是不对移的。例如，坐标和动量就是一对不相容的物理量，不可能同时测准微观粒子的位置和动量，它们的不确定性满足。密度算符和约化密度矩阵如果一个量子力学体系能够用一个波函数来描述，我们称它处在一个纯态上；否则，我们称它处在一个混合态上。处在混合态上的粒子以一定的概率出现某个波函数上。通常有三种情况可以用密度矩阵或者混合态来描述一个量子力学体系的状态。有关密度矩阵可参考文献15。第一种情况，假设有一个由N 个量子力学体系组成的系统，为了简便，

7、将每个这样的量子力学体系称为一个分子。这些分子之间是独立的、没有相互作用的。有 个粒子处在态 上，共有k 种波函数， 。对于这样的一个大系统，如果随机地从里面取出一个分子，那么这个分子就有 的几率处在态上。这个大系统中的分子的平均状态可以写成第二种情况是对于复杂的耦合系统。如果只注意其中的一部分子系统的时候，就无法用态矢量来描述系统的全部信息。在这种情况下也引入密度算符来描述量子系统及其演化。 例如对于两个粒子A 和B 组成的复合系统，它的状态可以写成 。相应的密度算 符就是 如果只考虑其中的A 粒子，则其状态可以 用以下密度矩阵表示（6）其中 是求迹，是对B 粒子状态求平均。第三种可以有混合

8、态的情况是，假设一个量子体系处在一个多变的环境，如果不关心它的瞬时状态，只想知道它在一段时间内的平均状态，此时可以对它进行时间的平均，从而得到混合态。这种情况与第一种情况类似，是将第一种情况的对空间平均换成了对时间的平均。量子信息的理论基础非克隆定理非克隆定理16的内容为：一个未知的量（3）（4）（5）( 为普郎克常数专题报道Cover Features Communications of CCF 2008/7 16子态不能被完全拷贝。虽然量子态不能精确克隆，但是可以近似克隆，或者可以进行概率地精确克隆17。量子幺正操作和量子逻辑门根据量子力学理论，孤立量子系统态矢量随时间的动力学演化遵从薛定

9、谔方程（7）幺正算符 对应的变化通常被称为幺正变换或幺正操作。演化算符的幺正性使得量子信息过程有一些特殊的性质：（1）保几率性，即量子态的归一化性质不随时间的改变而改变，量子系统的总几率保持不变；（2）可逆性，即量子信息处理中的所有逻辑操作都是可逆的。在量子信息处理过程中，系统的幺正演化通过量子逻辑门来完成，根据作用的量子位数目，量子逻辑门被分为单量子比特门、二量子比特门和多量子比特门。常见的单比特量子门主要有 和沃尔什-哈德曼（Walsh-Hadamard ）门H 。量子受控非门（C N O T 门）是最常用的二比特量子门之一，其中的两个量子比特分别为控制比特与目标比特。当控制比特为时，它不

10、改变目标位；当控制比特为时，它将翻转目标位。量子纠缠态和贝尔不等式理论量子纠缠态的定义是：对于两粒子系统A 和B ，如果存在态 和 使得两粒子系统的量子态可以写成直积形式 ，则称此量子系统处于直积态（product state ）；否则，称此量子系统处于纠缠态（entangled state ）。伯姆（Bohm ）针对自旋为1/2的二能级量子体系提出了简化的纠缠态形式18，称之为贝尔（Bell ）基态，其中 和 分别表示二能级体系的2个本征态。经研究发现，贝尔基态是两粒子系统的最大纠缠态。对于三粒子的情况，格林伯格（Greenberger ）、霍姆（Horne ）和泽林格（Zeilinger

11、）三人给出了三体最大纠缠态的形式19，称为GHZ 态，（9）1964年，贝尔从隐变量和定域实在论出发，导出了一个不等式来判断量子力学还是隐变量理论正确20。利用贝尔不等式可以在实验上检验定域性，（10）其中 是对A 、B 粒子在 方向上进行测量得到的测量结果的关联函数，隐变量理论满足上式，而量子力学中有些状态不满足，考虑两粒子纠缠态（11） 就破坏贝尔不等式。贝尔不等式后来被推广为多种形式。1969年，克劳泽（Clauser ）、霍姆、奚模尼（Shimony ）和霍尔特（Holt ）提出了CHSH 不等式21，在这之后，各种贝尔型定理相继被提出，为研究量子力学和定域实在性之间的矛盾提供了场所。

12、1982年阿斯佩克（A s p e c t ）等人进行了贝尔定理的验证实验22。实验结果与量（8）（12）Communications of CCF 2008/7 17子力学符合，从而验证了纠缠粒子对违背了贝尔不等式，量子力学是非定域的。虽然现在大多数人相信量子力学是正确的，但是现有的实验还有缺陷，还不能完全说服反对者。量子纠缠的非局域性没有经典的类比现象，如何理解量子纠缠一直是争论的热点。目前研究一个量子态是否纠缠，以及如何判断量子纠缠的大小是量子信息的基础理论研究中的重要研究方向23。实验上已经实现了多个光子的纠缠态25和在任何自由度上都纠缠的超纠缠光子对26。量子通信简单地说，量子通信就

13、是通过量子信道实现经典信息或者量子状态的传输。按照这种定义量子隐形传态、密集编码等都属于量子通信。有的作者将量子密钥分配叫做量子通信，读者在阅读时需要注意。量子隐形传态量子隐形传态是根据英文Q u a n t u m Teleportation 翻译来的，也可译成“量子离物传态”。它的实质是利用量子纠缠，使得一个粒子在A 处的状态消失，而在另外一个地点B 处出现。量子隐形传态没有经典对应模式，是量子力学特有的。它是班内特等六个人在1993年提出的5，有的作者把这个最初方案就做六人方案，其原理如图1所示。手中有一个粒子，爱丽丝不知道它的量子状态。要求爱丽丝不实际发送手中的粒子，把它的状态传送给远

14、处的鲍勃。量子隐形传态过程可以摘述如下：假设爱丽丝手中的未知量子态为其中 。为了完成未知量子态的传输，爱丽丝和鲍勃先共享一对状态为 的EPR 1对，并分别拥有纠缠对 中的2和3粒子。然后，爱丽丝对未知态粒子A 和粒子2做联合贝尔基测量，此过程是一个重纠缠的过程。此时，爱丽丝将以相等的概率测量得到4个贝尔基态，得到每个贝尔基态的几率各占1/4。当爱丽丝完成贝尔基测量后，鲍勃手中的粒子3就会塌缩到对应的量子态。此时，爱丽丝告诉鲍勃她得到的测量结果，鲍勃可以通过选择适当的幺正操作来将粒子3的量子态转换到爱丽丝原来的未知量子态，即恢复到量子态 ，从而实现未知量子态的离物传输。虽然在爱丽丝做测量时状态的

15、塌缩是瞬时发生的，但是这里并不能实现超光速通信。因为只有量子态的塌缩并不能够实现信息的传输，鲍勃只有在得到了爱丽丝的测量结果之后才能实现粒子状态的转移。而爱丽丝的测量结果需要通过经典通信传输，因此不可能进行超光速通信。最近发展的受控量子隐形传态，在量子保密通信上具有重要的应用27。量子纠缠转移量子纠缠转移也是在1993年提出的28。其原理如图2所示。假设粒子l 和k 处在纠缠态，粒子m 和n 也处在纠缠态上。纠缠态有一个特性，即使它们离开很远，它们之间的纠缠状态也能保持。如果将粒子k 和粒子m 放在一起并进行贝尔基的测量。测量之后这4个粒子组成的体系的波函数就会发生塌缩。塌缩之后，粒子l 和n

16、 就会产生纠缠，而此前它们之间是没有 纠缠的。图1 量子隐形传态原理图在量子隐形传态中，通信双方爱丽丝（Alice ）和鲍勃（Bob ）的任务是：爱丽丝专题报道Cover Features Communications of CCF 2008/7 1量子中继就是利用了量子纠缠转移。假设有三个地点A 、B 和C ，B 点在中间。如果A 和B 之间有量子纠缠态，B 和C 之间有量子纠缠态，通过量子纠缠转移就可以实现A 和C 之间的量子纠缠。依次类推，可以实现任意长距离的粒子之间的量子纠缠，从而实现量子中继。量子密集编码量子密集编码是指利用量子纠缠，虽然只传送1个比特，但是却传送了2个比特的信息的一

17、种量子通信。它是1992年由班内特和威斯纳提出的29，其原理如图3所示。它的过程是：在通信前，接收者鲍勃将量子态制备在贝尔基态上。鲍勃保留粒子B ，并将粒子A 发给爱丽丝，此时，鲍勃和爱丽丝之间就共享了一对纠缠粒子对爱丽丝接收到粒子A 后，选择4个幺正操作 和 来改变由A 和B 粒子组成的量子系统的量子态。然后，爱丽丝将粒子A 再发送给鲍勃，鲍勃对AB 粒子做联合贝尔基测量，从而得到爱丽丝所做的幺正操作信息。这样鲍勃就通过一个粒子的传输而传送了4个量子操作的信息。如果通信双方事先约定量子操作 和 分别代表编码00、01、10和11，那么爱丽丝和鲍勃之间通过1个粒子的交换，完成了2比特经典信息的

18、传输，这就是量子密集编码。量子密集编码是量子信息的研究热点之一，例如向高维、多方的方向发展30，向对称的方向的发展31，并且在核磁共振和光学量子体系进行了实验演示32-35。量子密钥分配自从班内特和布拉萨德在1984年提出第一个量子密码协议（BB84协议）4以来，量子密码理论研究得到了很大发展，许多的量子密码协议被提出。与传统密码学不同，量子密钥分配（Quantum Key Distribution ，QKD ）是密码学与量子力学结合的产物，它以量子态为信息载体，利用量子力学的基本原理来保护信息并通过量子信道传送，在彼此之间建立共享密钥。这种方法也称为量子密码通信。其安全性是由量子力学中的测不

19、准原理和非克隆定理来保证的。量子密钥分配不是用于传输密文，而是用于建立、传输密码本，即在保密通信双方分配密钥。到目前，可以说量子密钥分配是量子通信技术里最成熟的分支之一，这不仅体现在理论上提出了数十种密钥分配方案，而且在实验上也取得了突出的进展。在量子密钥分配中，不同的信号源将依赖不同的量子特性和量子原理来保证通信的安全性。因此，我们可以根据信号源的不同将量子密钥分配大体上分为三类：（1）基于单粒子系统量子特性的量子密钥分配方案，如BB84协议4、B92协议36和HKH98协议37等；（2）基于纠缠粒子系统的量子关联性和非定域性等量子特性的量子密钥分配方案，例如Ekert91协议38、BBM9

20、2协议39图2量子纠缠转移原理图图3 量子密集编码原理图。Communications of CCF 2008/7 1和Long-Liu2002协议40等；（3）基于纠缠粒子与单粒子混合系统的量子密钥分配方案，例如卡贝略. 霍尔夫（C a b e l l o-H o l e v o ）协议41和薛-李-郭（Xue-Li-Guo ，音译）2002协议42等。我们说量子密钥分配是安全的，并不是说窃听者不能窃听量子信道，而是通信双方通过对一定的抽样数据出错率e 的分析，能够判断是否有人窃听量子信道。从而判断在双方传输的量子比特是否可用。量子直接安全通信量子直接安全通信利用量子态来直接传输机密信息本身

21、40,43,44。量子直接安全通信能够大大提高量子通信的效率。随着量子技术应用的发展，量子直接安全通信会有越来越多的应用。量子密钥分发是在两个相距很远的用户之间建立共同的密钥。量子密钥分配的安全性要求通信的双方能够探测到窃听者，并且在误码率较小的时候通过纠错和秘密放大得到任意程度的安全密钥。得到了共同的密钥之后，一方通过某种经典加密手段，如一次一密方法，将信息（plaintext ）加密得到密文（ciphertext ），再通过经典通道将密文发送给另外一方。在量子直接安全通信中，在量子信道中直接传输信息，不需要将信息加密成为密文通过经典信道传输。因而，量子直接安全通信具有比量子密钥分配更加严格

22、的要求。通信双方除了能够探测到窃听者之外，还需要保证在发现窃听者之前所传递的信息不泄露。研究表明，要达到这样的安全性，必须在通信的时候使用块传输，即将一定数量的量子信息的载体成批地由一方传递到另外一方。近年来量子直接安全通信成为大家关注的研究热点，众多的量子直接安全通信理论方案被提出，既有使用纠缠量子态的，也有使用单光子态的。但是，量子态在实际量子信道的传输过程中必然会受到噪声的影响，这是任何量子通信都必将面临的问题。在量子密码通信中，因噪声的影响而可能泄漏的信息可以通过经典的秘密放大处理方法来降低。这种处理虽然导致密码传输比特率降低，但可以把泄漏的信息减少到任意小的程度。但是在量子安全直接通

23、信中这一个问题并不好解决，特别是基于单光子双向运动的物理模型。为了降低噪声的影响，需要对量子态做纯化处理。因此量子直接通信的安全性分析，可允许的误码率等是量子直接安全通信的关键。由于在量子直接安全通信中需要块传输，因此要求通信的一方具有量子态存储设备，而这一设备也是长距离量子通信和量子计算所需要的。这也是量子直接安全通信技术的关键。量子直接安全通信的实验研究和实用化是另一个重要的关键。量子算法量子计算机是服从量子力学规律的新型计算模型。通常需要用量子计算机模拟量子物理系统随时间的演化从而完成某一计算任务，这就需要给出具体的算法，即给出量子逻辑门序列来实现这个幺正操作。量子算法的目的是将一系列量

24、子逻辑门组织起来，实现对量子计算机状态的幺正操作，使量子计算机按照设计者的意愿随时间演化，达到预期的输出状态。量子并行性量子并行计算贯穿于量子算法之中，使得量子算法与经典算法相比，以更高的效率得到所期望的计算结果。量子并行性是指：如果将量子计算过程中实施某个函数 的幺正操作 作用在量子寄存器的输入迭加态上，则它将对每个基矢量进行作用后并将所有结果进行线性迭加，产生一个输出迭加态。因此，只需要应用一次 就可以同时计算出不同 值对应的函数 。1 由爱因斯坦波道尔斯基罗森（EinsteinPodolskyRosen）首先提出的概念，即总自旋为零 的粒子对。专题报道Cover Features Com

25、munications of CCF 2008/720 （13）当前量子算法的基本思想主要有两种：（1）对振幅的放大，即放大所需要的输出值的振幅。其基本思想是对量子态进行幺正变换，从而放大所需要的输出值，使得在测量的时候可以较大的概率得到该结果，例如，格洛弗（G r o v e r ）算子搜索算法及其推广算法45-47。（2）相位估计算法。这类算法通过对相位进行操作，从而得到所需要的结果，例如，肖尔大数质因子分解算法3。目前，根据量子算法对计算加速的效果，将已发现的量子算法分为三类48：“相对黑盒”指数加速的量子算法、指数加速的量子算法和非指数加速的量子算法。“相对黑盒”指数加速的量子算法在计

26、算机科学中，量子黑盒是执行某种计算任务的幺正操作。它可以作为量子计算的一段子程序，当量子黑盒的输入为量子迭加态时，与输入为经典态时相比，它可以实现计算的指数加速，对应的算法称为“相对黑盒”指数加速的量子算法。“相对黑盒”指数加速的量子算法的一个典型代表是杜奇-约萨（Deutsch-Jozsa ）问题及其算法49。如果允许杜奇约萨问题有边界误差（bound error）的解，经典计算机也可以有多项式的解，此时量子算法并没有什么优势。而在要求精确解的时候，杜奇-约萨问题的经典解没有多项式算法，量子算法具有指数加速的优势。杜奇-约萨问题是指：假设有一个n 位输入的量子黑盒，它的计算函数为 如果对所有

27、的输入 都是0或者1，称 是常数函数；如果对一半的输 入 ， ，对另一半的输入 则 称 是对称函数。杜奇约萨问题希望判定 是否为常数函数。如果利用经典态作为输入，共需 次计算来解决此问题。而利用量子迭加态作为输入，则只需要运行一次量子黑盒，就可以得到肯定的结果，过程如下：首先，利用1个辅助量子位，将 量子位的沃尔什哈德曼变换 作用在 ，得到输入态 然后进行 操作，得到再对前个输入量子位进行沃什-哈德曼操作，得到此时测量前 个量子位，如果测得时，说明 是常数函数；如果测得的状态不是 态时，说明 是对称函数。可见，相对于经典算法的次计算，杜奇-约萨量子算法只需一次黑盒计算就解决问题，实现了“相对黑

28、盒”的指数加速。肖尔大数质因子分解算法肖尔大数质因子分解算法3是一个典型的实现指数加速的量子算法。根据经典计算复杂性理论，分解大数质因子属于NP 2困难问题（但不是NPC 问题），而在量子计算机上利用肖尔大数质因子分解算法，可以在多项式时间解决这一问题，实现了计算的指数加速。找两个质数的乘积是一个很容易进行的运算。可是如果反过来，把一个乘积分解成两个质数的乘积，则相对于前者是一个麻烦得多的问题。一般地，一个大数N ，我们要将之分解，约需要计算步。(14(15（16）（17） 2 可以在多项式时间内验证一个解是否正确的问题称为NP问题。无法做到在多项式时间验证解的正确性的问题是NP困难问题。3

29、RSA是一个Internet加密与鉴权系统，它使用Ron Rivest、Adi Shamir及Leonard Adleman在1977年开发的一个算法。Communications of CCF 2008/7 21计算的步数与大数的位数成指数增长关系。1个600位的大数，使用目前最快的计算机，居然要用比整个宇宙的年龄还要长的时间才能分解出。目前广泛使用的RSA 3密钥系统就是基于假定不存在快的大数分解算法，从而使得RSA 密钥系统受到巨大挑战，同时也推动了人类对量子计算机的研究。在量子计算机上实现肖尔的大数分解算法，分解一个L位的大数，计算步数下降为 。假定要分解的大数为N ，肖尔算法的过程如

30、下：（1）随机选取 （ 并与N 互质），用量子算法求函数 的周期T 。（2）若T 为奇数，则返回1，重新选取；若T 为偶数，则取。（3）求得y 后，用欧几里德辗转相除法求得 和 分别与N 的最大公约数，则可以找到质因子。以上算法的关键在于求得函数的周期T ，这是量子计算机体现其优越性的地方。这一算法在经典计算机上执行时，需要的物理资源和计算步骤是随着位数指数增加的，而在量子计算机执行肖子算法创是多项式增加的。格洛弗量子搜索算法1996年，格洛弗提出了非结构化数据库的量子搜索算法，又称为格洛弗算法45。该算法的时间复杂度为 ，与经典算法的平均复杂度为O(N相比，格洛弗量子搜索算法实现了计算的平方

31、加速。格洛弗量子搜索算法要解决的问题是：在 个量子比特的非结构化数据库中， 有个量子基态 ，其中只有一个目标态 满足某一量子黑盒的查询函数 ，其它量子态都使得查询函数 。量子搜索算法是以尽可能大的概率将目标态 找到。格洛弗搜索算法包括以下步骤：（1）数据库初始化。首先， 量子比特的寄存器处在 态上，实施 量子比特的沃尔什哈德曼操作 ，此时数据库被初始化为一个平均迭加态（2）进行格洛弗搜索迭代 次，然后对 量子比特状态进行测量，以一定概率得到目标量子态 。格洛弗搜索迭代包括四个子步骤：步骤1：反转目标态 的相位，而其它态保持不变。步骤2：进行 量子比特的沃尔什哈德曼变换， 。步骤3：反转除 态之

32、外的所有基态的相位，而保持 态不变。步骤4：进行 量子比特的沃尔什哈德曼变换， 。步骤2步骤4的过程，相当于对平均量子态进行了一个反转，将这个操作称为扩散操作，记为D 。可以从一种更直观的几何可视化角度去理解格洛弗量子搜索算法，即在以 态和 态为基矢的二维希尔伯特空间中，格洛弗迭代操作G 可以表示为单个格洛弗搜索迭代G 的整体作用可以看作是在二维平面内沿逆时针方向旋转2 角度。因此，在连续j 次搜索迭代之后，数据库的量子态变为 如果要以尽可能大的概率搜索到目标态，则需要尽可能满足条件 ，因此最佳的搜索迭代步 其中 INT 表示对实数取整。对于某个特定的数据库， 不一定恰好等于，因此格（19 ）

33、（20 ）（21 ）（18 ）专题报道Cover FeaturesCommunications of CCF 2008/722洛弗搜索算法的最大成功率不一定为100%，它是一个随迭代步数j 变换的周期性函数。相位匹配与精确量子搜索算法虽然格洛弗算法的搜索成功率很大，但是其有缺陷。它的搜索成功率只是在只有4个数据的时候才是100%。即使在数据库很大的时候，如果标记态的数量比较大，格洛弗算法的成功率也会很低。例如，如果标记态的数目是数据库的一半的时候，标准的格洛弗算法就失败了。有一个流行的错误，格洛弗等人认为，如果将格洛弗算法中的2个相位取反换成任意角度的转动，搜索算法依然可以成功。后来证明，格洛

34、弗的这个判断是错误的。在一般的相位转动下，2个转动的角度，也就是2个相位必须满足相位匹配条件51-53。相位匹配条件是量子搜索算法成功的必要条件。而格洛弗算法的成功率不是100%的主要原因是用1个固定的180度转动对任意的数据库进行搜索，这种粗糙的相位转动选择导致了搜索成功率的降低。2001年构建的改进格洛弗算法，可以精确地给出标记态47。对于含有1个目标态的N 条目非结构化量子数据库，该算法经过数次搜索迭代，可以以100%的成功率将目标态搜索到。其算法过程如下。对于N 个基态的平均迭加态的数据库，其相位轻动角是：特别指出，这里的角度不是唯一的。这里有个最小的搜索次数J op ，比这个数大的任

35、意整数也都可以。最近与格洛弗算法有关的一个发展是定点量子搜索算法54,55。定点量子搜索算法中随着搜索步骤的增加，体系的状态越来越接近目标态，不会像格洛弗算法那样是搜索步骤的周期函数。但是这个算法所需要的步骤是O(3n ，比经典搜索算法需要的步骤还多。但是这个算法在空间资源上比经典算法节约。结语本文介绍了量子信息的理论基础、常见的量子通信和主要的量子算法。量子信息是一个迅速发展的领域，还有许多重要的研究内容，如量子计算机的模型理论56，量子态识别和量子操作的识别57,58、消相干控制59、量子纠错60和量子编程语言61等。此外，将量子力学中的波粒二像性引入到量子计算中，有可能提高量子计算的能力

36、，建立经典算法和量子算法之间的联系62。量子信息学是量子力学和信息科学结合产生的交叉学科。今后，随着更多方面研究的结合，还会有新的研究内容出现。龙桂鲁 清华大学物理系、清华信息科学与技术国家实验室（筹）教授，博士生导师。现就职于清华大学原子分子与纳米科学重点实验室。1987年在清华大学获得博士学位。主要研究兴趣：量子计算、量子通信和核磁共振量子计算等。1 P. Benioff, The computer as a physical system: a micro-scopic quantum mechanical Hamiltonian model of com-puters as repre

37、sented by Turing machines. J. Stat. Phys.,1980, 22(5:563-5912 R. P. Feymnman. Simulating physics with computers.Int. Journal of Theor. Phys., 1982, 21(6:467-4883 P. Shor. Algorithms for quantum computaion: discretelogarithm factoring. Proc. 35th Annual Symposium oncomputer Science, IEEE, 1992:181-18

38、24 C. H. Bennett and G. Brassard. Quantum cryptogra-phy: public key distribution and coin tossing. Proc. IEEE 参考文献（22）Communications of CCF 2008/723 Int. Conf. on Computers, Systems and Signal Processing,Bangalore, India (IEEE, New York, 1984:175-1795 C. H. Bennett, G. Brassard, C. Crepeau, et al. T

39、ele-porting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels. Phys. Rev. Lett.,1993, 70(13:18956 李承祖, 黄明球, 陈平行等. 量子通信和量子计算. 长沙: 国防科技大学出版社, 20017 张永德. 量子信息物理原理. 北京: 科学出版社,20068 曾谨言, 裴寿镛主编. 量子力学新进展. 第一辑，北京: 北京大学出版社，20009 曾谨言, 裴寿镛, 龙桂鲁主编. 量子力学新进展. 第二辑, 北京:北京大学出版社, 200110

40、 曾谨言, 龙桂鲁, 裴寿镛主编. 量子力学新进展. 第三辑, 北京:清华大学出版社, 200311 龙桂鲁, 曾谨言, 裴寿镛主编. 量子力学新进展. 第四辑, 北京:清华大学出版社, 200612 喀兴林. 高等量子力学. 北京:高等教育出版社, 200113 曾谨言. 量子力学, 卷I, 卷II. 第三版, 北京:科学出版社, 200014 R. Shankar. Principles of Quantum Mechanics. 2nd edi-tion,Plenum Press, New York, 198015 Gui Lu Long, Yi-Fan Zhou, Jia-Qi Jin

41、, Yang Sun,Hai-Woong Lee. Density Matrix in QuantumMechanicsand Distinctness of Ensembles Having the Same Com-pressed Density Matrix, Foundations of Physics, 2006,36(4:1217-124316 W. K. Wooters, W. H. Zurek. A single quantum cannotbe cloned. Nature, 1982, 299:802-80317 T. Gao, F L yan, Z X Wang, Y Q

42、 Li. Quantum proba-bilistical cloning and computation, Front. Comput. Sci.China, 2008, 2(2:179-18918 D. Bohm. Quantum theory. Prentice Hall, EnglewoodCliffs, 199519 D. M. Greenberger, M. A. Horne, Z. Zerlinger. Going be-yond Bell's theorem. in Bell's theorem, quantum theory,and conceptions o

43、f the universe, Dordrecht: Kluwer, M.Kafatos (Ed., 198920 J. Bell. On the Einstein-Podolsky-Rosen paradox.Physics, 1964, 1:195-20021 J. F. Clauser, M. A. Horne, A. Shimony, et al. Proposed experimental to test local-hidden-variable theories. Phys.Rev. Lett., 1969, 23:880-88422 A. Aspect, Dalibard, G

44、. Roger. Experimental test of Bell's inequalities using for continuous variable systems.Phys. Rev. Lett., 1982, 49:1804-180723 X. H. Gao, A. Sergio, K. Chen, S. M. Fei and X. Q.Li-Jost. Entanglement of formation and concurrence for mixed states, Front. Comput. Sci. China, 2008, 2(2:114-12924 Y.

45、C. Wu and G. C. Guo. High-dimension Bell inequalities. Front. Comput. Sci. China, 2008, 2(2:190-19225 Z. Zhao et al. Experimental demonstration of vephotonentanglement and open-destination teleportation. Nature, 2004, 430:54-5826 J. T. Barreiro et al. Generation of hyperentangled photonpairs. Phys.

46、Rev. Lett., 2005, 95:26050127 X. H. Li and F. G. Deng. Controlled teleportation. Front.Comput. Sci. China, 2008, 2(2:147-16028 M. Zukowski, A. Zeilinger, A. Horne, et al. Event-ready-detectors Bell experiment via entanglement swapping.Phys. Rev. Lett., 1993, 70(26:4287-429029 C. H. Bennett and S. J.

47、 Wiesner. Communication viaone-and two-particle operators on Einstein-Podolsky- Rosen states. Phys. Rev. Lett., 1992, 69:2881-288430 X. S. Liu, G. L. Long, D. M. Tong and Feng Li. General scheme for superdense coding between multi- parties. Phys. Rev. A, 2002, 65:02230431 A. Crudka, A. Wojcik A. Sym

48、metric scheme for super-dense coding between multipaties. Phys Rev A, 2002, 66(1: 01430132 D. X. Wei, X. D. Yang, J. Luo, X. P. Sun, X. Z. Zeng and M. L. Liu. NMR experimental implementation of three-parties quantum superdense coding. Chinese Science Bul-letin, 2004, 49(5:423-42633 X. Li et al. Quan

49、tum dense coding exploiting a bright Einstein-Podolsky-Rosen beam. Phys. Rev. Lett., 2008, 88:04790434 X. Fang et al. Experimental implementation of dense coding using NMR. Phys. Rev. A, 2000, 61:02230735 J. Barreiro et al. Beating the channel capacity limit for linear photonic superdense coding. Na

50、ture Physics, 2008,4:282-28636 C. H. Bennett. Quantum cryptography using any two nonorthogonal states. Phys. Rev. Lett., 1992, 68:3121- 312437 W. Y. Hwang, I. G. Koh, Y. D. Han. Quantum cryptography without public announcement of bases. Phys. Lett.A, 1998, 244:489-49438 A. K. Ekert. Quantum cryptogr

51、aphy based on Bell's theorem. Phys. Rev. Lett., 1991, 67:661-66339 C. H. Bennett, G. Brassard, N. D. Mermin. Quantum cryptography without Bell's theorem. Phys. Rev.专题报道Cover Features 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 Lett.,1992, 68:557-669 G. L. Long, X. S.

52、 Liu. Theoretically e±cient high-capacity quantum-key-distribution schemes. Phys. Rev.A, 2002, 65:032302 A. Cabello. Quantum key distribution in the Holevo limit. Phys. Rev. Lett., 2000, 85:5635-5638 P. Xue, C. F. Li, G. C. Guo. Quantum key distributionvia quantum encryption. Phys. Rev. A, 2002

53、, 65:022317 K. BostrÄom and T. Felbinger. Deterministic Secure Direct Communication Using Entanglement. Phys. Rev. Lett., 2002, 89:187902 F. G. Deng, G. L. Long and X. S. Liu. Two-step quantum direct communication protocol using the Einstein- Podolsky- Rosen pair block. Phys. Rev. A, 2003,68(4:

54、042317; Secure direct communication with a quantum one-time pad. Phys. Rev. A, 2004, 69(5:052319;Quantum secure direct communication network with Einstein-Podolsky-Rosen pairs. Phys. Lett. A, 2006,359(5:359-365 L. Grover. A fast quantum mechanical algorithm fordatabase search. Proc. 28th Annual ACM

55、Symposium on Theory of Computing, ACM, New York, 1996, pp.212-219 M. Boyer, G. Brassard, P. Hoyer, A. Tapp. Strengthand weakness of quantum computation. Fortschr. Phys., 1998, 46:493-505 G. L. Long, Grover algorithm with zero failure rate, Phys.Rev. A, 2001, 64:022307 J. Preskill. Quantum information and quantum computation. California Institute of Technology, 1998 D. Deutsch, R. Jozsa. Rapid solution of problems by quant