量子计算机发展带来的思考.doc

量子计算机发展带来的思考 ——科学技术的创新与发展 一、引言 自从20世纪30年代以来，图灵机、计算这些重要的概念在科学的天空中就一直闪烁着无限的光彩。尤其是近年来量子计算机、生物计算机、DNA计算等领域的创新工作引起了所谓的图灵机就是指一个抽象的机器，它有一条无限长的纸带，纸带分成了一个一个的小方格，每个方格有不同的颜色。有一个机器头在纸带上移来移去。机器头有一组内部状态，还有一些固定的程序。在每个时刻，机器头都要从当前纸带上读入一个方格信息，然后结合自己的内部状态查找程序表，根据程序输出信息到纸带方格上，并转换自己的内部状态，然后进行移动。 它工作的时候是这样的：从读写头在纸带上读出一个方格的信息，并且根据它当前的内部状态开始对程序进行查表，然后得出一个输出动作，也就是是否往纸带上写信息，还是移动读写头到下一个方格。程序也会告诉它下一时刻内部状态转移到哪一个。因此，图灵机只要根据每一时刻读写头读到的信息和当前的内部状态进行查表就可以确定它下一时刻的内部状态和输出动作了。 对图灵机的计算能力的估价目前一般以强Church-Turing论题为据:任何算法过程都可以用图灵机进行有效模拟。由于随机算法的引人Church-Turing强论题后来被修改为更强的论题:任何算法过程都可用概率图灵机进行有效模拟。在这个问题的启发下, Deutsch与其他一些物理学家认识到, 一个数学问题的计算复杂性的P与NP分类没有绝对性, 而在此之前人们一直认为这种分类不依赖具体使用的计算系统。正是这个认识, 使得量子计算的研究得到广泛关注。随后, Deutsch 提出是否可以用物理学定律推导出任何更强的Church-Turing论题的问题, Deutsch选用被认为是物理学最基本规律的量子力学理论进行考虑, 提出了通用量子计算机的概念。 1.3量子图灵机 正如经典计算机建立在通用图灵机基础之上，量子计算机亦可建立在量子图灵机基础上．量子图灵机可类比于经典计算机的概率运算．前面提到的通用图灵机的操作是完全确定性的，用q代表当前读写头的状态，s代表当前存储单元内容，d取值为L，R，N分别代表读写头左移、右移或不动，则在确定性算法中，当q，s给定时，下一步的状态q，,s，及读写头的运动d完全确定．我们也可以考虑概率算法，即当q,s给定时，图灵机以一定的概率δ(q,s,q，,s，,d)变换到状态q，,s，及实行运动d．概率函数δ(q,s,q，,s，,d)为取值[O，1]的实数，它完全决定了概率图灵机的性质．经典计算机理论证明，对解决某些问题，概率算法比确定性算法更为有效．量子图灵机非常类似于上面描述的经典概率图灵机，现在q,s,q, ,s, 相应地变成了量子态，而概率函数δ(q,s,q，,s，,d)则变成了取值为复数的概率振幅函数δ(q,s,q，,s，,d)，量子图灵机的性质由概率振幅函数确定正因为现在的运算结果不再按概率叠加，而是按概率振幅叠加，所以量子相干性在量子图灵机中起本质性的作用，这是实现量子并行计算的关键．量子计算机可以等效为一个量子图灵机，但量子图灵机是一个抽象的数学模型，如何在物理上构造出量子计算机呢? 2、物理学基础（量子力学） 从物理观点看, 计算机是一个物理系统, 计算过程是一个物理过程。量子计算机是一个量子力学系统, 量子计算过程就是这个量子力学系统内量子态的演化过程。量子力学中与量子计算关系最为密切的两个特性是叠加态与纠缠态。由于量子态具有量子叠加和量子纠缠的性质, 使得量子计算有许多不同于经典计算机的新特点。 信息一旦量子化，描述“原子水平上的物质结构及其属性”的量子力学特性便成为量子信息的物理基础。此时由于信息载体――量子的微观特征，量子化的信息也变得多姿多彩。这些微观特征主要表现在： 1）量子态相干性：微观系统中量子间相互干涉的现象成为量子信息诸多不可思议特性的重要物理基础； 2）量子态纠缠性：N（大于1）个量子在特定的（温度、磁场）环境下可以处于较稳定的量子纠缠状态，对其中某个子系统的局域操作会影响到其余子系统的状态； 3）量子态叠加性：量子状态可以叠加，因此量子信息也可以叠加，所以可以同时输入或操作 N个量子比特的叠加态； 4）量子不可克隆定理：量子力学的线性特性确保对任意量子态无法实现精确的复制。量子不可克隆定理和测不准原理构成量子密码技术的物理基础。 利用量子信息实现通信的过程是使每一个微观粒子，通过自身的物理特性携带经典信息0和1的叠加信号后实现的数据传输的技术。事实上，经典计算机也是量子力学的产物，它的器件也利用了诸如量子隧道现象等量子效应。但仅仅应用量子器件的信息技术，并不等于现在所说的量子信息。目前的量子信息主要是基于量子力学的相干特征，重构信息密码、信