量子远距传输又有新发展

纽约时报科技版报道：美国物理学家实现了无纤连接的量子远距传输实验。在此之前，量子传输的纠缠是借助光纤连接实现的，而且，作业发源和目标两者彼此很近。这次实验突破了那些界限，因而，尽管实验不很完美，但被领域内行家看作是崭新的发展、使得量子计算通讯向实用目标迈进了一步。

量子计算机计算与现有计算机计算不同的是：一个量子比特是“0”和“1”同时作业，而现有的是非“0”即“1”。不言而喻，量子计算比现有计算要强大得多得多。通俗比喻说，量子通讯可以将“物体”转换为“信息”、将该“信息”通过“波”而传递到目的地后、再将“信息”转换为“物体”；这是现有计算机电子通讯做不到的事。

为实现“十月革命”，列宁把马赫主义打倒，形成一个结果：在前苏联以马克思列宁主义为国家意识形态的社会里，量子物理和高维空间物理学被视为国家政治意识形态的敌人。如此一来，本来俄国具备的向量子物理进军的科学力量被严重窒息，至今，该领域主要或突破发展几乎就没一个来自俄国。

改革开放和解放思想政策实施，使中国多少摆脱了前苏联做法、允许不同于马列主义意识形态的科学实验，因而，能有潘建伟和他的同事苑震生与陈宇翱等实现了300米光纤连接的量子纠缠的量子远距传输实验，在全球学界得到同行的充分肯定和赞赏。

不幸的是，中国还没有完全摆脱前苏联做法，政治意识形态还在时时干预科技学术，以至于多年来、在宣传媒体界有两个突出表现：

[1] 为政治意识形态服务，宣传媒体把量子“远距传输”翻译说成是“隐型传输”。“远距传输”的原文是“teleport”，而“隐型传输”是“hiden-port”。

[2] 一些中科院的院士和宣传媒体合伙，按照前苏联政治意识形态而把量子物理称为“伪科学”，并试图根据所谓“反伪科学”的科普法条款、将量子物理学在政治上打死、置于死地。

从事科学的底线是实事求是，是承认事实、面对事实和观察事实。新近实现的量子远距传输实验成功，再次证明列宁关于科学学术的“主义”是完全错误的。不必多说，中国要科学创新发展，就需要进一步改革开放和解放思想，需要更彻底地摆脱前苏联体制做法。

20世纪十大算法

本世纪初，美国物理学会(American Institute of Physics)和IEEE计算机社团 (IEEEComputer Society)的一本联合刊物《科学与工程中的计算》发表了由田纳西大学的Jack Dongarra和橡树岭国家实验室的Francis Sullivan 联名撰写的“世纪十大算法”一文，该文“试图整理出在20世纪对科学和工程领域的发展产生最大影响力的十大算法”。
作者苦于“任何选择都将是充满争议的，因为实在是没有最好的算法”，他们只好用编年顺序依次列出了这十项算法领域人类智慧的巅峰之作——给出了一份没有排名的算法排行榜。有趣的是，该期杂志还专门邀请了这些算法相关领域的“大拿”为这十大算法撰写十篇综述文章，实在是蔚为壮观。本文的目的，便是要带领读者走马观花，一同回顾当年这一算法界的盛举。

1946 蒙特卡洛方法

在广场上画一个边长一米的正方形，在正方形内部随意用粉笔画一个不规则的形状，呃，能帮我算算这个不规则图形的面积么？蒙特卡洛(Monte Carlo)方法便是解决这个问题的巧妙方法:随机向该正方形内扔N（N 是一个很大的自然数）个黄豆，随后数数有多少个黄豆在这个不规则几何形状内部，比如说有M个:那么，这个奇怪形状的面积便近似于M/N，N越大，算出来的值便越精确。别小看这个数黄豆的笨办法，大到国家的民意测验，小到中子的移动轨迹，从金融市场的风险分析，到军事演习的沙盘推演，蒙特卡洛方法无处不在背后发挥着它的神奇威力。

蒙特卡洛方法由美国拉斯阿莫斯国家实验室的三位科学家John von Neumann（看清楚了，这位可是冯诺伊曼同志！）,Stan Ulam 和 Nick Metropolis共同发明。就其本质而言，蒙特卡洛方法是用类似于物理实验的近似方法求解问题，它的魔力在于，对于那些规模极大的问题，求解难度随着问题的维数（自变量个数）的增加呈指数级别增长，出现所谓的“维数的灾难”（Course of Dimensionality）。对此，传统方法无能为力，而蒙特卡洛方法却可以独辟蹊径，基于随机仿真的过程给出近似的结果。

最后八卦一下，Monte Carlo这个名字是怎么来的？它是摩纳哥的一座以博彩业闻名的城市，赌博其实是门概率的高深学问，不是么？

1947 单纯形法

单纯形法是由大名鼎鼎的“预测未来”的兰德公司的Grorge Dantzig发明的，它成为线性规划学科的重要基石。所谓线性规划，简单的说，就是给定一组线性（所有变量都是一次幂）约束条件（例如a1*x1+b1*x2+c1*x3>0)，求一个给定的目标函数的极值。这么说似乎也太太太抽象了，但在现实中能派上用场的例子可不罕见——比如对于一个公司而言，其能够投入生产的人力物力有限（“线性约束条件”），而公司的目标是利润最大化（“目标函数取最大值”），看，线性规划并不抽象吧！线性规划作为运筹学(operationresearch)的一部分，成为管理科学领域的一种重要工具。而Dantzig提出的单纯形法便是求解类似线性规划问题的一个极其有效的方法，说来惭愧，本科二年级的时候笔者也学过一学期的运筹学，现在脑子里能想起的居然只剩下单纯形法了——不过这不也正说明了该方法的简单和直观么？

顺便说句题外话，写过《万历十五年》的黄仁宇曾说中国的传统是“不能从数目字上管理”，我们习惯于“拍脑袋”，而不是基于严格的数据做决定，也许改变这一传统的方法之一就是全民动员学习线性规划喔。

1950 Krylov子空间迭代法
1951 矩阵计算的分解方法

50年代初的这两个算法都是关于线性代数中的矩阵计算的，看到数学就头大的读者恐怕看到算法的名字已经开始皱眉毛了。Krylov子空间叠代法是用来求解形如Ax=b 的方程，A是一个n*n 的矩阵，当n充分大时，直接计算变得非常困难，而Krylov方法则巧妙地将其变为Kxi+1=Kxi+b-Axi的迭代形式来求解。这里的K(来源于作者俄国人Nikolai Krylov姓氏的首字母)是一个构造出来的接近于A的矩阵，而迭代形式的算法的妙处在于，它将复杂问题化简为阶段性的易于计算的子步骤。

1951年由橡树岭国家实验室的AlstonHouseholder提出的矩阵计算的分解方法，则证明了任何矩阵都可以分解为三角、对角、正交和其他特殊形式的矩阵，该算法的意义使得开发灵活的矩阵计算软件包成为可能。

1957 优化的Fortran编译器

说实话，在这份学术气息无比浓郁的榜单里突然冒出一个编译器(Compiler)如此工程化的东东实在让人有“关公战秦琼”的感觉。不过换个角度想想，Fortran这一门几乎为科学计算度身定制的编程语言对于科学家（尤其是数学家，物理学家）们实在是太重要了，简直是他们形影不离的一把瑞士军刀，这也难怪他们纷纷抢着要把票投给了它。要知道，Fortran是第一种能将数学公式转化为计算机程序的高级语言，它的诞生使得科学家们真正开始利用计算机作为计算工具为他们的研究服务，这是计算机应用技术的一个里程碑级别的贡献。

话说回来，当年这帮开发Fortran的家伙真是天才——只用23500行汇编指令就完成了一个Fortran编译器，而且其效率之高令人叹为观止:当年在IBM 主持这一项目的负责人JohnBackus在数十年后，回首这段往事的时候也感慨，说它生成代码的效率“出乎了所有开发者的想象”。看来作为程序员，自己写的程序跑起来“出乎自己的想象”，有时候还真不一定是件坏事！

1959-61 计算矩阵特征值的QR算法

呼，又是一个和线性代数有关的算法，学过线性代数的应该还记得“矩阵的特征值”吧？计算特征值是矩阵计算的最核心内容之一，传统的求解方案涉及到高次方程求根，当问题规模大的时候十分困难。QR算法把矩阵分解成一个正交矩阵（什么是正交矩阵？！还是赶紧去翻书吧！）与一个上三角矩阵的积，和前面提到的 Krylov 方法类似，这又是一个迭代算法，它把复杂的高次方程求根问题化简为阶段性的易于计算的子步骤，使得用计算机求解大规模矩阵特征值成为可能。这个算法的作者是来自英国伦敦的J.G.F. Francis。

1962 快速排序算法

不少读者恐怕和我一样,看到“快速排序算法”（Quick Sort）这个条目时,心里的感觉是——“这可总算找到组织了”。相比于其他一些对程序员而言高深莫测的数学物理公式,快速排序算法真是我们朝夕相处的好伙伴——老板让你写个排序算法,如果你写出来的不是快速排序,你都不好意思跟同事打招呼。其实根本不用自己动手实现, 不论是ANSIC,C++ STL,还是Java SDK,天下几乎所有的SDK里都能找到它的某种实现版本。

快速排序算法最早由Tony Hoare爵士设计，它的基本思想是将待排序列分为两半，左边的一半总是“小的”，右边的一半总是“大的”，这一过程不断递归持续下去，直到整个序列有序。说起这位Tony Hoare爵士，快速排序算法其实只是他不经意间的小小发现而已，他对于计算机贡献主要包括形式化方法理论，以及ALGOL60 编程语言的发明等，他也因这些成就获得1980 年图灵奖。

快速排序的平均时间复杂度仅仅为O(Nlog(N))，相比于普通选择排序和冒泡排序等而言，实在是历史性的创举。

1965 快速傅立叶变换

如果要评选对我们的日常生活影响最大的算法，快速傅立叶变换算法应该是当仁不让的总冠军——每天当拿起话筒，打开手机，听mp3，看DVD，用DC拍照 ——毫不夸张的说，哪里有数字信号处理，哪里就有快速傅立叶换。快速傅立叶算法是离散傅立叶算法（这可是数字信号处理的基石）的一种快速算法，它有 IBM 华生研究院的James Cooley和普林斯顿大学的John Tukey共同提出，其时间复杂度仅为O(Nlog(N))；比时间效率更为重要的是，快速傅立叶算法非常容易用硬件实现，因此它在电子技术领域得到极其广泛的应用。


1977 整数关系探测算法

整数关系探测是个古老的问题，其历史甚至可以追溯到欧几里德的时代。具体的说:给定—组实X1,X2,...,Xn，是否存在不全为零的整数a1,a2,...an，使得:a 1 x 1 +a2 x 2 + . . . + a n x n ＝ 0 这一年BrighamYoung大学的Helaman Ferguson 和Rodney Forcade解决了这一问题。至于这个算法的意义嘛，呃，该算法应用于“简化量子场论中的Feynman图的计算”——太深奥的学问拉！

1987 快速多极算法

日历翻到了1987 年，这一年的算法似乎更加玄奥了，耶鲁大学的Leslie Greengard和Vladimir Rokhlin提出的快速多极算法用来计算“经由引力或静电力相互作用的N 个粒子运动的精确计算——例如银河系中的星体，或者蛋白质中的原子间的相互作用”，天哪，不是我不明白，这世界真是变得快！

卡西米尔排斥力得到实验证实

空间并不是什么都没有：真空中充满着量子力学能量波动，它们能够在彼此非常靠近的物体之间产生一种力。这种被称为“Casimir–Lifshitz”的力虽然很弱，但却能引起“粘滞作用”（Stiction），即机械部件粘结成纳米机器。此前，人们只测量到物体之间的相互吸引力，但在理论上，如果真空被某种媒介取代的话，“Casimir–Lifshitz”力就应当变成排斥力。现在这种力已经被实验证实。比吸引力弱一点的排斥力是在一个精心选择的体系中测量到的，该体系由浸没在流体中的相互作用的材料组成。这两种力的强度都随着物体间距的减小而增大。排斥力应当可以让物体以量子形式悬浮在一种流体中，从而产生一种新型的、可切换的纳米尺度的器件，它具有超低的静态摩擦力和低的粘滞作用。悬浮只取决于各种不同材料的光学性质。本期封面所示为一个镀金聚苯乙烯小球和一个二氧化硅薄片之间的排斥力（左边）。用金取代二氧化硅（右边），二者之间的作用力便变成了吸引力。论文地址：http://www.nature.com/nature/journal/v457/n7226/full/457156a.html

《自然》：量子中继器实验被完美实现

从中国科学技术大学获悉，该校合肥微尺度物质科学国家实验室教授潘建伟及其同事苑震生、陈宇翱等，利用冷原子量子存储技术，在国际上首次实现了具有存储和读出功能的纠缠交换，建立了由300米光纤连接的两个冷原子系综之间的量子纠缠。这种冷原子系综之间的量子纠缠可以被读出并转化为光子纠缠，以进行进一步的传输和量子操作。该实验成果完美实现了远距离量子通信中急需的“量子中继器”，向未来广域量子通信网络的最终实现迈出了坚实的一步。8月28日出版的国际著名科学期刊《自然》，以《量子中继器实验实现》为题发表了这项重要研究成果。

目前，高效安全的信息传输日益受到人们的关注。基于量子力学的基本原理，量子通信具有高效率和绝对安全等特点，因此成为国际上量子物理和信息科学的研究热点。然而，作为量子通信的基本资源，脆弱的纠缠光子极易被信道吸收，造成信号随通信距离指数衰减、误码率提高进而导致通信失败。因此，目前量子通信的距离被限制在100公里的量级。类比于传统通信中为了补偿信号衰减而建立的中继器，奥地利科学家在理论上提出，可以通过量子存储技术与量子纠缠交换和纯化技术的结合来实现量子中继器，从而最终实现大规模的远距离量子通信。

据悉，潘建伟及其奥地利的同事分别在1998年和2003年从实验上实现了纠缠交换和纠缠纯化，但是量子存储的实验实现却一直存在着很大的困难。为了解决这一问题，一些科学家做了大量的研究工作。例如，中科大教授段路明及其奥地利、美国的合作者曾于2001年提出了基于原子系综的另一类量子中继器方案，该方案具有易于实验实现的优点，受到了学术界的广泛重视。然而，进一步的研究表明，由于这一类量子中继器方案存在着对于信道长度抖动过于敏感、误码率随距离增加而增长过快等严重问题，无法被用于实际的远距离量子通信中。

为了解决上述困难，潘建伟和他的同事陈增兵、赵博等，于2007年提出了具有存储功能并且对信道长度抖动不敏感、误码率低的高效率量子中继器的理论方案。同时，潘建伟小组及其德国、奥地利的同事经过多年的合作研究，在逐步实现了光子—原子纠缠、光子比特到原子比特的量子隐形传态等重要阶段性成果的基础上，最终从实验上实现了此类量子中继器。

由于量子中继器的实验实现在量子信息研究中的重要意义，《自然》杂志为此专门向有关科学新闻媒体发布了题为《量子推动》(Quantum Boost)的新闻稿，称赞该工作“扫除了量子通信中的一大绊脚石”。

线性方程组的量子算法

这篇论文中提出了一个非常漂亮的量子算法，把求解稀疏矩阵方程的复杂度由O(n)降低到log(n)。我们现有的量子算法，比如Shor算法，Grover算法大都只能对经典算法作出多项式性的改进，可这个算法把最好的经典算法效率作出了指数性的提高。更加重要的是，这是第一个解决了我们科学和工程中最常见的问题的量子算法。像Shor算法那样破解密码毕竟用途有限。在实际的工程和科研中，我们遇到最多的问题就是解线性方程组，且我们遇到的大部分线性方程组都是稀疏的，维度也非常高。经典算法为了解决这个问题，作出了诸多努力，但是现在最好的算法也只能达到O(n)的复杂度。这个量子算法告诉我们，利用量子计算机解我们经典世界最常遇到的线性方程组，会非常非常快，我们可以解近乎无限维的稀疏线性方程组。我相信这会帮助我们解决以前无法解决的问题，长期天气预报，更加有效的网络检索处理。问题只在于，我们什么时候才能造出真正实用的量子计算机。