【视频】量子计算机是如何加速计算的？ | 姚期智

姚期智

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

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

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

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

文字版·英文

Okay, And now, since 1981, there has been a lot of progress in designing quantum algorithms and thinking about implementation, so that there's a lot of work on how to utilize quantum power. And for example, I want to specifically mention a particularly famous and striking example namely that we know that in modern cryptography, there are many crypto systems to protect secrets. They would use something related to factoring of large integers.

And now if I give you, say, a 400-bit -- a 400-digit integer, it turns out to be extremely difficult to factor it. So we all know that multiplication is easy. If you multiply two 200-digit numbers, I think that you can do it very fast, and certainly with a computer, you can do it really fast. But if I give you a 400-bit … digit number, and ask you where are the two factors, and you will have difficulty doing it.

And now this problem turns out to have a quantum algorithm, proposed by Peter Shor in 1994. And it's been proved that a quantum computer will be able to factor it much faster. So there are many ways to estimate what the running times are of the quantum computer and so one estimate saying that if you today want to factor at 400-digit number on the supercomputer, it would take 600,000 years.

But if you do it on a quantum computer, and when a suitably sized quantum computer is available, ok, then you can do it in a few hours, and possibly minutes. So Peter Shor’s algorithm, it's probably the most famous quantum algorithm.

But that's not the only quantum algorithm that is actually important. I mean, the factoring is great for crypto-code breaking, but there are other things actually related to. One of the questions from Feynman: If you have quantum computers, can you simulate quantum systems? 

And it turns out for by now, there are large classes of problems people have proved, that it's possible to simulate many quantum physical systems with the quantum computer.

And now, in particular, if you really have very powerful quantum computers to simulate physical systems, you would be able to make progress on problems such as the design of new materials, or the design of drugs, and so on. And so it would have enormous potential impact. And there are things that are actually pretty classical type of nonlinear optimization, and also there are things related to problems in machine learning, and AI, Quantum computing is in addition very useful in related fields, like in quantum communication and quantum cryptography. I think it's a subject that the QCrypt conference is devoted to.

So this would relate to things like unbreakable codes and many other cryptographic operations using quantum operations. And now, I think that it's fit to point out that we have some of the originators of the field and also great system builders here.

Ah, I think that the famous work by Charles Bennett and Gilles Brassard is really the kind of the people who pioneered the whole field. And professor Jian-Wei Pan is a person who is really one of the leading experimental system builders in this area. I think including the Micius satellite. I think this is among the great achievements.

And now, as I mentioned the very beginning the “how” and “why” of quantum computer remain mysterious to outsiders. And so now we're going to the heart of the matter. Let's see that how quantum power can be used to speed things up. And actually, we are going to look at this famous quantum algorithm for doing a factoring by Peter Shor.

Peter Shor’s algorithm is very mathematical, so I’m going to present it in a different way. And so, kind of hide all the mathematics, but doing things in a more conceptual way. So I’m going to do it in two steps. In the first step, I'm going to describe an alternative classical algorithms to the standard factoring algorithms that a number of theorists are doing.

So we're going to design a classical algorithm to solve this problem. And unfortunately, this classical algorithm would also run in exponential time. However, this algorithm is going to have the advantage where if you look at it and if you think about the essence of quantum mechanics, you'll be able to simulate it with a quantum computer, with the exponential speedup.

And so therefore, we’re going to do a two-step thing. First, we're going to design a classical algorithm, and the second part is that we're going to show the quantum power is enough to simulate how this classical algorithms is used.

And the wave-particle duality is going to come in at the second stage. And now, actually, this classical algorithm itself is really interesting because it has some famous forerunner because it's really the descendant of some very famous work in physics. And this branch of physics or chemistry, is called x-ray crystallography.

Okay, it's using x-rays to take pictures like you know, that we take chest x-ray pictures to see whether there is any disease. Or when you hurt your leg, you take x-ray pictures to see whether the bones are intact or not.

Okay now, this very famous line of work starting in 1895 with Roentgen, who accidentally discovered a mysterious phenomenon which he termed x-rays. Okay, and it's a novel thing. People had difficulty determining whether it's a particle or a wave. And, but in any case Roentgen got recognized by his work in discovering the x-ray. And he actually was the first Nobel Prize winner in 1901 of the physics prize

And now in 1912, von Laue solved the problem, resolved the problem, whether an x-ray is a particle or a wave. And von Laue, he had this great idea by shining the x-ray through crystals like salt and so on. And he managed to get a diffraction pattern. And I think according to the standard of the time, if you can get diffraction pattern, then it has to be wave because particles, they don't interfere with each other.

Now that's not the end of the story. I think it's fine for von Laue to receive a Nobel prize for his work, but there are better things to come. In 1913, the Braggs, father and son team, they derived a mathematical formula for the diffraction pattern. To see that, well, how do you explain the diffraction pattern. Well, the mathematics using optics, then you can do it. And, this has a very big implication.

Once you have the ability to use mathematics to analyze and make predictions, then you can use it in reverse I mean suppose you have a crystal of unknown structure, and you take some x-ray pictures, maybe many of them from different angles and so on.

Now, you look at the mathematics, sometimes you will be able to recover what the crystal structure must be like. That's a great thought. That you look at …… you take a photo of something, and you come back to figure out what's the secret of the crystals.

And this is immensely successful and it used many, many Nobel prizes in the next fifty years. And, actually, they get more and more ambitious. You can, initially, because the math formula is pretty messy, so you can only analyze very simple things, like inorganic material molecules but later on, even very large molecules of importance to biology, people found ways of analyzing them and determining the structure of these proteins and these structures.

So very complicated things you can do, by this simple idea. And so now let's summarize what we have done so far. What we have discovered is that if you use the x-rays, I mean this is light wave. If you use it and you take pictures, you can recover. Or in our computer science mind, you can compute a function of the object, some secret of the object. So now the question, this would be an intellectual leap in saying that if I look at an integer, is there a way for me to take an x-ray picture of the integer?

Of course, if you write the bits, you put an x-ray through it. I think you would just get exactly back what you start with. So, you have to build a crystal somehow, based upon this integer. And then you take x-ray threw it. And perhaps you will be able to do it. So the answer is yes, the kind of the first stage is to design this classical algorithm. And now we are designing really an optical algorithm. But, since it's classical physics, if it's classical physics, I can simulate it with the classical computer. So it will be a classical algorithm. Okay.

So, let's just imagine that we're taking this x-ray photo of the integer N and first we……there is some way …… you have to do it smartly, in order to grow a crystal. And then you have this x-ray on it. And look at the diffraction pattern, maybe you have to do it several times.

And you figure out, you examine the photo and you figure out what this factor is. This can actually be done. There's kind of messy mathematics in it, but this actually can be done.

And so this is basically the pictorial way of seeing it. You have this integer. You kind of do an optical experiment. You look at the pattern and you see what it is. And now the problem is that the crystal is of enormous size. So essentially, if you do the naïve thing, build this crystal, I think the whole galaxy, and maybe the whole universe, will not be enough to support this experiment.

And now come to the next stage. So now here's the critical observation. The first one is that we don't need the whole photo. Because classically, you take an x-ray, the doctor will see the whole negative, and then look at it, but we don't need that. Actually, we only need a few sample points. So we don't need exponential number of samples. We only need a polynomial number of samples. So that's progress.

Now, how do you take samples? Even taking one sample, It's sort of difficult, because if you look at taking one sample, the calculation you do, it's the sum over an exponential number of terms. So if you use the classical algorithm to do it, it's still hard. But that exponential sum is very structured. So that if you use a clever way to do the (computation) if you have a quantum computer, you can do something called the quantum Fourier transform, if you have quantum (computer), you can do the trick of the monkey king.

So that you can do the kind of parallel search, and do it with an exponential amount of saving in terms of time. Ok, now, what does it mean to take one sample? And now here comes the punch line, where the wave-particle duality comes in. Taking one sample means that, usually when I take an x-ray picture, there are many x-ray photons are going through your body and so on.

But suppose you make a light to be dimmer and dimmer until eventually there's only one photon at a time that can go through the apparatus. And now the wave-particle duality is saying that even though it's just one photon, one particle going through it, that actually, the probability distribution will be identical to the classical one. So that you are going to have exactly the same distribution, so if I can sample, just do it for one photon, and detect where the photon lands.

And you see that the critical point is that when it’s a particle. And then you can talk about I want to detect where the photon will land. When you measure them, they can only land in one place. So you get a very definitive sample point of the whole thing. So, the net result is that you combine these together, you get a quantum algorithm, of a kind of polynomial running time.

I think that's the kind of summary of the main part that the main point I want to make that where does the quantum power come from? It's no more mysterious than the mystery of quantum physics.

🔽点击查看往期内容

想要和更多志同道合的人一同讨论科普问题，获得墨子沙龙小秘书贴心服务，及时获取各类科普活动通知吗？扫码加墨子沙龙小秘书，拉你入墨子沙龙超大群。

墨子沙龙是由中国科学技术大学上海研究院主办、上海市浦东新区科学技术协会及中国科大新创校友基金会协办的公益性大型科普论坛。沙龙的科普对象为对科学有浓厚兴趣、热爱科普的普通民众，力图打造具有中学生学力便可以了解当下全球最尖端科学资讯的科普讲坛。

关于“墨子沙龙”