说到质因数分解必定离不开量子计算机，讲到量子计算机，又必定离不开质因数分解。很多地方都有讲到过，一个很大的数，要把它分解成质数，经典计算机需要几亿年，可是量子计算机却只需要几秒，巴拉巴拉，可是为什么呢？

好像很难找到科普类的文章具体讲讲其中的道理，那些文章要么太浅显，根本进不去本质，要么又太深，里面公式比文字多。我觉得，科普当然要有深又有浅才能high起来。

而我又一直对这个问题特别感兴趣，所以终于花了几天的时间，看了不少资料，才算是把其中的逻辑理出一条线来。

质因数分解

是一个很容易理解的运算，就是把一个数字，分解成质数相乘的形式，比如30=2*3*5.

对于一个比较小的数字，我们很容易就能找到它的质因数。可是对于一个很大的数，比如一个768位的质因数，就需要数百台机器运行数年才可能计算的出来。

从时间复杂性上来讲，如图

不同的计算需要的计算资源是不同的。

质因数分解被认为是指数级增长类型的问题，如果还记得那个在棋盘上放米粒的故事，就知道，涉及到指数级增长的东西都是很可怕的。

因为质因数分解的这样一个特点，所以，在计算机领域它就被拿来作为加密的手段。

就是RSA加密

它的加密过程是这样。

我选取两个大的质数q、p，然后把他们相乘，组成一个更大的数字n=q*p，然后再根据某些条件选一个数e。

我们可以根据n和e计算得到公钥；再根据e，p，q计算得到私钥。

然后我把这个公钥广播出去。收到这个公钥的人如果有什么信息想发送给我，他就可以利用这个公钥对这个信息进行某种加密，得到密文。

而我收到密文之后，就可以利用私钥对密文进行解密，得到明文就是原来的信息。

因为，密文解密一定需要用到秘钥，而求得秘钥一定需要p和q，所以如果有人想窃听的话，他就必须面对一个问题，就是他必须要把n分解成p和q，这就是我们前面说到的质因数分解。对于一个足够长的n，比如说2048位，理论上根据现在的计算机进行计算，就算他计算到地球毁灭都不可能算出结果。

但是，从理论上来讲，质因数分解这样一个对于普通计算机来讲是无比困难的问题，在量子计算机面前却是一个非常简单的问题，一个2048位的质因数分解，可能不到一秒就能计算出来。（虽然现在量子计算机还只停留在嘴巴上）

为什么量子计算机可以比普通计算机计算速度要快那么多？

这涉及到量子计算上的算法了。具体到质因数分解这个问题。

就是Shor's algorithm这样一个量子计算机算法

提到量子计算机，这里有两个概念，必须首先说一下。

第一，就是什么是量子计算机里的量子。

在量子力学里，量子指的是任意的微观粒子。

比如说一个电子。

在实验里面，物理学家发现，当束电子束穿越一高强度的磁场的打到后面的屏幕的时候，电子会在后面屏幕上打出两个分明的点。

表现的就好像电子有两种状态，这两种状态在磁场中的表现就好像是经典物理里电荷在旋转。于是就分别把这两种状态叫上旋与下旋。

而电子的这两种状态和经典的状态不一样，就是一个电子的状态可以是两个的叠加，比如一个电子可以有50%的概率上旋，50%的概率下旋。只有当我们进行测量（比如经过一个强磁场），它的状态就会随机变成两种中的一种，这时，它就一个确定的状态，比如上旋。但随着时间的流逝，它的状态又会慢慢演化，变得不确定了。

而量子计算机，使用的就是量子作为基本的计算单位叫做量子比特。普通计算机使用的普通比特只有两个状态0或者1.而量子比特除了表示0或者1之外，还可以表示0和1之间的任何状态。

（实际上，一个量子，比如电子的自旋它的状态需要两个复数来表示，就是说它状态的可能性是一个四维的面，而普通计算机的比特状态可能性只是两个点。）

对于量子比特我们还需要知道的一点，就是对于一个量子，比如电子，我们可以对它进行某些操作。

比如，我们可以使它通过某一震荡频率的磁场，它的状态就会旋转，从完全的上旋变成完全的下旋。

在量子计算机里对通过各种不同的量子逻辑门，对量子进行操作。

第二个要说的就是傅里叶变换。

学过大学数学，就算没学过也应该听说过它。它是一种变换。

很久以前，傅里叶发现，任意的一个周期函数或者图像，都是可以分解成不同频率的正弦波的叠加。

于是他就找到了公式，可以把一个周期函数表示成用按频率表示的形式，就是频域。

而这里我们要用到的一个它的特点就是，对于一个周期不是很明显的函数，经过傅里叶变换之后，我们就可以很清楚的看到它的周期是多少了。

我们需要知道一个一点是在量子计算机里面，通过不同逻辑门的组合，是可以实现离散傅里叶变换的。

知道了上面两个概念，下面我们就可以进入正题，讲讲Shor's algorithm 是什么一个过程了。

（Ps，我真的已经在很尽力的讲清楚了，如果看到这里你已经有一些懵逼了，那么放心，继续往下看，你会更懵的。）

首先，这个算法包括了两个部分，一部分是经典计算机实现的部分，另一部分是量子计算机进行的计算。

我们先来讲经典部分。

首先，问题是有一个很大的数N，我们知道它由两个质数p和q组成。而我们要通过计算算出这两个数。

第一步：选取一个小于N的任意数字a。

第二步：计算gcd（a，n）（gcd是求最大公约数的操作，比如gcd（20，15）=5，这在计算机里是一个很容易计算的操作。）假如结果不等于1，那么我们中彩票了，求出的数就是我们要的其中一个；假如等于1继续下一步

第三步：找到最小的r，使 a^{x} mod N = a^{x+r} mod N，这一步就是需要在量子计算机里实现的步骤。（mod是求余数的操作，比如9 mod 5=4，因为9÷5=1余4，根据欧拉定理，我们一定是能找到r的）

第四步：假如r是奇数，或者r是偶数且 a^{r/2}-1 mod N=-1.则回到第一步。

第五步：如果r是偶数，则gcd（ a^{r/2} -1,N）=p，gcd（ a^{r/2} -1,N）=q

这里可以这么解释。

整个过程举个例子如图。

于是，整个问题转化成了找到最小的r的过程，使 a^{x} mod N = a^{x+r} mod N.

对于这样的问题，我又一个大胆的想法，如图。

我们可以把实数轴想象成一条绳子，于是 a^{x} 根据大小不同分布于这条绳子的不同位置，我们把然后我们 a^{x} 所在的用红色标记，然后我们找一个周长为N的圆柱，然后把这条绳子缠到圆柱上。

那么如图 a^{x} 中所有除以N有相同余数的数，就会落到圆的图一个位置上了。

这样一个操作，我们用复数就可以很好的实现。

在复数坐标系里，我们把不同的 a^{x} 用复数表示，我们再把余数用角度θ表示，如图。

于是我们可以画出一个x与θ的关系图，这是一个看起来很乱的图，但是机智的我们知道，它一定是有一个周期r的，而我们需要的就是要找到这个r。

那么，找一个图像的周期用什么？当然是用傅里叶变换啦。

我们把这一个图像经过傅里叶变换，我们就可以得到它的周期对应的频率而算得它的周期r啦。

当然上面的骚操作只能用脑子想想就好了。因为对分离变量的函数进行傅里叶变换求出周期的计算复杂程度和直接求大数的质因数是一样。

那为什么要讲这样的一个操作，那是因为对于经典计算机无比困难的一个操作，可是，对于量子计算机来讲，分离变量的函数进行傅里叶变换求出周期却是基操。

于是，这里量子计算机正式上场。看它对：找到最小的r的过程，使 a^{x} mod N = a^{x+r} mod N.这样一个问题，如何进行计算。

首先：对于N位的数字，我们需要q个量子比特，而 N^{2} < 2^{q} <2 N^{2} ，当然选用我们最熟悉的电子作为量子比特，而电子的上旋下旋态我们分别用│1> 和│0> 表示。

一，最开始，我们使这q个量子比特出于│0>态

二，用hadamard gate使量子比特们变成（ \sqrt{2}/2(│0>+│1>) ），就是一半概率上旋，一半概率下旋的状态。

三，再使用controlled-U gate使量子们分别变成（这里实在输不了符号了，你们看图吧）的状态，

其实这一步，就相当于前面我们把绳子缠到圆上的操作一样。

四，那么接下来当然就是量子傅里叶变换来了，就算在量子计算机里，这也是一个复杂的过程，但没有复杂到变态。就是通过重复使用量子逻辑门来实现的。

五，最后，对所有的n个量子比特进行测量，测量它们处于上旋还是下旋，记录下第z个量子比特是上旋的。

因为量子比特态之间的相互干涉，所以基本上所有的量子比特都会是下旋态，只有其中的一个有很高的概率会是上旋，我们是有超过50%的概率得到想要的结果的。假如没有量子比特是上旋，或者超过一个是上旋，那就只能重新再算一遍咯。

六，于是通过对z进行计算，就可以计算出我们要的r。对r进行验证，如果r是偶数，且满足（a^{x} mod N = a^{x+r} mod N），那么我们就得到结果了，否则就，从最开始的第一步取不同的a开始重新计算。

（这里要提一点，由于某些我说不清，你听不懂的原因，这里求出的z不是直接的r的周期，而是另外的一个数字，我们需要进过计算才能得到r。）

所以，总结一下，这个量子计算算法的特殊之处，也就是它与经典算法本质区别的地方，就是它对于分离傅里叶变换的计算，其复杂程度不是随N增大而指数级别增的。

而为什么会这样，我们可以这样去理解。

在经典计算里面，傅里叶变换的计算过程中，对于绳子上的一个点，我们需要通过很多计算才能算出来，而且因为大多数情况下是无理数，只能近似的去表示。

可是对于量子计算机来讲，绳子上的一个点，就真的只是一个点而已，我只需要用一个量子比特就可以表示出它的值了，而且不需要近似，因为一个量子的态可能性是一个四维的面，用来表示一个圆绰绰有余。

其中难度的区别，就相当于经典计算机这个小孩在算百万位级别数字的乘除，而量子计算机只在算个位数的加减法。

唉，好累，今天先说到这里，以后如果想到什么再补充。