用微信扫码二维码

分享至好友和朋友圈

姚期智

中国科学院院士，美国科学院外籍院士，美国科学与艺术学院外籍院士，国际密码协会会士，清华大学交叉信息研究院院长

2017年初，姚期智与物理学家杨振宁放弃美国国籍转为中国国籍。

自从2004年辞去普林斯顿大学终身教职回国后，姚期智始终活跃在教育第一线，他主导并与微软研究院共同合作，在清华创办了如今大名鼎鼎的「姚班」，培养出了一大批中国计算机科学的顶尖人才，其门生遍布国内外 AI 产业和计算机科学研究的各个关键领域。

2010年，姚期智还创立了清华交叉信息研究院，信息科学与多个学科在这里交叉互动，成果叠出，以开疆辟土的恢弘气势填补了国内计算机科学在该领域的空白地带，为世界学术瞩目。

视频

文字版·中文

自1981年以来，科学家已经取得了巨大进步, 在量子算法的设计和实现上。做出了很多利用量子特性加速计算的工作。比如说, 下面我会举一个非常著名的量子算法例子。我们知道在现代密码学中，有许多密码系统用来保护信息。它们利用大数分解来进行加密，现在如果我给你一个400位的数字，事实证明你很难直接分解出它的因数，我们知道两个数的乘法很容易，如果把两个200位的数相乘，你可以很快的计算出结果。如果用计算机来计算的话，甚至会更快。

但是我给你一个400位的数字，让你计算出它的两个因数，你很难解出来。但事实上有个量子算法能解决这个问题，它是由Peter Shor在1994年提出。而且已经被证明，量子计算机能够非常快速的分解大数。

有很多方法可以估计，量子计算机运行该算法的时间。一种估计是，如果你使用超级计算机来分解一个400位的数字，大概需要60万年。但如果你用量子计算机来计算，假设我们已经有了一台合适的量子计算机，你只需要几个小时甚至几十分钟就能完成计算。所以Peter Shor的这个量子算法，也许是最著名的量子算法。但这并不是唯一重要的量子算法。

我的意思是，大数分解算法对破解加密系统非常有用，但是也有许多其他的重要算法，其中一个便是费曼的问题：“量子计算机否能够模拟量子系统？” 事实上到目前为止，已经证明,量子计算机能解决许多种问题，用量子计算机也确实可以模拟许多量子系统。

现在尤其是，可以利用量子计算机去模拟特定的量子系统，从而可以在许多问题上取得进展，比如新材料的开发，以及新药物的研制等。

所以，量子计算机将会产生巨大的影响。此外还有一些经典的非线性优化问题，以及机器学习，人工智能相关的问题。

量子计算在一些相关的领域也非常有用，比如量子通信和量子密码学。我认为这也是Qcrypt会议讨论的议题。这涉及到像使用量子计算来破译密码，以及其它的加密解密操作。

现在我认为这是一个合适的时机去介绍一下，这个领域的一些先驱者和开创者。坐在台下的Charles Bennett 和 Gilles Brassard做出了许多著名的工作，他们是这个领域的伟大先驱。此外，潘建伟教授是这个领域中实验方向的杰出领导者之一，我认为像墨子号量子卫星是一个非常伟大的成就。

正如我前面提到的，“为什么量子计算机这么强大？它是如何做到的？” 外行仍然不能理解。所以我现在要谈到问题的核心。量子计算机是如何加速计算的？我接下来将介绍这个著名的量子算法：由Peter Shor发明的大数分解量子算法。

Peter Shor的这个算法是非常数学化的，所以我将以不同的方式呈现它。我会略过高深的数学表达，以更概念性的方式来讲解，因此我会分成两步来介绍Shor算法。

在第一步中，我将描述一个经典算法来替代大数分解算法，即我们设计了一个经典算法来解决这个问题。不幸的是，这个经典算法需要消耗指数级多的时间，但是这个经典算法也有好处，它可以帮助你理解量子力学的本质。你可以用量子计算机模拟它，并获得指数加速。

因此我们将分成两步，第一步我们要设计一个经典算法，第二步我们将展示量子计算机足够强大去模拟经典算法，波粒二象性会出现在第二步中。

实际上这个经典算法本身很有趣，因为它涉及到一些著名的先驱科学家的工作。它也确实是由一些著名的物理学工作启发而成。这个物理或者化学分支，叫做X射线晶体学。它是用X光来拍摄照片，就像我们拍胸部X光照片看是否有任何疾病。或者当你的腿受伤时，你会拍X光照片看骨头是否受伤。

这个著名的工作起源于Roentgen在1895年的发现，他偶然发现了一种他称之为X射线的神秘现象。这是一个新奇的东西。人们很难确定它是一个粒子还是一个波。无论如何，Roentgen因发现X射线的工作中而得到了认可。他实际上在1901年获得了第一届诺贝尔物理学奖。

然后在1912年，von Laue分析了这个问题，X射线到底是粒子还是波？他提出一个很棒的想法：把X射线照射到像盐这样的晶体上，他设法得到一个衍射图案。按照当时的科学理论水平，如果能得到衍射图案，那就证明它肯定是波。因为粒子不会相互干涉。

但故事没还有结束。

我认为von Laue值得获得诺贝尔奖，但接下来还有更棒的发现。1913年，Braggs父子推导出了衍射现象的数学公式。想想，你如何解释衍射图样？用怎样的数学公式才能解释它。这个工作意义重大。一旦你能用数学公式来分析和预测，那么你就能运用在实验中。

假设你有一个未知结构的晶体，你拍摄了一些x射线照片，也许从各个角度都拍摄了。现在根据数学公式，你甚至可以恢复出晶体的结构。这真是个好办法。你只是拍了张照片，然后就能恢复出晶体的结构。

这个方法是非常成功的，因为接下来的许多年由它又产生了许多诺贝尔奖。事实上，科学家们后来变得更有野心。因为最初的数学公式很粗糙，你只能分析非常简单的东西，比如无机材料分子。但后来，可以逐渐分析更复杂的生物大分子。科学家们找到了分析它们的方法，并确定了这些蛋白质的结构。

所以通过非常简单的思路，却可以做很复杂的事情。现在来总结一下我们做了什么。我们发现如果你使用X射线，即这种光波，对一些东西拍照，你就可恢复出这些东西的结构。用我们计算机科学的语言来说，你可以计算出被研究对象的一些秘密，所以这是智力上的一大飞跃。类似的如果我想分析一个整数，有没有办法让我拍一张整数的X光照片？

当然，如果你写下这个数字，然后用X射线照射它，我想你就回到了我前面刚开始讲的地方。即你需要根据这个整数构造一个晶体，然后用X射线去照射它。也许你能做到这一点。答案是肯定的。

第一步就是设计出这个经典算法，而我们正在设计的就是这种光学算法。但由于它是经典物理学范畴，我们可以用经典计算机来模拟它。所以它是一个经典算法。

然后想象一下用X射线去给这个整数N拍照。不过首先你需要足够聪明地去构造出一个晶体，然后你用X射线去拍照，看一下衍射图案。当然也许你需要多试几次，接着你分析照片，就可以得到这个数字的因数，实际上这是可以完成的, 尽管里面涉及到一些复杂的数学。

这基本上就是图像化的去理解这个经典算法，即你有一个整数需要因数分解，然后你做一个光学实验，通过衍射图案就能分析出结果，现在问题是这个晶体的体积非常巨大。如果你想天真的去建造这个晶体，我认为整个银河系，甚至整个宇宙都不够大。

现在进入下一步，也是最关键的地方。第一我们实际上不需要整张照片，因为传统上你去照X光，医生会看到整个底片，但我们不需要。实际上我们只需要几个样本点就够了，并不需要指数级的样本数。我们只需要多项式量级的样本数，这就是进步之处。

现在的问题是如何去采样？即使是采一个样本点? 也是很困难的。因为如果你取一个样本进行计算，你需要对指数多的项求和，所以，如果你使用经典算法来计算，它仍然很难。

但是指数多的项求和是非常结构化的，如果你用一种聪明的方式去计算，即如果你有一台量子计算机，那么你可以使用量子傅里叶变换进行计算。

打个比方，你可以使用前面提到的孙悟空的那种本领。这样你就可以进行并行搜索，并指数级的节省时间。这对采一个样本点意味着什么呢？现在就是最精彩的地方了，波粒二象性将会起作用了。通常当你拍一张X光照片时，有许多X光的光子穿过你的身体。

但是假设X光越来越弱，直到最终每次只有一个光子能通过装置。波粒二象性告诉我们，即使只有一个光子，仍然能通过它。事实上，一个光子通过装置后的概率分布将与经典情形相同，这样你就会得到完全相同的分布。

因此如果我能采样，只需要发射一个光子并探测光子着陆的位置。你看，关键之处在于只需要一个粒子，然后探测光子通过晶体后的位置分布。当你测量它们时，它们只能在处在一个位置。因此，这个样本点包含了整个晶体的信息。因此，最终的结果是把这些组合在一起，得到一个多项式运行时间的量子算法。

总结主体部分，我想要表达的主要观点是：量子计算的强大能力来自于什么地方？其实它并没有比量子物理更加神秘。

特别声明：以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布，本平台仅提供信息存储服务。

Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.