量子信息学是量子力学与信息科学、计算机科学的交叉学科。美国生物学家E.O.威尔逊(Edward O. Wilson)有一段话很好地说明了交叉学科的重要意义,他说:“科学是我们时代最大胆的形而上学,是人类的创造,相信如果我们有梦想,坚持去发现、解释、再梦想,从而不断进入新的领地,让世界显得更清晰,我们就能掌握宇宙的真正奇异之处,而这些奇异之处将会被证明是互相联系,有意义的。”量子信息就是宇宙的一个奇异之处,反映了信息与物质的深刻联系。

不同学科的科学家给交叉学科带来各自的特长。大数学家希尔伯特有一句幽默的名言:“物理学如此重要,不能留给物理学家。”事实上,希尔伯特对广义相对论的数学形式做出过重要贡献,当时对爱因斯坦构成竞争,让爱因斯坦感到很大压力。类似地,物理学家可以说,生物学是如此重要,不能全留给生物学家。事实上,正是物理学家协助开启了分子生物学。

物理学家还可以说,信息和计算是如此重要,不能全留给计算机科学家。这正是本文所要回顾的。我们将追溯物理学家所走的信息之路,从经典信息到量子信息。

量子信息并不是指经典信息技术的量子物理基础,虽然物理学对经典信息提供了硬件基础,电子计算机的器件(晶体管、存储器等)中的电子也确实服从量子力学。量子计算也不是指关于量子力学的计算问题,不是计算物理。这些固然是重要的领域,但不是所谓的量子计算与量子信息。

什么是信息

信息的英文是information。顾名思义,信息是被告知的东西(Information is that which informs)。 信息是讯息(message)的内容,是对我们在获得该讯息之前对它的无知程度的度量,是对不确定性的降低。当我们对于某件事的不确定性越大,就需要越多的信息来消除这个不确定性。信息的一个性质是,它可以编码成各种形式。比如,同样的思想可以用不同语言来表达。信息论中,信息用一个字符串来表达。

信息不仅是个抽象的数学概念。信息离不开物理载体,又可在不同物理载体之间转换。信息处理过程是物理过程,受物理规律主宰。比如,由声音传递的信息取决于空气和耳膜的振动,由文字表达的信息取决于粉笔灰或墨水的分布;磁存储的信息取决于磁畴的状态;生命信息取决于遗传物质中四种碱基的分布;神经网络中的信号取决于神经元的状态。

1991年,兰道尔(Rolf Landauer)提出一个口号——信息是物理的——倡导从物理的角度研究计算和信息。1990年,惠勒(John Wheeler)提出一个口号——物质来自比特。惠勒和兰道尔的思想影响了最早研究量子信息的一批人,可以称他们为量子信息学的祖父。

顺便提一下,1972年,安德森(Phil Anderson)曾提出:“多了就是不一样”。是说,多体系统会展现出少体系统没有的新性质。从信息和量子信息的角度考虑物理定律的层展,也是一个有意思的方向。

麦克斯韦妖

最早进入物理学的信息问题,可能是麦克斯韦妖佯谬。1867年,麦克斯韦在一封信里提出这个佯谬。他在1871年出版的《热的理论》(Theory of Heat)一书中,做了详细论述。考虑封闭容器内处于恒温的气体,他写道:“假设这样的一个容器分成两半,A和B,隔板上有一个小洞,有一个有意识的存在(being)能够看到单独的分子,能够关闭或打开这个洞,从而让较快的分子从A运动到B,让较慢的分子从B运动到A。因此他不需要做功,就能提高B的温度,降低A的温度。这与热力学第二定律矛盾。1879,汤姆逊(William Thomson,也就是开尔文勋爵)将麦克斯韦假想的being称为麦克斯韦妖。

4.1

麦克斯韦

(James Clerk Maxwell,1831—1879)

1929年,作为博士论文,西拉德(Leo Szilard)研究了麦克斯韦妖问题。他用比特表示分子的位置状态,涉及了信息。(这里比特指容器的左右,他没有用比特和信息这些名词。)西拉德提出麦克斯韦妖测量分子状态时,消耗能量,熵增加了kBln2,抵消了气体分子的熵减少。这里kB代表玻尔兹曼常数。

西拉德还提出一种利用信息的热机,也就是说,可以从信息提取功。我们用查尔斯·本内特(Charles Bennett)在1987年提出的版本来讨论。考虑一个恒定温度的热库接触的小车,以及一串小隔间组成的传送带,每个小隔间里面有一个分子。假设事先知道每个分子的位置状态(信息),也就是在小隔间的左半部或者右半部。相应地,就可以设计机械,利用活塞向右半部或者左半部移动,分子所在的空间增加到整个小隔间。从而分子总是对外做功,驱动小车运动。也就是说,信息转化为功。如果事先不知道分子的位置,平均做功为零。

信息论

1948年,香农(Claude Shannon)借助熵的概念,提出了信息论。考虑一个字母表,由a1,a2, ..., an组成,每个字母出现的概率分别是p1,p2,..., pn,p1+p2+...+ pn=1。香农定义了信息熵: H=-p1log2(p1) -p2log2(p2) ...-pnlog2(pn)。这里log2代表以2为底的对数。香农证明了这n个字母组成的讯息可以压缩到nH比特。也就是说,信息熵代表平均每个字母的信息量,定量刻画了信息存储与传输所需的资源。

我们可以看出,如果p1=1, 其他的pi=0,也就是说只有a1这一个字母出现,那么H=0, 也就是说没有信息量;如果每个pi都等于1/n, 那么H=log2n,这是最大值。

兰道尔原理

从20世纪30年代开始,计算机的基础理论和技术有很多发展。1961年,兰道尔在IBM工作时提出了兰道尔原理:每删除一个比特的信息,环境的熵至少增加kBln2,也就是说,至少需要耗散能量kBTln2。我们知道,熵乘以温度T就是热量,也就是耗散到环境的能量。

1973年,本内特提出可逆计算的概念,指出原则上不需要能耗。虽然很多逻辑运算是不可逆的,比如2+3和1+4都等于5,因此从输出结果5,不能唯一确定输入。但是不可逆运算可以嵌套在可逆运算中,也就是将输入信息也当作输出结果的一部分。1982年,他提出可逆图灵机模型。图灵机是最简单的计算模型。

在这些工作的基础上,1987年,本内特给出了麦克斯韦妖佯谬的解决方案——对分子状态的测量本身可以不消耗能量,测量结果存储在妖的记忆中,气体的熵减少由妖的记忆的熵增加补偿。但是妖的记忆有限,为了存储新的测量结果,需要删除旧的记忆,因此必须将熵转移到环境,也就是说,必须耗散能量到环境中去。因此耗散的能量不是来自测量信息,而是来自删除信息。当然,如果将气体、妖、环境一起考虑,总熵总是不减少的。

信息与能量

作为对前述若干概念的消化,我们看一下信息与能量的关系。如果事先知道某讯息(一串比特,比如各分子的位置)的内容,删除这个讯息不需要消耗能量。

例如,考虑一个盒子中有一个分子,如果知道它在盒子的哪半边,可设法用一个小盒子包住它,它对小盒子的每个壁都有碰撞,平均做功为零,因此我们在不做功的情况下将它转移到事先选好的盒子的一半(事先选定左边或者右边),也就是删除讯息。因此,知道信息后,可以不费能量将其删除。而且,前面说过,还可以利用它,让分子对外做功。

但是,如果不知道分子位置时,我们只能统一地将盒子体积压到一半(事先选定左边或者右边)。这需要付出能量。

计算机极简史

19世纪的查尔斯·巴贝奇(Charles Babbage)设计了两个机械计算机,虽然都没能实际完成。19世纪20年代,巴贝奇设计了计算多项式函数的差分机。1837年,他又设计了可编程的机械计算机Analytic Engine,包含了计算机的主要元素。1941年,有人实现了他的设计。

4.2

巴贝奇制作的Analytic Engine的模型

诗人拜伦的女儿阿达·洛芙莱斯(Ada Lovelace)为Analytic Engine写了程序,成为历史上第一位程序员。巴贝奇和洛芙莱斯的照片曾经放在一起,作为英国50英镑新钞票上的候选人物。但最终,另一位候选人阿兰·图灵(Alan Turing)胜出。

4.3

图灵被选为50英镑新钞票上的人物

1937年,图灵提出了图灵机、普适图灵机和图灵假说,严格定义了计算和程序的概念。图灵假说是说,存在普适图灵机,可以模拟任何图灵机。这就是说,存在普适计算机,用程序就可以实现任何计算。

1939年,物理学家约翰·阿塔纳索夫(John Vincent Atanasoff)与他的学生克利福德·贝里(Clifford Berry)建造了第一台电子计算机。这是一台特定目的的计算机,不能编程。它用二进制和布尔代数,能计算29个联立方程。硬件上,它由电子真空管实现计算,用电容器作内存,没有中央处理器(CPU)。

物理学家约翰·莫克利(John Mauchly )和艾克特(J. P. Eckert)设计了世界上第一台电子通用计算机,即ENIAC (Electronic Numerical Integrator And Computer,电子数值积分计算机),1946年建成。ENIAC的第一个用途是冯·诺依曼和乌拉姆的氢弹计算。莫克利多次访问过阿塔纳索夫,但是1944年之前,没有告知后者自己也在造计算机。这使得莫克利后来没有获得专利。

电子计算机飞速发展。20世纪50年代,每秒做1 000次浮点运算。而现在的速度是148.6P FLOPS(P = 1012)。1965年,戈登·摩尔(Gordon Moore)总结出所谓的“摩尔定律”:单个集成电路芯片上的晶体管数目大约每两年翻一番。从下图可以看出,摩尔定律延续多年。

晶体管越来越小,越来越快。如此下去,单个比特只需要原子尺寸。但是在原子尺寸,量子效应将起支配作用,适用于经典计算机的摩尔定律也就不能延续。

所以,一个思路就是,变不利为有利,干脆用量子力学作为新的计算(逻辑)原理。利用量子力学的原理,特别是量子态叠加原理,完成计算任务,处理和传递信息,这就是所谓的量子计算与量子信息。

量子力学基本问题的研究

量子计算与量子信息又与量子力学基本问题密切关联。量子纠缠是超越任何经典关联的量子特性,研究始于爱因斯坦等人,经过戴维·玻姆(David Bohm)等人,后来由约翰·贝尔(John Bell)取得突破。

单量子系统在这些研究中体现出重要性。以前,正如薛定谔所说,我们从来不用单个电子或原子或小分子做实验。在思想实验中,我们有时候假设能够做,这不可避免导致奇怪的后果……

事实上,当年的思想实验今天已经成为真实的实验,对于奇怪后果的探究导致量子物理基础和量子信息的进展。

量子计算与量子信息的兴起

1978年,保罗·贝尼奥夫(Paul Benioff)提出一个量子力学模型,实现经典图灵机的每一步过程。1982年,费曼提出,用经典计算机模拟量子过程需要指数级资源,而量子计算机则可以有效地模拟量子过程。苏联的马宁(I. Manin)也有类似的想法。1983年,阿尔伯特提出量子元胞自动机。

1985年,英国物理学家戴维·多伊奇(David Deutsch)提出量子图灵机和普适量子图灵机的概念。1989年,他又提出由量子门组成的量子计算的线路模型。

作为一个有实用意义的突破,1994年,美国计算机科学家彼得·肖(Peter Shor)提出有效解决素数因子分解(寻找奇数的素数因子)的量子算法。在经典计算中,这个问题是一个NP问题,也就是说,需要的时间不是数字的二进制位数n的多项式函数。事实上,需要的时间是exp(O(n3(log(n)2/3 ))。而肖的量子算法需要的时间只是O(n2 log(n) loglog(n))。f=O(g)的意思是,|f/g|介于两个有限正数之间。 量子计算的算法基于纠缠态的运用。量子纠缠也导致量子通信,比如量子隐形传态。而量子密码的某些方案基于海森堡不确定关系,某些方案基于量子纠缠。

2017年,意大利的国际理论物理中心将狄拉克奖授予本内特、多伊奇和肖,以表彰他们用量子力学的基本概念解决计算和信息的基本问题,从而将量子力学、计算机科学和信息联系在一起。

小 结

信息是物理的。因此经典计算和经典信息基于经典物理,而量子物理导致量子计算和量子信息。突破摩尔定律的需要,经典信息和经典计算的量子推广,量子力学基本问题的探究,形成合力,催生了量子信息和量子计算。

___________________

本文作者施郁是复旦大学物理学系教授。