量子计算，发展中的伟大科学——记姚期智教授“21世纪计算”大会主题演讲
by 微软亚洲研究院
at 2011-12-07 19:56:42
original http://blog.sina.com.cn/s/blog_4caedc7a0102dzae.html
编者按: 量子计算,这一科学史上举足轻重的学科，正逐渐演变成为一项伟大的科学。然而，它对于很多人而言依旧蒙着一层神秘面纱。究竟什么是量子计算，这门学科究竟精彩在何处？让我们来听听清华大学交叉信息研究院院长、2000年图灵奖获得者、美国科学院及美国艺术与科学院院士——姚期智教授，是如何解答的。
Quantum Computing: A Great Science in the Making
姚期智教授是清华大学交叉信息研究院院长、2000年图灵奖获得者、美国科学院(NAS）及美国艺术与科学院（AAAS）院士、中科院院士。姚教授的研究课题包括算法和复杂性内容计算。从1995年到2006年，他一直担任麻省理工、斯坦福大学和加州大学、伯克利大学的教授。姚教授是中国香港大学的知名教授。他从三个方面对研究做出了贡献：1）理论计算科学，开发了现代拓扑学、解决了相关问题，并建立了计算几何学；2）数据结构内容计算，主要是在计算理论方面的贡献；3）量子计算学。
点击观看姚期智教授的精彩演讲视频：
诸位下午好，今天我为大家介绍的是量子计算。量子计算的出现距今已有几十年，但是这门学科对于包括计算机科学家在内的很多人来说，仍旧蒙着一层非常神秘的面纱。今天我要解答的问题，就是什么是量子计算，为什么这么多人觉得它是非常精彩的学科。事实上，我要指出的是，量子计算不仅是一门精彩的学科，而且正在逐渐演变为一项伟大的科学，在整个科学史上都是举足轻重的。
如何说明这一点呢？我认为最好的方法就是先看一些伟大学科的例子。首先，无可争议的就是X射线结晶学。1895年，威海尔姆•伦琴（Wilmellll Rsntgen）发现了X射线。当他获得了第一届诺贝尔物理学奖时，人们知道粒子，也知道波，但问题是，这个新的东西是一个波，还是一个粒子呢？在1912年，冯•劳厄（Max von Laue）确认X射线有很强的波的性质，因为他展示了可以利用实验展示它的衍射性质。展示方式就是对晶体发射X射线，这样我们就可以看到衍射图案。从这就可以看出，X射线其实是一种波长很短的波，因为波长应该大约等于晶体的结构的间隔。这个实验使冯•劳厄获得了诺贝尔奖。
1913年，亨利•布拉格（Henry Bragg）和劳伦斯•布拉格（Lawrence Bragg）又延伸出了一个数学公式，以数学量化的方式解释X射线晶体衍射的形成。事实上，他们发现这个X射线不是一种波，并决定将X射线以更加深入的方式进行研究。因为这样的研究，他们也获得了诺贝尔奖。20世纪20年代的时候，人们也了解到了，通过X射线可以使用数学公式，对简单的材质结构进行分析。比如说，金属物质和非有机的分子。但是，对于大分子而言，通过X射线的衍射图获得份子结构是非常困难的。人们研究了很多年，最终能够使用它去降低结构，并且对于大型的生物分子结构进行一种解构分析，霍德金（Hodgkin）也因此获得诺贝尔奖。
我想，大家可能更熟悉20世纪50年代的佩鲁斯和肯卓（Perutz & Kendrew），他们因肌红蛋白的结构分析获得了诺贝尔奖。同样是这个时代，威尔金斯（Wilkins）富兰克林（Franklin）从图片的层次进行DNA分析。毫无疑问，这确实是一项伟大的科学。第二个伟大的例子就是电脑。1901年，希尔伯特（Hilbert）在他的国会辩论中，就谈到了以数学的方式证明机械化。1936年，图灵（Turing）发明了图灵机，所以我们才能够严谨地定义什么叫做机械化。正如我在课堂上跟学生所说的，这就是电脑所带来的大爆炸。所有的现代轨迹，例如算法、计算机、人工智能、系统，各种各样的研究从此开始。1945年，约翰•冯•诺伊曼（Jonh von Neumann）开始建构电子计算机的设计。从20世纪40年代到50年代，我们就看到了晶体管的发明。毫无疑问，电脑科学的影响已经无所不在，它确实也是一项伟大的科学。
我们从中能学到什么呢？我认为，之所以能有这么伟大的科学，通常都是依赖颠覆性的技术推动一些以前根本想象不到的探索而发生的。比如，X射线帮助我们以更深入的方式探索分子的结构，而电脑赋予我们更高的计算能力和存储能力来解密DNA。
下面看一下今天谈到的量子计算，确实也非常符合刚才谈到的伟大科学的产生模式，跟我刚才谈到的两个例子非常类似。我相信，这也是量子计算非常关键的内容。我们经常谈到量子机械学，在有关量子机械学方面也有很多的论文，那些主要是从广义的角度来解释的。
希望通过我下面的介绍，能为大家揭开有关量子计算神秘的面纱。我们想象一下，颠覆式的量子计算学，比如我们通过一个物理进程来计算一个公式，先培育一个晶体C，它的结构是由函数和输入决定的。我们把一个量子波照在C上，就像X射线一样，去观察这样一个衍射的样式，这个时候如果我们运气好，就能够算出答案。当然，我们并非真的去培育一个晶体，而可以用仿真模拟这个过程。非常有意思的就是，软件的模拟能够让我们在合理的时间范围内非常精准地做出整个过程。
下面我再为大家举一个非常知名的例子。1993年，西蒙（Simon）在他发表的一篇论文中提出了人为虚构的问题（见图1）。假设有一个黑盒，它是一个公式，而这个公式有输入输出都是n比特的。他说这个公式是2对1，所以如果你看所有的输入输出，你会发现可能的输出结果是输入结果的一半，对于任何可能的输出，都恰好存在两个与之对应的输入。在黑盒中，有一个密文S，所以对于某一个输出，与之对应的两个输入存在一个关系：如果一个是X，另一个就是X+S。假如你知道了一些输入。这个加法运算是某种二进制的位运算。假设你知道了这个设定，但是你不知道S是什么，所以问题就是如何求出这个S。你只能够提供一些输入，然后观察与之对应的输出是什么。假设不知道非常神秘的X是什么，所以这个问题提的就是决定这个S。所以我们要做的就是散射，观察输出得出的是什么。
图1 西蒙的问题
在经典计算模型下，不提供指数级别的询问，黑盒就像一个随机的一对一的函数，是不能够求出S的。我们知道散射的重要例子，就是你有一个光源，你在上头钻一个洞，然后挡上，然后再去观察，布上有洞，有一个光源照过去，然后研究光散射的样式，有亮点，有暗点，而暗点就是这些光波所出现的位置。我们这个时候有两个屏幕，第一个是打了孔的，第二个是没有打孔的，这是非常知名的例子。所以你设定所有的物理参数，还有每个孔之间的距离，还有波长，我们就可以计算样式了。对于我们来说，非常有意思的发现就是，如果我们研究一下第二个屏幕，亮点和暗点之间的距离，肯定可以通过波长的公式计算出来（见图2）。
图2 散射的例子
所以，我们观察输出的样式，第二张屏幕至少能够为我们解答物理设置的信息。同时，我们感兴趣的地方是，我们想做什么呢？希望能够找出一个秘诀，我们进行设计。包括假设光的实验，后来观察屏幕上的间隔，会告诉我们里面神秘的地方。正是这样的情况，假设光的实验，在第一个屏幕上，我们能够一直钻一个孔，每一个孔有一个标签，叫做二进制的标签放上去。第二个屏幕是一个二维的屏幕，在X到N，还有Z轴，还有Y轴上，具体规定一下实验。我们会说，圆来自于其中一个孔，在第一个屏幕上，这个标签是X，会跟着散射到第二个屏幕上，也是完全的一条横线上。相关的Z决定由F(x)的值，就是黑盒里面F(x)的值决定。对X轴Y轴应该是均匀的，每一个符号会相互的交替，幅度是正的，或者负的，加或减，加或减取决于X、Y的内积，二进制乘在一起的话，第二个模块得到0，如果X.1是同等的话，会得到更多的幅度，或者是更少的幅度。
来观察两个孔，就是X的S，差不多一半的亮点会消失了，因为是一个很大的干扰，他们相互之间影响了。两个孔，X+S的话，会注意到，正是这两点没有任何的光，横向坐标轴满足一个公式，亮点的地方就是1.Z=0。我们看一个亮点的地方，会告诉一个线性的等式控制的神秘地方。如果现在打开整体的屏幕，会看到第二个屏幕上，完全是可能的点的一半，是亮点区域。所以打开几个点的话，会得到一个线性的等式，这里面可以从S上能看到，这就是物理上的解决方案，对于找到神秘地方的办法。
现在我们的问题就是钻两个孔在屏幕上。任何一个屏幕无法观察到不同的现象，这就需要我们的软件发挥作用了。我们发现并不真正需要生成整体的参数，但是我们需要模拟这样的实验。就是一个光子上，来自于这个光源的，看一下在什么地方，在第二个屏幕上怎么衍射的情况。其中每一个观察的情况都给我们一个线性等式，就是S，观察到的Y=0。做两次这个实验的话，有很高的可能性，能够得到足够的等式，可以找出神秘的S，这就是我们整体的过程。对这个问题解决的一个方式，可以看到，实际上这样一个问题，如果真有一个量子L的话，就可以做这样的实验，而且很容易在量子的计算机上，也是微软目前正在做的项目。如果我们有量子的计算机，就可以来模拟上面的实验了。西蒙的一篇重要论文基本上使用了完全一样的办法。这种办法一年后被彼得•秀尔（Peter Shor）继续使用，设计了一个高效的分解整数因子的量子算法。这是非常聪明的选择和做法。
也许你可能会说，这只是个白日梦。我想，我们多数人有这样一种印象，量子计算机可能永远不会真正出现的。但是如果你和真正进行量子计算机试验的专家交流，你就会发现这个想法正在逐步实现。全球有很多主要的量子信息机构正在实现量子计算机。而且在过去的五六年时间里，很多主要的建构工作都已完成，例如，美国马里兰大学刚刚成立了一个量子研究中心，员工包括了1997年诺贝尔物理学奖得主William D. Phillips在内的29位较少，得到了美国国家标准局、基金委、国防部的资助。还有美国哈佛大学和麻省理工学院联合成立的超冷原子中心，研究人员包括2001年诺贝尔奖得主W. Ketterle在内15位科学专家教授，也得到了得到了美国国家标准局和基金委的支持。此外，在美国加州理工学院和微软合作的量子站，研究人员包括费尔兹奖得主M. Freedman在内的17名教授，美国政府和微软公司都对其给予了很大的支持。五年前，地处加拿大的黑莓的创立机构同样在新加坡启动了量子信息中心，而且在欧盟和日本也建有这样的中心。
试想一下，他们为什么如此感兴趣？早期的时候，人们想努力地选择不同的技术。现在已经很明确了，只有少数的几种技术可以是有可能实现的，而且是最佳的选择。人们已经取得很大的进展。就像计算机早期一样，起步非常困难，但当真正解决工程部分之后就比较简单。
图3 清华大学“全量子网络”项目
我们讲一下清华大学所做的工作——启动一个“全量子网络”项目（见图3）。这是一个973的项目，是我们中国的基础研究项目。我们想理解并建立计算机方面的全量子网络。计算机下一步就是发展量子计算机，有互联网的话，下一步就是量子的互联网，这是一种可能性。
量子网络引起学术界的兴趣，此外还具有现实意义：它并不只是量子互联网，还要建立量子计算机。设想一下如何建立超级计算机：在全球小的计算机很多的情况下，将其重新构建网络，如果做得正确，基础的架构就变成了一个超级计算机。同样的道理，在我们量子计算机上也是一样。我们一开始建立比较小的量子计算机，就是构建小的量子计算机的节点，然后将节点连接起来，利用量子网络连接，就变成一个可扩展的、庞大的量子计算机网络。最起码的理念是这样的，行业中的很多人（包括我们）都非常赞同这样的观点。对于量子计算机来说，可以把一个光子的流程发过来，流程就有可能增加距离，使用我们量子的中计网络，从而扩展到距离非常远的网络。
戴维德•维恩兰德（David Wineland）是这个领域的前沿研究者之一，他的团队采用著名的Ion Trap技术，建立大规模的量子网络。这是有可能使用的技术，划分的愿景和小的节点，在我们量子的网络节点上用光交换机加以连接，形成网络，再用Ion Trap寄存器连接起来。这里面有很多的实验结果。传统计算机里面一旦有这个理念，即可以将其连接起来建立大的量子计算机。听起来非常简单，我们需要在量子的地方加上存储、通信的比特，所有的点都需要大量的论证才能够变成现实。这样就有可能在存储和通信方面进行转换，需要大量的努力。这都是示意图（见图4），我们可以看到，科学界中每一个步骤、每一个小进展都会带来很多自然科学杂志的评论。
图4 David Wineland团队建立量子网络
最后总结一下，回到我们最基本的主题上，就是伟大的科学经常在什么时候发生？经常在我们的科学的学科能够发生互动的时候，特别是出现颠覆性的新技术已经成为现实的时候。我们的量子计算也面对着如此乐观的环境。我们相信，量子计算是一个非常好的科学，它应该是一项伟大的科学。
什么是伟大的科学？我们探讨一下。不同的人定有不同的定义，但应满足两个标准。第一，它必须有巨大的、深远的影响。举个例子来说，我们构建量子计算机，或者是最原始的初级计算机，并不仅仅出于我们的好奇和探索，它可以做伟大的事情，可以使我们有能力做量子的模拟，可以帮助我们区别不同的物理层的理论。而目前还不能做到这一点，是因为我们不能模拟量子的理论并在未来设计出新的材料。第二，它必须要能够提升人类的精神，能够让生活变得非常愉快，而不是受到约束。未来人类最需要就是这样的精神，使幸福来自很多方面，包括知识和科学的理论。
量子计算机的发展对于量子科学而言是一个很大的贡献。物理学家告诉我们：全球都是由物理组成的。日常生活中看来微小的电子、原子等，跟很多无形的晶体组成了我们共同生活的世界，而我们跟它们有不同的沟通。一百年以前，我们最终意识到它们的存在，实际上也开始学习它们的语言，这种语言叫做量子力学语言（但目前还不能达到，所以有些奇怪的行为仍旧无法解释）。过去二十年，我们的技术发展到这个程度。我们现在做量子的计算，设计量子计算机来说，可以将我们所有的小朋友汇聚起来，跟他们说悄悄话：你们能够为我跳舞么？当它们跳完舞离开之后，留下的痕迹（例如大合数的分解方案）就是让我在量子计算领域最兴奋的地方。所以我想说明，我的观点——量子计算是一项伟大的科学——被证明了。谢谢各位！
超越纳什均衡：21世纪的解决方案概念——记Joseph Halpern“21世纪计算”大会主题演讲
微软研究院将梦想变为现实的20年——记Rick Rashid“21世纪计算”大会主题演讲
模型检验和维数灾难——记Edmund M.Clarke“21世纪计算”大会主题演讲
___________________________________________________________________________________
欢迎关注
微软亚洲研究院人人网主页：http://page.renren.com/600674137
微软亚洲研究院微博：http://t.sina.com.cn/msra