量子计算机Word文档格式.docx
《量子计算机Word文档格式.docx》由会员分享，可在线阅读，更多相关《量子计算机Word文档格式.docx（20页珍藏版）》请在冰点文库上搜索。
这种现象看起来和人的直觉不符，因为在人类的日常生活中发生的现象遵循的是传统物理规律，而不是量子力学的规律，量子规律只统治原子级的世界。
下面的图a可以帮助我们更
好的理解这个不寻常的概念。
从某光源发射的光子沿某条路径射向一个一面涂有银的镜子。
该镜子使光束分离，其中的一半垂直射向接收器A，
另一半则射向接收器B。
但是，一个光子作为光的最小单位并不能被分离，所以光子被接收器A或B检测到的机率相
等。
如果凭直觉我们可能认为光子离开镜子的方向是随机的，或者沿垂直方向，或者沿平行方向。
但是，量子动力学告诉我们，光子实际上是沿平行和垂直两个方向同时传播的。
在一个类似图a的试验中，光子被射向半面镀银的镜子，通过接收器显示岀的信号（如果一个接收器有信号，那么其它就没有信号）证实了光子是不可分的。
根据这个现象，人们可能认为光子的传播路径或者是垂直，或者是平行，
并且随机的在两种路径之中选择一个。
但是，量子动力学认为光子的传播实际上是同时沿两个方向进行的，而不是像试验a中所示选择其中一种。
这种现象，被叫做单粒子干涉，对这种现象在如图b所示的试验中有更好的阐述。
在这个试验中，光子首先撞击一个半面镀银的镜子，然后是一个全镀银的镜子，在最终到达接收器之前是另一个半面镀银的镜子，而且是半面镀银的镜子引起了光子沿一条或另一条路径传播的可能性。
一旦光子在第一次光柱分离之后沿两种路径之中的任何一条撞击镜子，那么这种现象就和图a中类似，所以人们就会推测光子将等机率的到达接
收器A或B。
但是，试验b结果显示这种现象实际上使得接收器A的接收率是100%，而接收器B则接收率为0%!
那么这是怎么回事呢？
图b描述的这个有趣的试验证明了单粒子干涉现象。
在这种情况下，试验显示出光子总是到达接收器A,而永远
不会到达接收器B!
如果一个单光子沿垂直方向传播并撞击镜子，通过和图a中的试验相类比，光子被接收器A和B
接受的机率应该是相等的。
对沿平行方向传播的光子来说也是同样的。
但是，试验的结果却有如此巨大的反差。
唯一可以得到的结论就是光子在沿两条路径同时传播，并在两条路径的交叉点产生干涉，因此破坏了光子到达接收器B的
可能性。
这就是已知的量子干涉，干涉的原因是可能的光子态或路径的重叠。
所以，尽管只发射了一个光子，但是好像有另一个和它相同的光子存在，并且这个光子沿一条不存在的路径传播，只有当这个光子和原光子路径相交因此发生干涉时才能够被发现。
例如，如果两条路径中的一条被一个吸收屏阻挡，那么接收器B才开始像在试验a中一样显
示出信号。
量子的这个独特的性质使得当前在量子计算机中的研究不仅是今日计算机思想的延续，而且也是这个思想的一个全新分支。
是量子计算机利用这些特殊的性质赋予了计算设备潜在的难以置信的威力。
但是，令人惊奇的是，量子计算机的外观并不同于我们现在所使用的计算机，它看起来可能更象放在计算机旁边的咖啡杯。
1.2量子计算机中的基本概念
比特和昆比特
传统计算机的电路是建立在一个用固体设备代表二进制数字位（bit，比特）0或者1的基础上的。
在大部分的计算机中，晶体管关闭（输出电压为0V）代表了二进制数0，而晶体管打开（输出电压为5V）代表了二进制数1。
而量子计算机则操纵着量子位或者说昆比特。
一个昆比特说明一个单粒子能存在于0或1的状态，或者同时存在
于0和1的状态，这说明昆比特比比特可以表示的状态多。
而且量子重叠态允许同时进行许多运算，这就是已知的量子平行，可以大大减少计算时间。
可能昆比特最简单的一个例子就是光子可沿两条路径传播。
一条路径可以代表0，另一条路径可以代表1。
当光束射向分光机时光子能存在于两条路径的重叠态。
分光机很像一面普通的镜子，但是，反射层被做的很薄，并不是所有的光都被反射，一些光也可以通过它传播。
当单光子遇到分光机时，光子出现于反射路径和向前传播路径的重叠态。
光子在两条路径的重叠态时即可同时代表0和1。
许多量子系统能用做昆比特位使用
量子平行
一个一位（就是同时只能存储一位数字）的存储器能储存数字0和1。
同样的，一个两位（就是同时只能存储两位位数字）的存储器可以存储二进制数00，01，10和11（把这些二进制数字翻译成十进制就是0，1，2和3）。
但是，这些存储器的共同特点和局限就是，在一个特定的时刻只能储存一个数字（如二进制数10）。
相对而言，一个量子重叠态运行一个昆比特位同时储存0和1。
两个昆比特位能同时储存所有的4个二进制数。
三个昆比特位能储存8个二进制数000，001，010，011，100，101，110和111。
下表表明300个昆比特位能同时储存多于1090个数字。
这甚至多于我们这个可见宇宙中的原子数。
这表明了量子计算机的威力：
只用300个光子（或者300个离子等等）就能储存比这个宇宙中的原子数还多的数字，而且对这些数字的计算可以同时进行。
量子纠结
这是量子计算中使用的另一个量子物理学特征。
当两个或多个粒子互相影响时，不可能独立描述任何一个量子的状态。
即使当它们随后即被分开很远的距离，它们的行为表现的好像它们仍然是一个整体。
因此我们称这些粒子是纠结的。
量子纠结这个性质允许了用于实现量子运算法则的量子数的大量减少。
总之，这是人类制造使用量子计算机中的一个大难题。
1.3量子计算机
一、量子计算机的概念及发展背景
1996年，美国《科学》周刊科技新闻中报道，量子计算机引起了计算机理论领域的革命。
同年，量子计算机的先驱之一，Bennett在英国《自然》杂志新闻与评论栏声称，量子计算机将进入工程时代。
目前，有关量子计算机的理论和实验正迅猛发展，那么，什么是量子计算机呢？
量子计算机，顾名思义，就是实现量子计算的机器。
要说清楚量子计算，首先看经典计算。
经典计算机从物理上可以被描述为对输入信号序列按一定算法进行变换的机器，其算法由计算机的内部逻辑电路来实现。
经典计算机具有如下特点：
（1）其输入态和输出态都是经典信号，用量子力学的语言来描述，也即是:
其输入态和输出态都是某一力学量的
本征态。
如输入二进制序列0110110,用量子记号，即10110110>
。
所有的输入态均相互正交。
对经典计算机不可能
输入如下叠加态：
C1|0110110>
+C2|1001001>
o
（2）经典计算机内部的每一步变换都将正交态演化为正交态，而一般的量子变换没有这个性质，因此，经典计算机中的变换（或计算）只对应一类特殊集。
相应于经典计算机的以上两个限制，量子计算机分别作了推广。
量子计算机的输入用一个具有有限能级的量子系
统来描述，如二能级系统（称为量子比特），量子计算机的变换（即量子计算）包括所有可能的么正变换。
因此量子计
算机的特点为[1]:
[1]量子计算机的输入态和输出态为一般的叠加态，其相互之间通常不正交；
[2]量子计算机中的变换为所有可能的么正变换。
得出输出态之后，量子计算机对输出态进行一定的测量，给出计
算结果。
由此可见，量子计算对经典计算作了极大的扩充，经典计算是一类特殊的量子计算。
量子计算最本质的特征为量子叠加性和相干性。
量子计算机对每一个叠加分量实现的变换相当于一种经典计算，所有这些经典计算同时完成，并按一定的概率振幅叠加起来，给出量子计算机的输出结果。
这种计算称为量子并行计算。
量子并行处理大大提高了量子计算机的效率，使得其可以完成经典计算机无法完成的工作，如一个很大的自然数的因子分解（后面将叙及）。
量子相干性在所有的量子超快速算法中得到了本质性的利用[2]o
量子计算机的概念源于对可逆计算机的研究，而研究可逆计算机是为了克服计算机中的能耗问题。
早在六七十年
代，人们就发现，能耗会导致计算机芯片的发热，影响芯片的集成度，从而限制了计算机的运行速度。
Landauer[3]
最早考虑了这个问题，他考察了能耗的来源，指出：
能耗产生于计算过程中的不可逆操作。
例如，对两比待的异或操作，因为只有一比特的输出，这一过程损失了一个自由度，因此是不可逆的，按照热力学，必然会产生一定的热量。
但这种不可逆性是不是不可避免的呢？
事实上，只要对异或门的操作如图1所示的简单改进，即保留一个无用的比特，该操作就变为可逆的。
因此物理原理并没有限制能耗的下限，消除能耗的关键是将不可逆操作改造为可逆操作（见图
1）o
图1不可逆异或门改进为可逆异或门
Bennett[4]后来更严格地考虑了此问题，并证明了，所有经典不可逆的计算机都可以改造为可逆计算机，而不影响其计算能力。
经典计算机实际上就是一个通用图灵机。
通用图灵机是计算机的抽象数学模型，它由两部分构成：
[1]具有无限多个存储单元的记录带，每个存储单元内容的变化是有限的，通常用二进制的“O和“1”来表示;
[2]一个具有有限内态的读写头，每步操作中读写头可以在记录带上左移或右移一格或不动。
图灵机在操作中，读写头根据其内态和当前存储单元的内容，按既定的规则，改变其内态和存储单元的内容。
并决定下一步读写头的移动方向。
上述图灵机的模型是不可逆的，例如，对如下图灵机操作“写存储单元-->
左移一格”，其逆就变成了“左移一格-->
写存储单元”，该逆操作不再是一个有效的图灵机操作。
但Bennett证明了一个基本结果：
对所有不可逆的通用图灵机，都可以找到一个对应的可逆图灵机，使得两者具有完全相同的计算能力和计算效率。
因为计算机中的每步操作都可以改造为可逆操作，在量子力学中，它就可以用一个么正变换来代表。
Benioff[5]
最早用量子力学来描述可逆计算机。
在量子可逆计算机中，比特的载体成为二能级的量子体系，体系处于|0>
和|1>
上，但不处于它们的叠加态。
量子可逆计算机的研究，其核心任务为，对应于具体的计算，寻找合适的哈密顿量来描述。
早期的量子可逆计算机，实际上是用量子力学语言表述出来的经典计算机，它没有利用量子力学的本质特性，如量子叠加性和相干性。
Feymann首先指出[6]，这些量子特性可能在未来的量子计算机中起本质作用，如用来模拟量
子系统。
Deutsch[7]找到一类问题，对该类问题，量子计算机存在多项式算法（多项式算法指运算完成的时间与输入二进制数据的长度，即比特的位数存在多项式关系），而经典计算机则需要指数算法。
但最具轰动性的结果却是Shor
给出的关于大数因子分解的量子多项式算法[8]（见第三节），因为此问题在经典公钥体系中有重要应用。
Shor的发
现掀起了研究量子计算机的热潮，从此后，量子计算机的发展日新月异。
、量子计算机的构造及实验方案
正如经典计算机建立在通用图灵机基础之上，量子计算机亦可建立在量子图灵机基础上。
量子图灵机可类比于经
典计算机的概率运算。
前一节提到的通用图灵机的操作是完全确定性的，用q代表当前读写头的状态，s代表当前存
储单元内容，d取值为L,R,N,分别代表读写头左移、右移或不动，则在确定性算法中，当q,s给定时，下一步的状态q'
，s'
及读写头的运动d完全确定。
我们也可以考虑概率算法，即当q,s给定时，图灵机以一定的概率（q,s,q,s”,d）变换到状态q'
s'
及实行运动d。
概率函数（q,s,q'
d）为取值[0,1]的实数，它完全决定了概率图灵机的性质。
经
典计算机理论证明，对解决某些问题，慨率算法比确定性算法更为有效。
量子图灵机非常类似于上面描述的经典概率图灵机，现在q,s,q'
相应地变成了量子态，而慨率函数（q,s,q'
d）则变成了取值为复数的概率振幅函数x（q,s,q'
d），量子图灵机的性质由概率振幅函数确定。
正因为现在的运算结果不再按概率叠加，而是按概率振幅叠加，所以量子相干性在量子图灵机中起本质性的作用，这是实现量子并行计算的关键。
量子计算机可以等效为一个量子图灵机。
但量子图灵机是一个抽象的数学模型，如何在物理上构造出量子计算机呢？
理论上已证明[9]，量子图灵机可以等价为一个量子逻辑电路，因此可以通过一些量子逻辑门的组合来构成量子计算机。
量子逻辑门按其输入比特的个数可分为单比特、二比特、及三比特逻辑门等。
因为量子逻辑门是可逆的，所以其输入和输出比特数相等。
量子逻辑门对输入比特进行一个确定的幺正变换，得到输出比特。
Deutsch[10]最早考虑了用量子逻辑门来为造计算机的问题，他发现，几乎所有的三比特量子逻辑门都是通用逻辑门。
通用逻辑门的含义是指，通过该逻辑门的级联，可以以任意精度逼近任何一个么正操作。
后来不少人发展了Deutsch的结果，最后Deutsch和Lloyd各自独立地证明[11]，几乎所有的二比特量子逻辑门都是通用的，这里“几乎”是指，二比特通用量子逻辑门的集合是所有二比特逻辑门的集合的一个稠密子集。
实验上通常用一些具体的量子逻辑门来构造计算机。
Barenco等人[12]证明，一个二比特的异或门和对一比特进行任意操作的门可构成一个通用量子门集。
相对来说，单比特逻辑门在实验上比较容易实现，现在的不少实验方案都集中干制造量子异或门。
量子异或门和经典异或门非常类似，它有2个输入比待：
控制比特和受控比特。
当控制比特
处于|1＞态，即在上能级时，受控比特态发生反转。
用记号C12代表量子异或操作，其中1,2分别代表控制和受控比
特，则有
其中n1,n2取值0或1，表示模2加。
已有的用来实现量子异或门的方案包括：
利用原子和光腔的相互作用[13]；
利用冷阱束缚离子[14]；
或利用电子或核自旋共振[15]。
在已实现的方案中，以冷阱束缚离子方案最为成功[16]，我们稍详细地介绍这一方案。
在冷阱束缚离子计算机中，N个离子经激光冷却后，束缚到一个线性势阱或环形势阱中，每个离子的两个内态作
为量子比特的载体。
离子受到势阱束缚势和相互间库仑排斥势的作用，在平衡位置附近作微小振动，可用简正模描述，量子化后即用声子描述。
其中频率最低的模称为质心模。
每个离子可以用不同的激光束来控制，在激光束的作用下，离子内态和离子集体振动的元激发——声子发生相互耦合。
通过声子传递相互作用，可实现任意两个比特之间的异或操作。
类似的想法还可以用来实现多比特的量子逻辑门，但目前只有二比特的量子逻辑门得到了具体的实验证实。
原子光腔方案也有实验报道。
原子和光腔的相互作用是量子光学中比较成熟的实验，但此方案的弱点是不易级联，难以形成复杂的逻辑网络。
Gershenfeld等最近指出[15]，利用宏观样品的自旋共振，经适当操作，也可以用来实现量子逻辑门，这种方案稳定性好，在理论上被认为很有前途。
实验上，今年初美国的MIT和LosAlamos小组已实现了
包含3个量子比特的自旋系统，并成功地执行了1十I=2的运算。
三、量子计算机的优越性及其应用
与经典计算机相比，量子计算机最重要的优越性体现在量子并行计算上。
因为量子并行处理，一些利用经典计算机只存在指数算法的问题，利用量子计算机却存在量子多项式算法，这方面最著名的一个例子当推Shor在1994年给
出的关于大数因子分解的量子多项式算法。
大数的因子分解是数学中的一个传统难题，现在人们普遍相信，大数的因子分解不存在经典的多项式算法，这一结果在密码学中有重要应用。
密码学的一个新的方向是实现公钥体制。
公钥体制中，加密密钥公开，可以像电话号码一样通知对方，而脱密密钥是保密的，这样仍然可以实现保密通信。
公银体制的核心在于，从加密密钥不能导致脱密密钥，即它们之间不存在有效的算法。
最著名的一个公钥系统由Rivet，Shamir和Adleman提出，它的安全性就基于大数因子分解，因为对于经典计算机，后者不存在有效的多项式算法。
但Shor却证明，利用量子计算机，可以在多项式时间内将大数分解，这一结果向RSA公钥系统的安全性提出严重挑战。
Shor的算法的主要思想为，首先利用数论中的一些定理，将大数的因子分解转化为求一个函数的周期问题，而后者可以用量子快速傅里叶变换（FFT）在多项式步骤内完成。
除了进行一些超快速计算外，量子计算机另一方面的重要用途是用来模拟量子系统。
早在1982年，Feymann就猜
测，量子计算机可以用来模拟一切局域量子系统，这一猜想，在1996年由Lloyd证明为正确的[17]。
首先得指出，
模拟量子系统是经典计算机无法胜任的工作。
作为一个简单的例子，考虑由40个自旋为1／2的粒子构成的一个量子
系统，利用经典计算机来模拟，至少需要内存为240=106M，而计算其时间演化，就需要求一个240X240维矩阵的指
数，这一般来讲，是无法完成的。
而利用量子计算机，上述问题就变得轻而易举，只需要40个量子比特，就足以用来
模拟。
Lloyd进一步指出，大约需要几百至几千个量子比特，即可精确地模拟一些具有连续变量的量子系统，例如格点规范理论和一些量子引力模拟。
这些结果表明，模拟量子系统的演化，很可能成为量子计算机的一个主要用途。
四、量子计算的困难及其克服途径
量子计算的优越性主要体现在量子并行处理上，无论是量子并行计算还是量子模拟，都本质性地利用了量子相干性。
失去了量子相干性，量子计算的优越性就消失殆尽。
但不幸的是，在实际系统中，量子相干性却很难保持。
消相干（即量子相干性的衰减）主要源于系统和外界环境的耦合。
因为在量子计算机中，执行运算的量子比特不是一个孤立系统，它会与外部环境发生相互作用，其作用结果即导致消相干。
Uruh定量分析了消相干效应，结果表明，量子相
干性的指数衰减不可避免。
Unruh的分析揭示了消相干的严重性，这一结果无疑是对量子计算机的信奉者的当头一棒。
因为量子计算机本质性地利用了量子相干性，相干性的丢失就会导致运算结果出错，这就是量子错误。
除了消相干会不可避免地导致量子错误外，其他一些技术原因，例如量子门操作中的误差等，也会导致量子错误。
因此，现在的关键问题就变成，在门操作和量子存储都有可能出错的前提下，如何进行可靠的量子运算？
Shor在此方向取得一个本质性的进展，这就是量子纠错的思想[19]。
量子纠错是经典纠错码的量子类比。
在三四十年代，经典计算机刚提出时，也曾遇到类似的法难。
当时就有人指出，计算机中，如果任一步门操作或存储发生错误，就会导致最后的运算结果面目全非，而在实际中，随机的出错总是不可避免的。
经典计算机解决此问题，采取的是冗余编码方案。
我们以最简单的重复码来说明其编码思想。
如果输入1比特信号0，现在可通过引入冗余度将其编码为3比特信号000，如果在存储中，3比特中任一比特发生错误，如变成001，则可以通过比较这3比特信号，按照
少数服从多数的原则，找到出错的比特，并将其纠正到正确信号000。
这样虽然在操作中有一定的错误率。
计算机仍
然能进行可靠运算。
Shor的编码就是这种思想的量子类比，但在量子情况下，问题变得复杂得多。
量子运算不再限制于态|0>
而是二维态空间中的所有态，因此量子错误的自由度也就大得多。
另一个更本质的原因为，量子力
学中有个著名的量子态不可克隆定理[20]（我们将另撰文介绍），它指出，对一个任意的量子态进行复制是不可能的。
因此对1个单比特输入态|>
无法将其编码为3比特输入态|>
|>
这些困难表明，任何经典码的简单类比，在量子力学中是行不通的。
但Shor却给出了一个完全新颖的编码，他利用9个量子比特来编码1比特信息，通过此编
码，可纠正9个比特中任一比特所有可能的量子错误。
（关于量子纠错更进一步的介绍，可参看后续文章（《量子编码》）。
Shor的结果极其振奋人心，在此基础上，各种量子纠错码接二连三地被提出。
最新的结果（尚未出版）表明，在量子计算机中，只要门操作和线路传输中的错误率低于一定的阈值，就可以进行任意精度的量子计算。
这些结果显示出，在通往量子计算的征途上，已经不存在任何原则性的障碍。
五、展望
量子计算机的发展方兴未艾。
纵观其发展过程，量子计算机研究中最突出的特点是物理学的原理和计算机科学的交融和相互促进。
计算机不再是一个抽象的数学模型，物理原理对计算机计算能力和效率的限制愈来愈引起人们的重视。
自从Shor提出大数的因子分解的量子算法后，基于量子并行处理的一些超快速算法接连地被发现，现在已形成一门新的研究领域：
量子复杂性理论。
另一方面，量子计算机中消相干的克服，在理论上和实验上都是人们最关注的问题，量予纠错方案被寄予高度厚望，在1996年，量子纠错理论成为研究中最热门的课题。
与量子计算理论上的突飞猛进相比，量子计算机的实验方案还很初步。
现在的实验只制备出单个的量子逻辑门，远未达到实现计算所需要的逻辑门网络。
实验物理学家正在寻找更有效的制备途径，以克服消相干并实现逻辑门的级联。
理论上虽然已提出各种量子纠错码，但在实验上如何利用量子编码来有效地克服消相干，这还是一个富于挑战性的问题。
我们对此已进行了一系列研究（尚未出版），其目的是，根据量子计算机的具体物理模型，来寻找相应的最有效的消相干克服方案。
总体来讲，实现量子计算，已经不存在原则性的困难。
按照现在的发展速度，可以比较肯定地预计，在不远的将来，量子计算机一定会成为现实，虽然这中间还会有一段艰难而曲折的道路。
1.4量子计算的简短历史
基于量子动力学的计算设备的设想首先在19世纪70年代和19世纪80年代，由物理学家和计算机科学家，例如IBMThomas
升级会员 