量子计算的理论发展（二）-白红宇

抱歉这么久才更新第二篇，最近会多更新几篇的。

上次说到如何在量子线路中实现类似经典逻辑门的操作，那么，这件事情我们该从何思考起来呢？

对于确定的计算，经典计算机实现的是一个n比特输入，m比特输出的函数

记为 $f: \left\{ 0, 1 \right\} ^{n}\rightarrow \left\{ 0, 1 \right\} ^{m}$

我们可以将上述函数转化为m个函数，每个函数都是一个n比特输入1比特输出的函数

记为 $f\rightarrow f_{i} : \left\{ 0, 1 \right\} ^{n}\rightarrow \left\{ 0, 1 \right\}, i=1,2,3...m$

对于 $f_{i} (x)$ ，我们不妨设输出k个1，2^n-k个0，即输入 $x^{a} (a=1,2,3...k)$ 时输出为1，输入 $x^{a} (a=k+1, k+2, ... 2^n-1, 2^n)$ 时输出为0

这样可以写出 $f_{i} (x_{i})$ 的形式 $f_{i}(x)=f_{i}(x^{1})\vee f_{i}(x^{2})\vee...{\vee}f_{i}(x^{n})$

其中， $\vee$ 是或函数，任意一个 $f_{i} (x^{a})$ 的输入为1，则 $f_{i} (x^{a})$ 输出为1

而对于函数 $f_{i} (x^{a})$ ，我们可以写成 $f_{i} (x^{a})=x_1^{a}\wedge \bar{x_2^{a}}\wedge \bar{x_3^{a}}\wedge...{\wedge} x_{n-1}^{a}{\wedge} \bar{x_{n}^{a}}$

其中， $\wedge$ 是与函数，当 $x^{a}$ 的各位和等式右边的序列对应相等时（没有上横线的位为1，有上横线的位为0）， $f_{i} (x^{a})$ 为1

到现在为止，我们已经将最初的问题简化为只需要与门、或门、非门外加copy门这些基本逻辑门构成的问题了，简单地想，我们只需要在量子逻辑门中实现这些基本逻辑门就可以实现量子计算了

不过，还需要提到的是，量子计算和经典计算不同的是，它是可逆计算，可以简单地理解为输入和输出的数目相等，在可逆计算理论中，只要实现Toffoli门，就可以实现与或非门等基本逻辑门（这一过程是通过控制三个输入比特中特定的一个或两个输入比特来实现的，读者可以自己思考），那么，我们最后就把问题归纳到如何在量子计算中实现Toffoli门

Vm3b1BgPv0uONyJ8JHWieY6YD00g0O2yTjTzftKk

Toffoli门如图，是一个控制控制非门，只有当最上面两行输入为1时，最下面的输出将输入翻转

在量子力学中，我们知道比特是在Bloch球上的，对于比特的操控我们是通过让比特绕某一轴的旋转来实现的。在这里我们可以轻松实现的是3比特的Deutsch门，即控制控制旋转门，通过级联Deutsch门可以实现Toffoli门

后来的科学家进一步简化了Deutsch门，他们证明通过控制旋转门和控制非门的某种级联可以实现Toffoli门，如图

右面的V代表的是控制旋转门，而控制旋转门又可以表示为单比特旋转门和控制非门

这样，科学家们最后就将通用的量子计算简化为：单量子比特操控和两量子比特控制非门的操控！也就是说，只要我们做出来单比特旋转门和两比特控制非门，理论上我们就可以实现通用的量子计算了！

可是到现在各位可能还看不出来量子计算的威力在哪里，接下里我们介绍一些量子计算的算法，来让大家体会体会量子计算的效果，下期见（不会太久）！

原文发布时间为：2017.02.01

本文作者：Golden Horqin

本文来源：，如需转载请联系原作者。