Algorithm 版 (精华区)

发信人: Lerry (想不开·撞树), 信区: Algorithm
标  题: 量子信息讲座（一）
发信站: 哈工大紫丁香 (2002年04月23日16:24:01 星期二), 转信

量子信息讲座
第一讲   量子计算机
段路明   郭光灿
(中国科学技术大学物理系.合肥230026)
编者按   在人类即将跨入21世纪之际，信息科学面临着新的挑战。计算机是否存在极限
的运算速度？能否实现不可破译、不可窃听的保密通信？诸如此类的问题一直是数学家
和电子技术专家们关注的重要课题。近年来，物理学家加入这个研究行列，他们成功地
将量子理论和信息科学结合起来，提出许多令人耳目一新的概念、原理和方法，于是"量
子信息"作为新兴的学科分支便应运而生。当前量子计算机、量子通信和至于密码术等已
经成为研究热点，并取得重要进展。本刊从本期开始将陆续刊登一组"量子信息"专题文
章，介绍这个领域的动态和进展。
摘要   量子力学和计算机理论，这两个看起来互不相关的领域，其结合却产生了一门富
于成效的学科：量子计算机。文章介绍了量子计算机的基本概念和历史背景，它相对于
经典计算机的优越性，它的构造和实验方案，以及实现量子计算的困难及其克服途径，
最后展望了量子计算机的发展前景。
关键词   量子计算机，量子图灵机，量子并行计算，消相干
一、量子计算机的概念及发展背景
    1996年，美国《科学》周刊科技新闻中报道，量子计算机引起了计算机理论领域的
革命。同年，量子计算机的先驱之一，Bennett在英国《自然》杂志新闻与评论栏声称，
量子计算机将进入工程时代。目前，有关量子计算机的理论和实验正迅猛发展，那么，
什么是量子计算机呢？
   量子计算机，顾名思义，就是实现量子计算的机器。要说清楚量子计算，首先看经典
计算。经典计算机从物理上可以被描述为对输入信号序列按一定算法进行变换的机器，
其算法由计算机的内部逻辑电路来实现。经典计算机具有如下特点：
    （1）其输入态和输出态都是经典信号，用量子力学的语言来描述，也即是:其输入
态和输出态都是某一力学量的本征态。如输入二进制序列0110110，用量子记号，即|01
10110＞。所有的输入态均相互正交。对经典计算机不可能输入如下叠加态：
C1|0110110 ＞＋ C2|1001001＞。
    （2）经典计算机内部的每一步变换都将正交态演化为正交态，而一般的量子变换没
有这个性质，因此，经典计算机中的变换（或计算）只对应一类特殊集。
    相应于经典计算机的以上两个限制，量子计算机分别作了推广。量子计算机的输入
用一个具有有限能级的量子系统来描述，如二能级系统（称为量子比特）,量子计算机的
变换（即量子计算）包括所有可能的么正变换。因此量子计算机的特点为[1]:
    [1]量子计算机的输入态和输出态为一般的叠加态，其相互之间通常不正交；
    [2]量子计算机中的变换为所有可能的么正变换。得出输出态之后，量子计算机对输
出态进行一定的测量，给出计算结果。
    由此可见，量子计算对经典计算作了极大的扩充，经典计算是一类特殊的量子计算
。量子计算最本质的特征为量子叠加性和相干性。量子计算机对每一个叠加分量实现的
变换相当于一种经典计算，所有这些经典计算同时完成，并按一定的概率振幅叠加起来
，给出量子计算机的输出结果。这种计算称为量子并行计算。量子并行处理大大提高了
量子计算机的效率，使得其可以完成经典计算机无法完成的工作，如一个很大的自然数
的因子分解（后面将叙及）。量子相干性在所有的量子超快速算法中得到了本质性的利
用[2]。
    量子计算机的概念源于对可逆计算机的研究，而研究可逆计算机是为了克服计算机
中的能耗问题。早在六七十年代，人们就发现，能耗会导致计算机芯片的发热，影响芯
片的集成度，从而限制了计算机的运行速度。Landauer[3]最早考虑了这个问题，他考察
了能耗的来源，指出：能耗产生于计算过程中的不可逆操作。例如，对两比待的异或操
作，因为只有一比特的输出，这一过程损失了一个自由度，因此是不可逆的，按照热力
学，必然会产生一定的热量。但这种不可逆性是不是不可避免的呢？事实上，只要对异
或门的操作如图1所示的简单改进，即保留一个无用的比特，该操作就变为可逆的。因此
物理原理并没有限制能耗的下限，消除能耗的关键是将不可逆操作改造为可逆操作（见
图1）。
图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',s',d）为取
值[0,1]的实数，它完全决定了概率图灵机的性质。经典计算机理论证明，对解决某些问
题，慨率算法比确定性算法更为有效。
    量子图灵机非常类似于上面描述的经典概率图灵机，现在q,s,q',s'相应地变成了量
子态，而慨率函数（q,s,q',s',d）则变成了取值为复数的概率振幅函数x(q,s,q',s',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和Los Alamos小组已实现了
包含 3个量子比特的自旋系统，并成功地执行了1十l＝2的运算。
三、量子计算机的优越性及其应用
    与经典计算机相比，量子计算机最重要的优越性体现在量子并行计算上。因为量子
并行处理，一些利用经典计算机只存在指数算法的问题，利用量子计算机却存在量子多
项式算法，这方面最著名的一个例子当推Shor在1994年给出的关于大数因子分解的量子
多项式算法。
    大数的因子分解是数学中的一个传统难题，现在人们普遍相信，大数的因子分解不
存在经典的多项式算法，这一结果在密码学中有重要应用。密码学的一个新的方向是实
现公钥体制。公钥体制中，加密密钥公开，可以像电话号码一样通知对方，而脱密密钥
是保密的，这样仍然可以实现保密通信。公银体制的核心在于，从加密密钥不能导致脱
密密钥，即它们之间不存在有效的算法。最著名的一个公钥系统由Rivet，Shamir和 Ad
leman提出，它的安全性就基于大数因子分解，因为对于经典计算机，后者不存在有效的
多项式算法。但Shor却证明，利用量子计算机，可以在多项式时间内将大数分解，这一
结果向RSA公钥系统的安全性提出严重挑战。
    Shor的算法的主要思想为，首先利用数论中的一些定理，将大数的因子分解转化为
求一个函数的周期问题，而后者可以用量子快速傅里叶变换（FFT）在多项式步骤内完成
。
    除了进行一些超快速计算外，量子计算机另一方面的重要用途是用来模拟量子系统
。早在1982年，Feymann就猜测，量子计算机可以用来模拟一切局域量子系统，这一猜想
，在1996年由 Lloyd证明为正确的[17]。首先得指出，模拟量子系统是经典计算机无法
胜任的工作。作为一个简单的例子，考虑由40个自旋为1／2的粒子构成的一个量子系统
，利用经典计算机来模拟，至少需要内存为240=106M，而计算其时间演化，就需要求一
个 240 X 24O维矩阵的指数，这一般来讲，是无法完成的。而利用量子计算机，上述问
题就变得轻而易举，只需要40个量子比特，就足以用来模拟。Lloyd进一步指出，大约需
要几百至几千个量子比特，即可精确地模拟一些具有连续变量的量子系统，例如格点规
范理论和一些量子引力模拟。这些结果表明，模拟量子系统的演化，很可能成为量子计
算机的一个主要用途。
四、量子计算的困难及其克服途径
    量子计算的优越性主要体现在量子并行处理上，无论是量子并行计算还是量子模拟
，都本质性地利用了量子相干性。失去了量子相干性，量子计算的优越性就消失殆尽。
但不幸的是，在实际系统中，量子相干性却很难保持。消相干（即量子相干性的衰减）
主要源于系统和外界环境的耦合。因为在量子计算机中，执行运算的量子比特不是一个
孤立系统，它会与外部环境发生相互作用，其作用结果即导致消相干。Uruh定量分析了
消相干效应，结果表明，量子相干性的指数衰减不可避免。Unruh的分析揭示了消相干的
严重性，这一结果无疑是对量子计算机的信奉者的当头一棒。
    因为量子计算机本质性地利用了量子相干性，相干性的丢失就会导致运算结果出错
，这就是量子错误。除了消相干会不可避免地导致量子错误外，其他一些技术原因，例
如量子门操作中的误差等，也会导致量子错误。因此，现在的关键问题就变成，在门操
作和量子存储都有可能出错的前提下，如何进行可靠的量子运算？
    Shor在此方向取得一个本质性的进展，这就是量子纠错的思想[19]。量子纠错是经
典纠错码的量子类比。在三四十年代，经典计算机刚提出时，也曾遇到类似的法难。当
时就有人指出，计算机中，如果任一步门操作或存储发生错误，就会导致最后的运算结
果面目全非，而在实际中，随机的出错总是不可避免的。经典计算机解决此问题，采取
的是冗余编码方案。我们以最简单的重复码来说明其编码思想。如果输入1比特信号0，
现在可通过引入冗余度将其编码为3比特信号000，如果在存储中，3比特中任一比特发生
错误，如变成001，则可以通过比较这3比特信号，按照少数服从多数的原则，找到出错
的比特，并将其纠正到正确信号000。这样虽然在操作中有一定的错误率。计算机仍然能
进行可靠运算。Shor的编码就是这种思想的量子类比，但在量子情况下，问题变得复杂
得多。量子运算不再限制于态 |0＞和|1＞，而是二维态空间中的所有态，因此量子错误
的自由度也就大得多。另一个更本质的原因为，量子力学中有个著名的量子态不可克隆
定理[20]（我们将另撰文介绍），它指出，对一个任意的量子态进行复制是不可能的。
因此对1个单比特输入态|＞，无法将其编码为3比特输入态|＞|＞|＞。这些困难表明，
任何经典码的简单类比，在量子力学中是行不通的。但Shor却给出了一个完全新颖的编
码，他利用9个量子比特来编码1比特信息，通过此编码，可纠正9个比特中任一比特所有
可能的量子错误。（关于量子纠错更进一步的介绍，可参看后续文章（《量子编码》）
。 Shor的结果极其振奋人心，在此基础上，各种量子纠错码接二连三地被提出。最新的
结果（尚未出版）表明，在量子计算机中，只要门操作和线路传输中的错误率低于一定
的阈值，就可以进行任意精度的量子计算。这些结果显示出，在通往量子计算的征途上
，已经不存在任何原则性的障碍。
五、展望
    量子计算机的发展方兴未艾。纵观其发展过程，量子计算机研究中最突出的特点是
物理学的原理和计算机科学的交融和相互促进。计算机不再是一个抽象的数学模型，物
理原理对计算机计算能力和效率的限制愈来愈引起人们的重视。自从Shor提出大数的因
子分解的量子算法后，基于量子并行处理的一些超快速算法接连地被发现，现在已形成
一门新的研究领域：量子复杂性理论。另一方面，量子计算机中消相干的克服，在理论
上和实验上都是人们最关注的问题，量予纠错方案被寄予高度厚望，在1996年，量子纠
错理论成为研究中最热门的课题。
    与量子计算理论上的突飞猛进相比，量子计算机的实验方案还很初步。现在的实验
只制备出单个的量子逻辑门，远未达到实现计算所需要的逻辑门网络。实验物理学家正
在寻找更有效的制备途径，以克服消相干并实现逻辑门的级联。理论上虽然已提出各种
量子纠错码，但在实验上如何利用量子编码来有效地克服消相干，这还是一个富于挑战
性的问题。我们对此已进行了一系列研究（尚未出版），其目的是，根据量子计算机的
具体物理模型，来寻找相应的最有效的消相干克服方案。总体来讲，实现量子计算，已
经不存在原则性的困难。按照现在的发展速度，可以比较肯定地预计，在不远的将来，
量子计算机一定会成为现实，虽然这中间还会有一段艰难而曲折的道路。
参考文献
[1] S.Lloyd, Science 26l(1993), 1569; S.Lloyd, Science, 263(1994), 695.
[2] D. DiVincenzo, Science, 270(1995), 255.
[3] R.bouer, IBM J. Res. Dev.,5(1961), l83.
[4] C.H.Bennett, IBM J. Res. Dev.,6(1973),525.
[5] P.Benioff, Phys. Rev. Lett., 48(1982), 1581.
[6] R.P.Feymann, Int. J. Theor. Phys., 21(1982),467.
[7] D.Deutsch, R. Jozsa, Proc. R. Soc. London A. 439(1992), 553.
[8] P.W.Shor, in Procedeeings of the 35th Annual Symposium of Foundation of 
Computer Science. (IEEE Computer Society, Los Alamitos, CA) l994, 124.
[9] A.Yao, in Procedings of the 34th Annual Symposium of Foundation of Compu
ter Science. (IEEE Computer Society, Los Alamitos, CA), l993, 352.
[l0] D.Deutsch, Proc. R. Soc. London A, 425(l989), 73.
[ll] D.Deutsch, Proc. R. Soc. London A, 449 (1995),669,;S.Lloyd,Phys. Rev. L
ett., 75(1995), 346.
[12] A.Barenco et al., Phys. Rev. Lett., 74(1995), 4083.
[13] T. Pallizari et al., Phys. Rev. Lett., 75(1995), 3788.
[14] J. Cirac, P. Zoller, Phys. Rev. Lett., 74(l995), 4091.
[15] N.A.Geshenfeld, I. L. Chuang, Science, 275 (1997),350.
[16] C.Monroe et al., Phys. Rev. Lett., 75(1995),47l4.
[17] S.Lloyd, Science, 273(1996), 1073.
[18] W.G.Unruh, Phys. Rev. A, 51(l995), 992.
[19] P.W.Shor, Phys. Rev. A, 52(1995), 2493.
[20] W.K.Wootters, W.H.Zurek, Nature, 299 (1982 ),802　
首 页 -- 成 员 -- 科 研 --讲 座 -- 链 接 -- 留 言
中国科学技术大学量子通信与量子计算开放实验室版权所有
Copyright (c) 2001  All Rights Reserved

--
就让一切顺其自然
在你我之间
苦苦坚持多年
待我回到从前
在天的那边
让奇迹出现

※ 来源:·北大未名站 bbs.pku.edu.cn·[FROM: 162.105.30.157]
--
※ 转寄:·北大未名站 bbs.pku.edu.cn·[FROM: 202.118.224.2]
--
※ 修改:·Lerry 於 04月23日16:26:14  修改本文·[FROM: FTCL.hit.edu.cn]
※ 转载:．哈工大紫丁香 bbs.hit.edu.cn．[FROM: FTCL.hit.edu.cn]