经典计算在量子计算机上

事实上，量子计算机的确能很好的实现经典计算机能实现的计算，但有可能不能直接的模仿，因为，经典电路大部分是不存在相对于自身可逆的逻辑门，而量子电路可以有。

这时，我们需要用到一个很神奇的逻辑门：Toffoli gate

它相当于一个两个控制位的非门，所以也叫做控控非门，或CCNOT门，它需要两个控制位都为1时，第三个位才会执行非操作，否则，无事发生，这个门很神奇，它是一个可逆门，我们作用输入变量两次，有 ，因此，它是一个可逆门，并且，它的逆是它自己。

同时，Toffoli门可以模仿NAND（与非）门，和做FANOUT（扇出）：

我们上面都是写的经典电路，但我们可以将此以量子线路的形式实现，类似量子的CNOT门一样，当输入为 的时候，则会输出 。

所以，我们可以用这个Toffoli门，实现各种的逻辑运算，此外，对于非确定性的问题，我们可以根据qubit本身的状态，赖世雄，比如，对于 ，我们可以作用一个Hadamard门，得到 ，测量后，得到两个状态的概率各为一半，从而实现一半概率的模拟，从而实现生成随机数之类的模拟。

当然，量子计算机

量子并行性（quantum parallelism）

这里的并行性也不能完全理解成并行计算，虽然也有点这个意思，量子里的并行性是指，可以计算 的同时，对不同的 的值进行计算。

考虑下面的逻辑门（我们先不考虑逻辑门的具体实现）：

显然，输出为：

我们同时得到了两个函数的结果， 即 ，这也就是量子计算的量子并行性，这个结果很容易推广到更多位数，通过Hadamard变换（Hadamard transform），也叫做Walsh-Hadamard变换，在上图中，x是 经过一次Hadamard门形成的，即一次Hadamard变换，如果我们作用两次，可以得到：

我们可以把这个简写成 ， 叫做tensor，推广到更一般的形式，则是：

通过之前的类似的逻辑门的变换，我们能做到同时得到更多的结果：

下面，我们介绍一个量子算法，来加深对上面的并行性的印象。

Deutsch算法(Deutsch's algorithm)

算法的量子线路如下：

首先，输入为 ，两个qubit经过Hadamard门后为：

然后作用在 门上，我们可以有，第一个qubit是 ，第二个是 ，所以结果是 ，我们假设函数 的可能的值，然后整理一下，如下：

然后，x再作用hadamard门，得到：

我们可以整理一下，得到更简单的形式： ，所以，我们可以得到一个关于函数 的全局特征，即 的值，比需要求两次的经典计算机不同，我们只用了一次计算。

Deutsch-Jozsa 算法

当然，我们可以扩展到更一般的情况，就是Deutsch-Jozsa算法。

下面讲一个通信中很典型的一个题：

Alice姚传输一个 的值并发送给Bob，Bob计算完 后返回一个结果，0或者1，函数 保证是一个常数或者是返回0，1各二分之一概率的随机函数，Alice的目标是确认Bob用的是哪一种函数。

在经典计算机中，最坏情况下，Alice需要询问Bob至少 次，才能保证是哪一种，不过，我们换成qubit的话，我们有其他的方法。

和上面的算法类似，但我们扩展一下，线路图如下：

初始， ，作用Hadamard门后，我们有：

然后通过 门，得到：

后面的比较难理解些，我们先考虑普通的一个qubit作用在Hadamard门上，即 ，其中， 。

扩展到多个，我们有：

简化后，我们有：

类似，我们把 作用在Hadamard门上：

然后，我们分析这个结果，对于 这一项，它的振幅（就是前面的系数）值为 ，如果 为恒定值，那么 的振幅为+1或者是-1，所以，如果Alice观察到全0，则是恒定的，否则就是等概率随机01值的，算法过程总结如下：

但是，在实际生活中，类似的问题并没有应用，并且，测量量子状态的测量，也可能消耗比较大，最值得一提的是，类似的问题相对于确定算法，我们可以用概率算法来解决，这样更实用，虽然该算法没有实际意义，但对于后面的量子算法的设计还是有很大的启发的作用。

量子算法总结

下面，我们将介绍一些量子算法有前景的领域。

目前， 有三类的量子算法明显比经典算法好，首先，是基于量子的傅立叶变换，二是量子搜索算法，三是量子模拟，原书37页有更详细的背景介绍，但不影响后面学习，且后面的章节会再次讲到，就不赘述。不过，对于量子计算机是否真的优于经典计算机，我们还不确定。

接下来，我们讲述一些关于计算复杂度理论。

计算机复杂度理论用于把不同计算难度的问题进行分类，最基本的概念就是复杂类，一个复杂类的问题需要相同的计算资源来解决。

最基本的复杂类有两个：P和NP，简单来说（不够规范，科普性质），P是可以很快的解决的问题（严格上说是多项式时间内，P代表polynomial time），NP是可以很快检验一个结果是否正确，比如，将一个大数进行分解成质数相乘，很难，需要很多时间，而检验一个数是否是这个大数的质因数，则很容易，很快就能算出，所以，该问题属于NP问题。

很显然，P属于NP问题，但是，我们至今仍不清楚P和NP是否完全相等，P问题是否等价于NP问题，是计算机科学中最重要也是最难的问题之一，许多研究人员相信，两者是不等价的，实际上，在NP问题中，存在一类NP完全问题（NP-complete），许多的目前发现的，属于NP问题但不属于P问题的问题，都可以规约到NP完全问题中，即，不会比NP完全问题难。

不过，质因数分解不算NP完全问题，所以，我们也无法确定量子计算机能否快速的解决所有的NP问题。

除了P和NP，还有很多的复杂类，比如PSPACE，顾名思义，就是能在比较小的空间范围内解决的问题的类，时间上没有限制，我们普遍任务，PSPACE会P和NP类大，但是并没有证明。

BPP是指能在多项式时间内解决的随机算法（也就是很快），BPP被认为比P范围广。

关于量子计算复杂类，我们可以类似的定义，BQP为可以在计算机内很快计算出的问题，但允许一定概率上的误差，类似经典计算机中的P类问题，量子计算机可以很快的计算出P类问题，并且这已经是已知的，但目前没有存在很快解决PSPACE以外的问题的方法，综上，可以画图释义如下：