新浪科技《科学大家》撰文

姚期智世界著名计算机学家，年图灵奖得主，中国科学院院士，美国科学院外籍院士，清华大学交叉信息研究院院长姚期智——量子计算科学(上)量子计算已经出现在公众的视野中很久了。尤其是最近几年的发展，量子计算机似乎即将成为现实。但是量子力学对外行人来说是非常陌生的，甚至很多的计算机科学家，他们仍认为量子计算很神秘。他们也很难理解一些简单的问题，比如：量子计算到底跟经典计算有什么不同？它强大的计算能力从何而来？量子计算机的本质是怎么？它强大的计算能力从何而来？在十九世纪，经典物理学认为，世界上的所有物质可以分成两种类型，一种是粒子，你可以把它想象成棒球或者网球，它很坚硬且有弹性，处在特定的位置上。另一种是波，比如我们看到湖中的水波，另外像我们看到的光，或者叫“光波”，也是波现象的一个例子。这就是经典物理学对物质的解释。当时的科学家对这套理论非常满意。他们认为这套理论可以解释自然界的一切。然而到了二十世纪，当时的科学家们突然发现，整个世界并不是我们肉眼所看到的那样。经典物理模型有可能是错误的。他们发现，如果去观测一个很小的物体，比如原子、电子或者光子它们同时具有粒子和波的特性。人们看到的到底是粒子还是波，取决于我们的观测方式。通俗的讲，就好比《JekyllandHyde》的故事（编者注：英国作家Stevenson的的经典小说，书中主角有人格分裂。现多指由两种不同面目的人）。我不确定中国朋友是否熟悉这个故事。杰克是一个好人，海德是一个坏人。但大家都知道，他们实际上是同一个人的双重人格。爱因斯坦在年发表了一篇著名的论文，他提出：光不仅仅只是波实际上，光在特定条件下表现得像粒子。所以到目前为止，物理学家根据量子理论认为，宇宙中所有的物质都具有这种双重属性。即每个物体都具有两面性。一面是粒子的特性，一面是波的特性。物理学家给它起了一个非常好听的名字，就叫做波粒二象性。它告诉我们，世界上所有物质的真实面貌，跟我们肉眼观察到的是不一样的。他们实际上既有粒子的性质，同时又有波的性质。在量子理论中，这是物质的基本性质之一这种性质非常有名。所以波粒二象性对量子计算来说是非常重要的。量子计算机Vs经典计算机在年，Turing提出了图灵机这个概念，他也是计算机领域的伟大先驱者。在年之后的很多年，图灵及一些其他先驱者都认为，他们已经解决了计算理论的所有问题。他们觉得自己找到了一个非常完美的，或者说是唯一的计算模型。之后的很多年，大家都抱有同样的想法。但是自二十世纪六七十年代起，一些极具创新精神的科学家们开始思考计算的本质。他们重新审视计算这个概念，思考像计算过程中需要消耗多少能量等问题。之后沿着这个思路，一些科学家也在思考，利用量子理论进行计算的可能性。其中有一个科学家为此贡献良多，他就是CharlesBennett，他也是量子计算的先驱之一。对量子计算领域来说，也许最重要的一个工作是费曼在年做出的工作。他实际上提出了两个问题，第一个问题是：经典计算机是否能够有效的模拟量子系统？对计算机科学家来说，这是一个非常重要的问题。我们高度使用经典计算机，去计算和解释物理现象，并且实际上，计算效果确实非常好。这是因为经典物理现象都能用微分方程进行描述，而恰好经典计算机非常擅长解决这类问题。在很多领域，经典计算机都能非常好的模拟物理系统。但是费曼思考的是，如果不仅仅考虑经典物理，而且考虑量子物理的情形。虽然在量子理论中，仍用微分方程来描述量子系统的演化，但变量的数目却远远多于经典物理系统。如果你仍然想用经典计算机来模拟量子系统，即用经典计算机模拟经典系统的老思路，那么你需要指数级来增加时间才能完成模拟。所以费曼提出了这个问题而费曼的结论是：这是不可能的。因为目前没有任何可行的方法，可以求解出这么多变量的微分方程。然后，他提出了另一个问题，这是一个非常重要且极具创新性的问题：“如果我们放弃经典的图灵机模型，是否可以做得更好？”我认为没有计算机科学家这么想过，但是物理学家会这么思考，因为他们不是计算机科学家。费曼正是如此，他从物理学家实用主义的角度来思考这个问题。他说：“好吧，让我们看看我们能做些什么，如果我们不能以标准的方法去做，是否有新办法可以解决这个问题，从而获得正确答案？”他问道：如果我们拓展一下计算机的工作方式，不是使用逻辑门来建造计算机，而是一些其他的东西，比如分子和原子，如果我们使用这些量子材料，它们具有非常奇异的性质，尤其是波粒二象性。是否能建造出模拟量子系统的计算机？”于是他提出了这个问题，并做了一些验证性实验。然后他推测，这个想法也许可以实现。那么量子计算机和经典计算机有何本质区别呢？经典计算机本质上来说，你有一些数字串或者比特你将其作为输入，用经典计算机对它进行计算，然后获得输出结果，经典计算机就是通过数字逻辑来进行运算。而作为对比，量子计算机是由量子材料建造而成。你也可以输入量子比特，输入比特的状态用状态空间中的态矢表示。所以一种特殊情形是，它可以表示经典的0和1。但是实际上它可以表示更多的状态。让我们通过类比来理解它们之间的差别。假设你现在需要计算一个问题，首先你需要正确的表示这个计算任务，把它输入到量子计算机中，然后在特定的时间，你需要执行测量操作，获取测量结果，这个结果就是你需要的输出结果。我认为很重要也很有趣的一点，在量子计算机和经典计算机的区别中，就是很多年前人们认为模拟电路已经过时了。尽管模拟信号是电子工程师的最爱他们有了电压信号和电流信号后，就能利用这些信号进行信号处理。但当数字计算机普及之后，我们就把那些模拟设备扔进了垃圾堆里。因为我们没有必要再去使用它们。因为数字信号处理，可以更稳定、更可控，而模拟信号处理则很难精确控制。可是如果我们使用量子计算机的话，那么就又回到了模拟信号处理上。量子计算机只在计算过程的最后时刻，即执行测量操作获得测量结果时，才会将模拟信号变成数字信号。经典计算机通过操纵经典比特进行布尔运算，类似的，量子计算机是操纵量子比特。这些量子比特处在一个更大的状态空间中，量子操作本质上就是去旋转它们。现在我们来具体对比经典计算机和量子计算机的区别，用经典计算机去操纵n个比特，它有2^n种可能的状态，然后经典计算机对比特状态进行不断的映射。而如果用量子计算机去计算，比特的状态空间会更大，它的维度是一个复数C^2^n。如果你不熟悉复数，就把它当作一个欧几里得空间，只不过维度将指数级增大到C^2^n。所以利用这个特点，量子计算机可以做一些经典计算机无法完成的事情，因为量子计算机有更大的状态空间。而量子计算机对量子比特的旋转操作，完全不同于经典计算机对经典比特的排列操作。这个特点是量子计算机的另一个巨大优势。所以到目前为止，我介绍了经典计算机和量子计算机中的基本概念，但我不会详细介绍量子计算机中的旋转操作，它们实际上叫做幺正变换。过于专业的解释会让你们感到迷惑，所以忘掉它，就理解成旋转操作。所以理论上，量子计算机有更大的状态空间去处理问题。神秘的量子计算机如果一个人问量子计算科学家“量子计算机的奥秘到底是什么？为什么是它量子计算机如何加快计算速度的？”我认为可以这样回答：因为量子比特表示的不只是一个确定的状态，而是各种状态概率性的叠加。就比如著名的薛定谔的猫，这只猫实际处在活猫和死猫的叠加态。这是一种很特殊的状态，因为你不能说它是只死猫，也不能说它是只活猫。但是你知道它有多大概率是活的，多大概率是死的。这是非常诡异的一种状态。所以，如果你能用叠加态来表示事物的状态：即同时表示猫是生或死的状态。如果你真可以这样做的话，直观上理解就是，你具备了并行计算的能力。我们知道对许多计算问题来说，它们有很多不同的解。你需要遍历搜索每一个解，去查看哪一个是你想要的正确答案。现在假设你有一台理想的并行计算机，您可以使用非常多的处理器进行并行搜索。原则上，你可以大大加快运算速度。因此我认为你可以这样回答那个问题，量子计算机的超强计算能力来自于它的并行搜索能力。正是这种量子并行性使得量子计算机如此强大。我很想用潘建伟教授提过的比喻来向你们解释这种特性：在中国的神话故事中，有一个美猴王叫孙悟空。它有一项本领：可以变出许多个自己。它只需要拔下一根汗毛吹一下，就能变出一个一模一样的自己。量子并行性就相当于所有这些猴子在同时进行搜索。量子计算机就是拥有这种神奇的能力，来进行快速的并行搜索。但是我们需要注意这只是个比喻。它确实是真的，量子叠加态这种特性确实使并行搜索成为可能。但是，当你去查看所有的经典算法时你找不到利用这种量子特性进行并行搜索的算法。因此，它本身并不是一个真正意义上的答案。而我们要做的就是给你展示一个真正显示量子算法加速能力的例子在这个例子中，你将看到量子并行性在哪里起作用。打造一台量子计算机难度在哪？自年以来，科学家已经取得了巨大进步，在量子算法的设计和实现上做出了很多利用量子特性加速计算的工作。我们知道在现代密码学中，有许多密码系统用来保护信息，它们利用大数分解来进行加密。现在如果我给你一个位的数字，事实证明你很难直接分解出它的因数。两个数的乘法很容易，如果把两个位的数相乘，你可以很快的计算出结果。如果用计算机来计算的话，甚至会更快。但是一个位的数字，让你计算出它的两个因数，你很难解出来。但事实上有个量子算法能解决这个问题，它是由PeterShor在年提出，已经被证明量子计算机能够非常快速的分解大数。有很多方法可以估计量子计算机运行该算法的时间。一种估计是，如果你使用超级计算机来分解一个位的数字，大概需要60万年。但如果你用量子计算机来计算，假设我们已经有了一台合适的量子计算机，你只需要几个小时甚至几十分钟就能完成计算。所以PeterShor的这个量子算法，也许是最著名的量子算法。但这并不是唯一重要的量子算法。大数分解算法对破解加密系统非常有用但是也有许多其他的重要算法，其中一个便是费曼的问题：“量子计算机否能够模拟量子系统？”事实上到目前为止，已经证明，量子计算机能解决许多种问题，用量子计算机也确实可以模拟许多量子系统。现在尤其是可以利用量子计算机去模拟特定的量子系统，从而可以在许多问题上取得进展，比如新材料的开发，以及新药物的研制等。所以，量子计算机将会产生巨大的影响。此外还有一些经典的非线性优化问题以及机器学习，人工智能相关的问题量子计算在一些相关的领域也非常有用比如量子通信和量子密码学。CharlesBennett和GillesBrassard做出了许多著名的工作，他们是这个领域的伟大先驱。此外，潘建伟教授是这个领域中实验方向的杰出领导者之一，我认为像墨子号量子卫星是一个非常伟大的成就。正如我前面提到的，“为什么量子计算机这么强大？它是如何做到的？”外行仍然不能理解。8.27姚期智——量子计算科学（中）量子计算机如何能加速计算？所以我现在要谈到问题的核心：量子计算机是如何加速计算的？我接下来将介绍这个著名的量子算法：由PeterShor发明的大数分解量子算法。PeterShor的这个算法是非常数学化的，所以我将以不同的方式呈现它。实际上这个经典算法本身很有趣，因为它涉及到一些著名的先驱科学家的工作。它也确实是由一些著名的物理学工作启发而成。这个物理或者化学分支，叫做X射线晶体学。这个著名的工作起源于Roentgen在年的发现，他偶然发现了一种他称之为X射线的神秘现象。这是一个新奇的东西。人们很难确定它是一个粒子还是一个波。无论如何，Roentgen因发现X射线的工作中而得到了认可。他在年获得了第一届诺贝尔物理学奖。在年，vonLaue分析了这个问题，X射线到底是粒子还是波？他提出一个很棒的想法：把X射线照射到像盐这样的晶体上。他设法得到一个衍射图案。按照当时的科学理论水平，如果能得到衍射图案，那就证明它肯定是波。因为粒子不会相互干涉。但故事没还有结束。我认为vonLaue值得获得诺贝尔奖，但接下来还有更棒的发现。年，Braggs父子推导出了衍射现象的数学公式。想想，你如何解释衍射图样？用怎样的数学公式才能解释它。这个工作意义重大。一旦你能用数学公式来分析和预测，那么你就能运用在实验中。假设你有一个未知结构的晶体，你拍摄了一些x射线照片，也许从各个角度都拍摄了。现在根据数学公式，你甚至可以恢复出晶体的结构。这真是个好办法。你只是拍了张照片，然后就能恢复出晶体的结构。这个方法是非常成功的，因为接下来的许多年由它又产生了许多诺贝尔奖。事实上，科学家们后来变得更有野心。因为最初的数学公式很粗糙，你只能分析非常简单的东西，比如无机材料分子。但后来，可以逐渐分析更复杂的生物大分子。科学家们找到了分析它们的方法，并确定了这些蛋白质的结构，所以通过非常简单的思路，却可以做很复杂的事情。如果你使用X射线，即这种光波，对一些东西拍照，你就可恢复出这些东西的结构。用我们计算机科学的语言来说，你可以计算出被研究对象的一些秘密所以这是智力上的一大飞跃。类似的如果我想分析一个整数，有没有办法让我拍一张整数的X光照片？当然，如果你写下这个数字，然后用X射线照射它，我想你就回到了我前面刚开始讲的地方。即你需要根据这个整数来构造一个晶体，然后用X射线去照射它。第一步就是设计出这个经典算法，而我们正在设计的就是这种光学算法。但由于它是经典物理学范畴，我们可以用经典计算机来模拟它。所以它是一个经典算法。然后想象一下用X射线去给这个整数N拍照不过首先你需要足够聪明地去构造出一个晶体然后你用X射线去拍照，看一下衍射图案当然也许你需要多试几次接着你分析照片，就可以得到这个数字的因数实际上这是可以完成的，尽管里面涉及到一些复杂的数学。这基本上就是图像化的去理解这个经典算法即你有一个整数需要因数分解，然后你做一个光学实验通过衍射图案就能分析出结果现在问题是这个晶体的体积非常巨大。如果你想天真的去建造这个晶体，我认为整个银河系，甚至整个宇宙都不够大。现在进入下一步，也是最关键的地方。第一我们实际上不需要整张照片因为传统上你去照X光，医生会看到整个底片，但我们不需要。实际上我们只需要几个样本点就够了，并不需要指数级的样本数。我们只需要多项式量级的样本数，这就是进步之处。现在的问题是如何去采样？即使是采一个样本点？也是很困难的。因为如果你取一个样本进行计算，你需要对指数多的项求和。所以，如果你使用经典算法来计算，它仍然很难。但是指数多的项求和是非常结构化的，如果你用一种聪明的方式去计算即如果你有一台量子计算机，那么你可以使用量子傅里叶变换来进行计算。打个比方，你可以使用前面提到的孙悟空的那种本领。这样你就可以进行并行搜索，并指数级的节省时间。这对采一个样本点意味着什么呢？现在就是最精彩的地方了，波粒二象性将会起作用了。通常当你拍一张X光照片时，有许多X光的光子穿过你的身体。但是假设X光越来越弱，直到最终每次只有一个光子能通过装置。波粒二象性告诉我们，即使只有一个光子，仍然能通过它。事实上，一个光子通过装置后的概率分布将与经典情形相同，这样你就会得到完全相同的分布。因此如果我能采样，只需要发射一个光子并探测光子着陆的位置。你看，关键之处在于只需要一个粒子然后探测光子通过晶体后的位置分布。当你测量它们时，它们只能在处在一个位置。因此，这个样本点包含了整个晶体的信息。因此，最终的结果是把这些组合在一起，得到一个多项式运行时间的量子算法。姚期智——量子信息科学（下）量子计算机未来可期用于量子计算的技术手段最初可能有二十种左右，都是用于构建量子比特的基础单元，但是许多年之后似乎只有一些方案更有希望。如果你

转载请注明:http://www.aideyishus.com/lkcf/5848.html