女士们先生们， 我很荣幸能够参加这次的墨子沙龙活动。
我要特别感谢Qcrypt会议的主办方， 还有在座的几位朋友，感谢你们的邀请。同时我要特别感谢潘建伟教授， 是他邀请我到墨子沙龙来给大家做一个报告。我知道墨子沙龙对中国的科普事业贡献很大。
还有我也想提一下我的老朋友，两位传奇人物Charles Bennett 和 the Gilles Brassard。感谢他们也能够出席今天的活动。
我将尽力给大家做一个精彩的报告。
量子计算已经出现在公众的视野中很久了。尤其是最近几年的发展，量子计算机似乎即将成为现实。
但是量子力学对外行人来说是非常陌生的，甚至很多的计算机科学家，他们仍认为量子计算很神秘。他们也很难理解一些简单的问题，比如：量子计算到底跟经典计算有什么不同？它强大的计算能力从何而来？
所以今天我报告的目的，是想要向你们解释清楚这两个问题，
在开始之前，我想稍微讲一下背景， 回顾一下量子计算的历史。
在十九世纪，经典物理学认为，世界上的所有物质可以分成两种类型，一种是粒子，你可以把它想象成棒球或者网球，它很坚硬且有弹性，处在特定的位置上。
另一种是波，比如我们看到湖中的水波。
另外像我们看到的光，或者叫“光波”， 也是波现象的一个例子。
这就是经典物理学对物质的解释。当时的科学家对这套理论非常满意。他们认为这套理论可以解释自然界的一切。
然而到了二十世纪，当时的科学家们突然发现， 整个世界并不是我们肉眼所看到的那样。经典物理模型有可能是错误的。
他们发现，如果去观测一个很小的物体，比如原子、电子或者光子， 它们同时具有粒子和波的特性。人们看到的到底是粒子还是波，取决于我们的观测方式。
通俗的讲，就好比《Jekyll and Hyde》的故事（英国作家Stevenson的的经典小说，书中主角有人格分裂。现多指由两种不同面目的人。）我不确定中国朋友是否熟悉这个故事。
杰克是一个好人，海德是一个坏人。但大家都知道，他们实际上是同一个人的双重人格。
爱因斯坦在1905年发表了一篇著名的论文，他提出观点：光不仅仅只是波， 实际上，光在特定条件下表现得像粒子。所以到目前为止，物理学家根据量子理论认为， 宇宙中所有的物质都具有这种双重属性。
即每个物体都具有两面性。一面是粒子的特性，一面是波的特性。物理学家给它起了一个非常好听的名字，就叫做波粒二象性。
它告诉我们，世界上所有物质的真实面貌，跟我们肉眼观察到的是不一样的。他们实际上既有粒子的性质，同时又有波的性质。在量子理论中，这是物质的基本性质之一， 这种性质非常有名。
所以波粒二象性， 对量子计算来说是非常重要的。在我下面的介绍之中，我将向你解释，波粒二象性如何发挥着重要作用，使得量子计算机能够在特定问题下，计算速度远超经典计算机。
我已经讲了很多物理方面的内容， 如果我已经让你们相信了波粒二象性，这是物理学家们深信不疑的，而且目前看起来是正确的，那么你们很容易理解我接下来的内容。我接下来不会使用任何复杂的数学理论。
首先第一部分是这次报告的核心内容， 这是我今天演讲的主要内容，主要包括三个部分。
我将会给大家解释， 为什么量子计算机完全不同于经典计算机，同时也会追溯一下这个概念的起源。
之后我会给大家举一个非常著名的例子，量子计算机在这个例子中的运算速度远超过经典计算机。同时在这部分内容中，我也会给大家解释一下，波粒二象性如何在量子计算中扮演着重要角色。
然后我会给大家简短介绍一下，量子计算机在具体建造过程中的的困难，让你们知道我们现在处在哪个阶段。
最后我会简要总结一下这次报告。
在1936年，Turing提出了图灵机这个概念，他也是计算机领域的伟大先驱者。
在1936年之后的很多年，图灵以及一些其他先驱者都认为，他们已经解决了计算理论的所有问题。他们觉得自己找到了一个非常完美的，或者说是唯一的计算模型。之后的很多年，大家都抱有同样的想法。
但是自二十世纪六七十年代起，一些极具创新精神的科学家们，开始思考计算的本质。他们重新审视计算这个概念，思考像计算过程中需要消耗多少能量等问题。
之后沿着这个思路， 一些科学家也在思考，利用量子理论进行计算的可能性。其中有一个科学家为此贡献良多，他就是Charles Bennett，他也是量子计算的先驱之一，现在就坐在下面。
也许最重要的一个工作， 对量子计算领域来说，是费曼在1981年做出的工作。
他实际上提出了两个问题，第一个问题是：经典计算机是否能够有效的模拟量子系统？对计算机科学家来说，这是一个非常重要的问题。
我们高度使用经典计算机，去计算和解释物理现象，并且实际上，计算效果确实非常好。这是因为经典物理现象，都能用微分方程进行描述。而恰好经典计算机非常擅长解决这类问题。
在很多领域，经典计算机都能非常好的模拟物理系统，但是费曼思考的是，如果不仅仅考虑经典物理，而且考虑量子物理的情形。
虽然在量子理论中，仍用微分方程来描述量子系统的演化，但变量的数目却远远多于经典物理系统。
如果你仍然想用经典计算机来模拟量子系统，即用经典计算机模拟经典系统的老思路，那么你需要指数级增加的时间才能完成模拟。
所以费曼提出了这个问题，而费曼的结论是：这是不可能的。因为目前没有任何可行的方法，可以求解出这么多变量的微分方程。
然后，他提出了另一个问题，这是一个非常重要且极具创新性的问题。
如果我们放弃图灵机模型，我认为没有计算机科学家这么想过，“如果我们放弃经典的图灵机模型，是否可以做得更好？” 但是物理学家会这么思考，因为他们不是计算机科学家。
费曼正是如此，他从物理学家实用主义的角度来思考这个问题。他说：“好吧，让我们看看我们能做些什么， 如果我们不能以标准的方法去做，是否有新办法可以解决这个问题，从而获得正确答案？”
他问道： "如果我们拓展一下计算机的工作方式， 不是使用逻辑门来建造计算机，而是一些其他的东西，比如分子和原子，如果我们使用这些量子材料，它们具有非常奇异的性质，尤其是波粒二象性。是否能建造出模拟量子系统的计算机？”
于是他提出了这个问题，并做了一些验证性实验。然后他推测，这个想法也许可以实现。
现在，我们来看一下量子计算机和经典计算机的本质区别。
经典计算机本质上来说，你有一些数字串或者比特，你将其作为输入，用经典计算机对它进行计算，然后获得输出结果，经典计算机就是通过数字逻辑来进行运算。
而作为对比，量子计算机，是由量子材料建造而成。
你也可以输入量子比特，输入比特的状态用状态空间中的态矢表示。所以一种特殊情形是，但是实际上它可以表示更多的状态。
让我们通过类比来理解它们之间的差别。
假设你现在需要计算一个问题，首先你需要正确的表示这个计算任务，把它输入到量子计算机中，然后在特定的时间，你需要执行测量操作 ，获取测量结果，这个结果就是你需要的输出结果。
我认为很重要也很有趣的一点， 在量子计算机和经典计算机的区别中，就是很多年前人们认为模拟电路已经过时了。他们有了电压信号和电流信号后，就能利用这些信号进行信号处理。
但当数字计算机普及之后，我们就把那些模拟设备扔进了垃圾堆里。因为我们没有必要再去使用它们。
因为数字信号处理，可以更稳定、更可控，而模拟信号处理则很难精确控制。可是如果我们使用量子计算机的话，那么就又回到了模拟信号处理上。
量子计算机只在计算过程的最后时刻， 即执行测量操作获得测量结果时，才会将模拟信号变成数字信号。
经典计算机通过操纵经典比特进行布尔运算，类似的，量子计算机是操纵量子比特。
这些量子比特处在一个更大的状态空间中，量子操作本质上就是去旋转它们，现在我们来具体对比经典计算机和量子计算机的区别。
用经典计算机去操纵n个比特，它有2^n种可能的状态，然后经典计算机对比特状态进行不断的映射. 而如果用量子计算机去计算，比特的状态空间会更大，它的维度是一个复数C^2^n. 如果你不熟悉复数，就把它当做一个欧几里得空间，只不过维度将指数级增大到C^2^n 。
所以利用这个特点，量子计算机可以做一些经典计算机无法完成的事情，因为量子计算机有更大的状态空间。
而量子计算机对量子比特的旋转操作，完全不同于经典计算机对经典比特的排列操作。这个特点是量子计算机的另一个巨大优势。
所以到目前为止，我介绍了经典计算机和量子计算机中的基本概念，但我不会详细介绍量子计算机中的旋转操作，它们实际上叫做幺正变换。过于专业的解释会让你们感到迷惑，所以忘掉它，就理解成旋转操作。
所以理论上，量子计算机有更大的状态空间去处理问题。如果一个人问量子计算科学家，“量子计算机的奥秘到底是什么？ 为什么是它？量子计算机如何加快计算速度的？”
我认为可以这样回答： 因为量子比特表示的不只是一个确定的状态，而是各种状态概率性的叠加。
就比如著名的薛定谔的猫，这只猫实际处在活猫和死猫的叠加态。
这是一种很特殊的状态，因为你不能说它是只死猫，也不能说它是只活猫。但是你知道它有多大概率是活的，多大概率是死的。这是非常诡异的一种状态。
所以，如果你能用叠加态来表示事物的状态。即同时表示猫是生或死的状态。如果你真可以这样做的话，直观上理解就是，你具备了并行计算的能力。
我们知道对许多计算问题来说，它们有很多不同的解。你需要遍历搜索每一个解，去查看哪一个是你想要的正确答案。
现在假设你有一台理想的并行计算机，您可以使用非常多的处理器进行并行搜索。原则上，你可以大大加快运算速度。因此我认为你可以这样回答那个问题， 量子计算机的超强计算能力，来自于它的并行搜索能力。
正是这种量子并行性使得量子计算机如此强大。
我很想用潘教授提过的比喻，来向你们解释这种特性，在中国的神话故事中，有一个美猴王叫孙悟空。它有一项本领：可以变出许多个自己。它只需要拔下一根汗毛吹一下，就能变出一个一模一样的自己。
孙悟空吹毛变猴
量子并行性就相当于所有这些猴子在同时进行搜索。量子计算机就是拥有这种神奇的能力，来进行快速的并行搜索。但是我们需要注意这只是个比喻。它确实是真的，量子叠加态这种特性确实使并行搜索成为可能。
但是，当你去查看所有的经典算法时，你找不到利用这种量子特性进行并行搜索的算法。因此，它本身并不是一个真正意义上的答案。而我们要做的就是，给你展示一个真正显示量子算法加速能力的例子，在这个例子中，你将看到量子并行性在哪里起作用。
文字版·英文
Ladies and gentlemen， it’s a great pleasure to be here. And I would like to thank the organizers of the Qcrypt， I think， including the important friends here. And for inviting me. And also especially I would like to thank professor Pan， he invited me to make this also one lecture in the Micius Salon， which has accumulated a lot of momentum in the popularization of science in China.
And， well， let me also mention two of my oldest friends， the legendary Charles Bennett and the Gilles Brassard. I think that is surely -- I think that， you know， with them here， I'm going to try to give a really good talk. So I think that Quantum Computing has been in the public eyes very very often in the last few years.
And actually， from the activities in recent years， it really seems that quantum computer is on the verge of becoming a reality.
However， quantum mechanics is such a foreign subject. So that outsiders， even for many computer scientists， they still think that quantum computing is a mystery. And they will have a hard time answering simple questions like， “how is quantum computing different from classical computing？ ” And “where does quantum computer get its enormous power from？” And so the purpose of my talk， is that I really want to address this two questions to give you a precise answer on the nature of quantum computer and where does quantum computing get its power from？ And before going on， let me give away the plot a little bit. I'm going to review who the star is in today's presentation.
And we all know that in classical physics in the 19th century， people thought that all the objects in the world， they are of two types. They either are particles， so you can think of it as a baseball， or a tennis ball. It's very hard， it bounces， it occupies particular positions. And the second kind is called waves.
For example， when you look at the water wave on the lake， or if you -- less obviously -- the light that we get， they are called “light wave” was for a good reason， namely that light was thought as being a typical example of a wave phenomenon.
So there are only these two objects in classical physics， and the physicists were pretty happy about it. They thought they understood everything about nature.
But then comes the 20th century， and scientists， physicists， certainly realize that the world is not what it seems. The classical picture is wrong. Basically， they have found out that if you look at tiny objects， like atoms or electrons or photons， they possess characteristics of both particles and waves. So the particle and the wave nature would manifest themselves， depending on in what context you look at them.
So I think that in the layman's language， that we all know the classical story of 《Jekyll and Hyde》. I’m not sure that in Chinese it’s well known. Jekyll and Hyde， one of them is that is a good guy； the other is a bad guy. They are actually of the same person. And people really found out.
Famously， Einstein， in 1905， wrote a paper， in which he established that light is not just a wave. It actually， under certain circumstances， manifests itself as a particle. So， I think that by now， the physicists， according to quantum theory， that every object in the universe actually has this dual characteristic. So every object， it's kind of having two sides. One is the particle side and the other is the wave side. And the physicists have a fancy name for it.
It's called the wave-particle duality. It’s just a fancy name for saying， that the objects in the world. They are different from what we thought， classically. They have both the wave and particle characteristics. So in quantum theory， this is one of the fundamental properties of a quantum object. It's very， very famous. And so， the wave-particle duality turns out to be actually immensely important in quantum computing.
So in our story， I'm going to show you that exactly the particle-wave duality plays the starting role in making it possible for us to do quantum computing faster than classical computing under certain circumstances. So I have talked a lot about physics， if I’ve convinced you the wave-particle duality， is something that physicists believe and it seems to be true， then you will have no problem following what I’m going to say.
So I absolutely will not use any mathematics in this presentation. And the outlines are these talk， we have three parts。the first part is really the central part of this talk. We are going to show you， why quantum computing is a radically different way of doing computation than classical computers. And we’ll trace the beginning of the concept. And then we're going to show you a particularly famous example， where quantum computers can solve problems much much much faster than classical computers.
So it is in this part， we are going to show how the wave-particle duality plays such a prominent role. And then we’ll give a fairly brief survey of the realization problem of quantum computers， just to give you an idea where we are in the engineering side. And then we'll have some concluding remarks.
So， in 1936， Turing raised the concept of a Turing machine. So that really is the forerunner of the computer as we know it today. After 1936 for many many years， Turing himself and other pioneers of the concept of computation thought， they have solved the problem of computation. They thought they have found the ideal way， and actually the only way， of doing computations in the universe. And for many many years， we also believed that.
And but they're starting from the 1960’s and 70’s， people start -- kind of really innovative people – started thinking about some issues about the nature of computation. So they want to re-examine the concept of computation， for example， how much energy， that does it have to do？
And， along that line， some people also start talking about the possibility of using quantum theory to do computation. And actually， one person who has contributed the tremendously to that is Charles Bennett， who is right here， among those pioneers. And perhaps the most influential work that influence the development of quantum computing is the one by Richard Feynman in 1981.
And he asked a question， actually， two questions that， can quantum physics been simulated efficiently but classical computer？ So that's a perfectly reasonable question for a famous computer scientist. It's saying that since we use the computer so much in order to understand and to analyze physics， and the question is that， actually， the classical computer has been really， really successful in analyzing physics. And because the classical physics， they are done by partial differential equations. And the classical computers are very good at doing it.
In many many cases， the classical computers can simulate physical phenomena extremely well. But Feynman is worried about the question of that， if you think about things beyond classical physics， if you go into the realm of quantum physics. so the quantum physics and the quantum equations， they also are some sort of partial differential equations， but they are objects much more complicated than the classical variables.
And so if you want to simulate， along the line of the classical computer simulating classical physics， you’re going to use exponential time， and so on.
So， Feynman asked this question. And I think his conclusion， it’s --that is probably unlikely， because there doesn't seem to be any reasonable way that you can really get a handle on the immense number of variables in quantum equations. And then on a more positive note， he has to ask the question and now that's a very innovative and important question if we give up on Alan Turing， I think that no computer scientist is going to say that， even think about the question --“If you give up Alan Turing can you do better？ ”.
But the physicists can because they are not computer scientists. And so Feynman says that， in the typical physics tradition， that they are very pragmatic. They say that， “well， let's see what we can do If we cannot do it in the standard way， are there ways that we can get around this problem， finding something so that we can get answers， get numbers？”
And so Feynman asked the question that if you enlarge the class of computers， so that the components that you use to build a computer is not just the logic or gates， but something that you could use， including molecules and atoms， if you can use those quantum objects， which are known to have very peculiar properties， in particular， the wave-particle duality are， would you be able to build computers that actually can simulate quantum laws？ So he asked this question and he did some small example then， and he conjectured that， well， this might be true.
And now， let’s take a look at the difference between the classical computer and a quantum computer and the classical computer， in essence， you have some strings， you have digits， you have bits， and you have a string are as input， and you like to transform it， and you want to do computation， and you go through a classical computer.
And a classical computer is something that can perform digital operations. And now in contrast， a quantum computer is a quantum device that are built up in whatever way， with the quantum material， and you can input， representations of the input bits in the physical space. So in particular， it could be just things that represent the binary bits. But in general， it could be something larger.
But let's just stick to the idea that we are comparing oranges with oranges， so that you have something you'd like to compute. You just represent it in the physical space， and you put it go through the quantum device. And at a certain time， you perform the measurement. You look at the outcome of the object， and just see what number you get. And that's supposed to be your output.
And a critical thing that I think in a way is fun， that the quantum device -- different from the classical computer is that for many many years we thought that the analogs are out because you know the analogs were the favorite of the electrical engineers. You know they have voltages， they have currents. They do signal processing using those things.
But when the computers became popular， we thought that those analog devices should be thrown into the garbage can because that we will never have the need to use them again， because making things digital has the advantage of making things more stable and more controllable， and the analog devices are more unruly.
Okay now， but the quantum device if use things that are built from atoms or quantum materials， then suddenly we're coming back to analog devices. It’s only at the very end， when we decide that the computations are over and decided to look at what we get， then we convert it into the digital thing.
And now， what are those devices in the quantum computer is just manipulates the bits with the Boolean operations. And in the quantum device， the corresponding thing is to manipulate the qubits. So these are objects in a big geometric space. And essentially， you do rotations.
Okay， so if you look at comparing the computing devices in the classical case， you do operations on n bits. And also the space is this 2^n strength， you do mappings back and forth. And now in the quantum space， you're actually looking at the much larger， much richer geometric structure and it’s the complex number， C^2^n. And if you don't like complex numbers， just think of it as Euclidean space， except that dimension that corresponds to n bits would be 2^n： exponentially large.
So， now that's the first indication that we might be able to do something that the classical computers cannot do because now we have such much richer， bigger space. And the rotation， it could be very different from just simple permutations of the bits. Ok， so， that gives us hope.
So now basically， I have defined all the concepts of the classical computer and a quantum computer. And I’m not going to – So the rotations are technically， they are called unitary transformations in the space. But it’s going to make us dizzy， So let’s look at it and forget it. So these are operations.
And now， even though that， in principle， it looks like that we have a larger space to work with. Now， if somebody ask a quantum computer scientist， “what's the secret of quantum computing？ why is it？ Can you say more precise （what） the quantum computers do that makes it possible to speed up things？”
And I think here is a typical answer that people would keep in saying that. Well， each qubit represents not a single state， but in some way， a particular kind of probabilistic combination of states and the famous Schrödinger’s cat is saying that a cat could be in a state of superposition of a live cat and a dead cat. And now， this is a particular type of state of matter， so that you cannot say it's a live cat or it’s a dead cat.
But you know it has probability to be dead or alive. And it behaves in very peculiar ways. And so， when you have the power of representation to represent both possibilities at the same time， namely， represent the possibility of the cat being alive or the cat being dead. The basic operation， you can represent it in such a way. It is intuitively that gives you some sense that quantum operations have some potential for doing parallelism.
And we know that， in computational problems， a lot of times what you do is that you have many different possible answers and you would like to search through each one of them， to see which one is the right answer that you want.
If you have a parallel computer and suppose you have ideal parallel computers， you can take as many processors as you want and do a parallel search. Then in principle， you can speed it up a lot during this process. So I think that a popular way of saying that the quantum computer is powerful is that the quantum computer can do parallel search.
So there's this quantum parallelism that makes it possible. And I cannot help but to use a professor Pan’s metaphor saying that I'm explaining to the lay person that you know in Chinese fable， there is this monkey king Sun Wukong. And the monkey is possible to make many copies of himself. Sun Wukong can take a hair， and make it into another monkey， so that you can （be like） all these monkeys to search through all the possibilities. And so， in the way， quantum computers sometimes possess this magical ability so that you can do the search fast.
However， we have to keep in mind that this is really just a metaphor.
It’s certainly true that the kind of representation makes it conceivable that there is some possibility of doing a parallel search. However， in almost all the cases， when you look at a typical classical algorithm， and you will not find any way to use the quantum ability to do a parallel search.
So therefore， it's something that is not a real sense for answer by itself. And so what we would like to do is that to give you a real demonstration of the power of the speedup of a quantum algorithm. And also in the process， you are going to see exactly where the parallelism would arise.
