量子计算

一、量子力学

为了方便讨论，需要引入狄拉克符号

这称作狄拉克符号，A代表某种状态。

量子力学里面有个重要的概念，叫做测量，在测量某个物理量之前，你是无法确定系统的该物理量的。比如说，对于著名的薛定谔的猫，猫放在箱子里面，箱子里面的放射性元素是否衰变决定着猫的死活，但是在你打开箱子之前（或者任何尝试测量猫死活状态、放射性元素是否衰变的举动），你无法确定。这时有

其中a代表死了的概率幅，b代表没死的概率幅。概率幅（概率幅是个复数）乘以概率幅的共轭，是该状态的概率。

这个式子表示猫处于在一个叠加的状态，又死又活。当你进行测量之后，才会具体的变成  或者  （测量之后变成的这个特定的状态称作基）。而假设你制备完全相同的若干个此系统，都进行测量，那么死活的统计结果就是式子里面的概率幅算出的概率。

你可能会说，这看起来就只是个数学技巧而已。但其实不是，又死又活的叠加态是真实的物理，这一点，实验可以证明，比如单光子的杨氏干涉实验。

二、量子计算

大家知道，电子计算机其实基于一些基础的逻辑门，比如或门，与门，非门。换句话说，只要你通过物理方法实现了这些门，那么原则上就可以做出电子计算机了（暂时忽略时序电路的实现）。

量子计算机也有类似的性质。基于某些证明，有了受控非门和单量子比特门就可以原则上实现所有量子门（定义在后面给出）。下面我会一个个介绍

单量子比特门，顾名思义，就是对于单个量子比特进行操作的门。由于我们刚才说，量子力学里面存在叠加态这种状态，所以这个门相当于

 的映射

也就是

为了满足物理意义（变换之后，  和  的概率和还是1），还要求U是个酉矩阵。

比如

（给出了单个  和  的变换，也就是给出了  到  的）

就是一个单量子比特门（这个门叫做Hadamard门）。

（单量子比特门其实又可以分成几种独立的操作的结合，也就是  酉矩阵的所有基对应的操作）

受控非门，是对于多量子比特来说的，下面以双量子比特为例。

我们用  或者  表示  和  两个单量子比特

受控非门是如下的映射

其中A为控制比特，B为目标比特。控制比特为0时，目标比特不变，为1时，目标比特翻转。

（和之前类似，给出了单个的基的变换，也就是给出了任意双量子比特，包括叠加态，的受控非门操作。顺便一提，受控非门也是酉矩阵）

任意量子门，也就是任意n个量子比特到n个量子比特之间，满足概率总和不变（也就要求是酉矩阵）的操作，都可以由单量子比特门和受控非门实现。

好了，说了这么多，在量子比特上进行的计算，到底和经典比特有什么不同呢？

下面会说到量子并行性特点

先忽略物理实现的方法，假设我们存在一个量子逻辑门，可以实现映射

其中f(x)是一个对我们有用的函数，而当输入的x为两个量子比特时（这个时候大概是  ），  。特别的，当y=0时，有

想象一个黑箱子，有两个输入比特，两个输出比特

现在我们输入两个量子比特，一个  ，一个  （注意，这个地方x可能是叠加态）

那么黑箱子就会返回给我们两个量子比特，  和 

关于这个黑箱子的实现方法，很长，我就不细说了。大概的逻辑就是，我们可以构造一个量子门（Fredkin门），以多用一些比特的代价，实现经典逻辑门（量子门可逆，而经典逻辑门不可逆）。然后找到f(x)的经典逻辑门实现方法，用Fredkin门替换，也就是f(x)的量子门实现了。

现在我们对输入的  做一些操作，比如让  通过Hadamard门变换成  。

也就是说现在黑箱子输入的两个量子比特，一个是  ，一个是 

那么我们会发现，输出的  量子比特变成了

而另一个输出的  自然是

因为输出的是  ，所以把两个写一起，此时输出就是

如果输入x是两个量子比特,那么同理，输出是

这说明了什么？

我们的量子比特只通过了一个计算f(x)的量子门，就同时计算了  个f(x)的值（其中假设x输入的是n个量子比特。当然，还是有些额外开销，比如n个Hadamard门，和Fredkin门实现f(x)量子门时的额外开销，但这些都是n量级的。）

但这里有个小小的问题，虽然所有的f(x)都被计算了，原则上，我们对输出进行测量，如果  中x为x0，那么就可以知道后面那个量子比特为f(x')的值。但是，我们测量，最终得到的只是一个  ，不可能同时测量到所有的  。听起来似乎相当的绝望，不过，好消息是，通过构造一些特别的量子算法，可以间接的利用到量子并行性的额外信息，从而加快某些算法。换句话说，如果需要量子计算机真的全面替代电子计算机，而不是只在某些特定的算法上面加速，那么需要一个通用的量子算法。

三、物理实现

注意到之前的所有讨论，其实可以看出物理实现有这么几个要求。

在需要测量（或者说是计算完成）之前，要保持量子比特的叠加态（叠加态使量子算法具有优势）。

需要实现基本的，单量子比特门和受控非门（这两个是量子门的基础）

要能产生基，也就是说产生  和 

在这之前，先提一下物理实现酉矩阵的原理。在量子力学中，测量被刻画为一个算符，其中测量系统能量的算符为H，比如

就表示对  系统的能量测量，测量结果为E。

根据量子力学的另外一个结论，  体系随着时间的演化可以写成

如果我们找到H,使得  的作用相当于酉矩阵的话，那么量子比特在这系统中就相当于通过了对应的量子门。