量子计算机理论概述

陈灵生

浙江广电集团，浙江 杭州 310005

1 经典计算机与Moore定律

所谓经典计算机就是指目前在广泛使用的电子计算机，之所以称为经典计算机，是因为现在有了量子计算机的概念。毫无疑问，经典计算机在广泛的使用领域取得了巨大的成功，很难想象那个行业能离得开计算机。

电子计算机的发展依赖于大规模集成电路技术的发展。早在1965年，Moore就提出大胆预言（后来该预言被称为Moore定律）:在未来十年内集成到一个芯片内的晶体管数目每一年（后来修正为每18个月）翻一番。该定律居然神奇地有效了40多年。虽然Intel等公司还在极力维持Moore定律的有效性[1]，但是这种趋势不可能无限地延续下去，因为随着集成度的不断加大，设计一个存储单元的原子数目将达到几个原子的数量级。一旦只涉及几个原子和电子，经典物理学规律将不再有效，必须要用量子物理学来处理，因此量子计算机的出现可以说是科学技术发展的必然结果。

2 量子计算机概念的提出

计算机是执行计算任务的机器，它的本质是一个物理系统，计算过程本质上是个物理过程，量子计算机在本质上就是一个量子力学系统[2]。

美国物理学家Feynman在1982年提出量子计算的概念。在更早一点的时候，Benioff在“作为物理系统的计算机”一文中证明了一个重要的定理[3]，从该定理得出的结论是，通过量子态的幺正演化可以实现经典图灵机得计算功能。因此量子计算机所理论上是可行的，而且它的性能至少不低于经典计算机。

由于量子态的幺正演化只存在于理想的孤立系统中，但在实际中，量子系统不可避免地和周围环境发生相互作用，表现为量子计算中的噪声干扰，导致量子计算很容易出错。同时人们也不清楚，量子计算是否优于经典计算，所以量子计算一开始只停留在理论上可行的阶段。

3 量子计算

随着一些优秀的量子算法被人们陆续发现，量子计算机逐渐成为研究的热点。特别是美国计算机专家Shor于1994年提出的大数的素因子分解算法特别引人注目。大数素因子分解算法之所以重要，是因为大数的素因子分解是经典计算机的难解问题，而这正是目前广泛使用的RSA公开密钥加密系统得以安全的先决条件的。也就是说大数的因子分解是经典计算理论中的NP难题，然而Shor的量子算法把它转化为P类问题。这给量子计算机研究注入了新的活力，引发了量子计算机研究的热潮[4]。

量子计算机之所以有可能取得远超经典计算机的计算性能，是和量子计算本身的特点分不开的。经典计算处理的基本单元是比特（bit，即二进制的0或1），与之对应，量子计算处理的单元是量子比特（quantum bit，qubit）。量子比特通常用Dirac标记写成和的形式，也称为计算基矢，它们相互正交。经典比特要么处于0，要么处于1；但量子比特则不同，它不仅可以是或，而且可以是这两种态的任意线性组合

其中α和β是复系数，满足归一化条件

这就是量子态的叠加原理。

量子态叠加原理是量子计算机有可能进行大规模并行计算的物理基础。单个量子比特可以处于叠加态，多个量子比特组成的量子系统也可以处于叠加态。而且量子系统的态空间的维数随着量子比特数的增加成指数上升。比如两个量子比特组成的量子系统，它的基矢有，该系统可以处在这四个态的叠加态中。一般地，n个量子比特系统的态空间是2n维Hilbert空间，可以用它的2n各基矢（其中i是个n位二进制数串），制备出一般态:

如果量子计算机对2n这个一般态进行计算，就相当于对个基矢态同时进行计算，这就是量子计算的并行性。

与经典计算机中的逻辑门相对应，量子信息处理的基本操作元件是量子逻辑门。从数学的观点看，量子逻辑门就是幺正矩阵或是幺正矩阵的组合，对量子态实施幺正变换就实现了对量子态所表达的数据的计算。

如果对任意维的Hilbert空间态（即量子态）的幺正变换，都可以通过一个逻辑门的组合来实现，那么这个逻辑门就是一个通用逻辑门。对于量子计算的通用逻辑门组，就是所谓的Deutsch门。Deutsch证明任意维Hilbert空间的幺正变换的量子计算网络都可以用这个门的组合构造出来。这样从理论上来说，可以像用经典逻辑门构建经典计算机一样，用量子逻辑门构建量子计算机。

量子计算中还可利用的一个资源就是所谓的量子纠缠。比如双量子比特系统处于态

这就是一个纠缠态。在这个特殊的态中，复合系统（双量子比特）的态是完全确定的，但其中每个子系统（单个量子比特）的态是不确定的。同时两个子系统之间存在着不可分割的联系，表现为对其中任何一个子系统的测量会引起另一个子系统态的瞬时改变，不管两个子系统相距有多远。目前，人们可以利用量子纠缠实现隐形传态，即利用两地共享的量子纠缠对，把其中一地的未知量子态传输到另一地，却不需要传送这个量子比特本身。还可以利用量子纠缠实现超密编码，即用一个量子比特位传送两个比特的经典信息。

4 量子计算机的实现与挑战

经典计算机的实现方法比较统一，都是以大规模集成电路为基础，采用Von Neumann的体系结构。然而，目前提出的量子计算机的实现方法则五花八门，不同学科的研究人员都从自己的研究领域出发，提出不同的实现方法。从理论上说，只要满足量子计算所需的条件，任何实现方法都是可行的。目前已经提出的量子计算机的物理实现方案有:核磁共振量子计算机、离子阱量子计算机、中性原子量子计算机、光量子量子计算机、超导量子计算机等[2]。

虽然量子计算机和量子算法已经有了基本框架，但最终要实现具有实用价值的量子计算机，还存在着许多需要解决的问题。对于这么多种量子计算机的实现方案，哪一种最具实现价值，还没有定论。

同时，量子计算机的性能到底能比经典计算机优越多少，也不是十分清楚。虽然由于量子态的叠加性，量子计算可以实现大规模的并行运算，但一旦要让计算结果输出，必须进行测量，一旦进行测量，叠加态就会坍缩到被测物理量的一个本征态。因此要通过测量把并行计算的所有结果都读出来是不可能的。如何利用量子计算中的并行特性，需要巧妙的算法设计。因此到目前为止，除了Shor大数素因子分解算法、Grover数据库搜索算法等少数几个优秀的量子算法之外，再寻找优秀量子算法的难道很大。量子计算机要真正进入实用还有很长的路要走。

[1]张邦维.Moore定律还会继续有效吗[J].自然杂志，2004，26(1).

[2]李承祖，陈平形，梁林梅，戴宏毅.量子计算机研究(上):原理和物理实现[M].科学出版社，2011.

[3]P.Beniof f.The computer as a physical system:A microscopic quantum mechanical Hami ltonian model of computers as represented by Turing machines.Journal of Statistical Physics, 1980，22.

[4]赵生妹，郑宝玉.量子信息处理技术[M].北京邮电大学出版社，2010.