什么是量子计算机

什么是量子计算机: 什么是计算机; 量子计算机，顾名思义，就是实现量子计算的机器。要说清楚量子计算，首先看经典计算。经典计算机从物理上可以被描述为对输入信号序列按一定算法进行变换的机器，其算法由计算机的内部逻辑电路来实现。经典计算机具有如下特点：（1）其输入态和输出态都是经典信号，用量子力学的语言来描述，也即是:其输入态和输出态都是某一力学量的本征态。如输入二进制序列0110110，用量子记号，即|0110110＞。所有的输入态均相互正交。对经典计算机不可能输入如下叠加态： 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和 Adleman提出，它的安全性就基于大数因子分解，因为对于经典计算机，后者不存在有效的多项式算法。但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的结果极其振奋人心，在此基础上，各种量子纠错码接二连三地被提出。最新的结果（尚未出版）表明，在量子计算机中，只要门操作和线路传输中的错误率低于一定的阈值，就可以进行任意精度的量子计算。这些结果显示出，在通往量子计算的征途上，已经不存在任何原则性的障碍。