好长时间没有来看雪发文了，近期也没什么可写的，把以前不务正业写的文章重新整理下(换个题目并调整了部分内容)发到这里冒个泡。废话几句，量子计算往往容易被媒体吹嘘得神乎其神，写这篇目的也是为了能够让更多的人了解量子计算的精髓和灵魂，也是我自己理解量子计算的一个过程，分享出来希望能够给想要试图理解量子计算的小伙伴一点启示。对于量子计算我也好些年没搞了，目前的水平也只能如此了，如有错误，望各位海涵。不知道该发哪个版块，段老大说发软件逆向板块吧，因此扔到这里来共同学习探讨。由于论坛不支持公式编辑，因此文字中的公司只能用类似字母代替，推导的公式也只能截图，如果阅读时对应不上，可以留言。

很多人对于量子计算或多或少都有所了解，但目前量子计算圈和安全圈存在着巨大的鸿沟，关于量子计算报道大多喜欢夸大其词，让人感觉量子计算像玄学一样，徒增神秘感，并不利于量子计算思想的普及。很多人虽然对量子计算做了很深入了解，但大多事后仍旧疑惑不解：为什么量子叠加态还能参与计算？量子计算机又是怎样实现并行运算的？量子计算机又是如何解决特定问题的？

本文就从量子计算最为重要的算法—Shor算法开始做详细探讨，看他是如何破解RSA的？ 为了更通俗易懂，本文涉及的公式推导都尽量详细，力求高中水平的数学基础能看懂。你既不需要懂密码学，也不需要懂量子力学也能明白算法的精髓。

本文将详细分析Shor算法的实现过程，整数周期数及非整数周期数下Shor算法分析，Shor算法概率评估，实例分析。不得不说，量子计算以及量子计算机是一个很庞大的知识体系，个人水平有限，此处我们仅仅就单纯地围绕Shor算法本身进行探讨分析，不考虑退相干对算法的影响，也不考虑物理实现。

废话不多说，先回答几个让人疑惑的问题。

一个量子可以同时处于两种状态的叠加（比如自旋向上和自旋向下），这种叠加态测量的瞬间就会随机变为一个确定的态（测量得到自旋向上），这个过程叫波函数的坍塌。我们如果将这两个态表示为0,1，而每种态观测后出现的概率幅(注意不是概率，概率幅的平方为概率为1）为α,β，那么这个量子可以表示为

这里右尖括号为狄拉克符号，表示量子态， 0,1为基态，+表示叠加，两种态的概率幅平方和为1，即 α^2+β^2=1 。而我们通常说的量子计算就是通过量子逻辑门来操作处于叠加态的量子。比如Hadamard门，简称H门（在量子计算中非常重要），他的一个主要功能就是通过计算基态产生等概率的叠加态。通过H门变换后的单量子叠加态为：

两种基态的坍塌概率都为1/2 ，两个量子的H门得到的结果如下：

每个态坍塌的概率 1/4 ，对于n个量子的H门变换后：

其他量子门这里就不做介绍了，本文暂时不会涉及，想更深入了解可以到维基上看。

https://en.wikipedia.org/wiki/Quantum_logic_gate

量子门及其对应的门矩阵如下图：

量子门及门矩阵，图片来自wikipedia

还有一个比较重要的复合门是受控U(a,x)门，想深入了解的看这篇文章：一只冰牙喵：4.2 受控操作，不过这里看不懂也没关系，我们只需要知道受控U门可以用于计算以a为基底的幂，其一般用于生成指数函数值。

受控U门（来自https://zhuanlan.zhihu.com/p/422428222）

量子并行运算（Quantum Parallelism）是基于量子叠加态（Quantum Superposition）和幺正变换实现的。量子计算正是有了数据的可叠加性和幺正变换，从而决定了一次操作即可改变全部数据。比如有量子寄存器，存了10个处于叠加态的量子，在通过运算时只需要一次性操作这10个量子，但是由于可叠加性，这10个量子叠加态可以表示2^10个基矢，一次操作10个量子，相当于一次对2^10个基矢进行了操作，这就大大提高了运算的速度。

在经典计算中，并行性的核心思想是将一个计算任务分配给多个处理器同时运行，要快于使用一个处理器来运行。在理想的情况下，将工作分配给K 个处理器就应该使计算时间缩短为原来的1/K。但是现实肯定不是这样的，真实的任务往往具有串联性，只有部分具有并联性的子任务才能够做并行运算。由于量子计算的特点是数据的可叠加性质和操作的幺正变换本质，从而就决定了量子计算的语义特征是完全意义上的通过一次操作即可改变全部数据的并行计算。将一个N 位量子寄存器中的 2^N 个数据同时通过一次幺正变换（即进行一次运算）所需的时间定义为 Tq ，而经典计算中对一个数据进行运算的时间为 Tc ，因为一次量子计算就对所有的数据做了并行处理，所以量子计算加速能力可以表示为

如果 Tc=Tq ,那么加速能力 S=2^N,也就是说对量子计算机做一次运算，相当于对经典计算机做 2^N 次运算。

此外，一台量子计算机并不一定在所有计算任务上都比一台经典计算机做得好，比如乘法运算在一台量子计算机上执行就不如传统计算机上快。为了突出量子计算机的优越性，就需要开发量子并行效应能力的算法。

量子计算机是严重依赖于优秀的量子算法的实现，虽然通用量子计算机能做经典计算机的所有事情，但是只有在处理特定问题上量子计算才具有决定性的优势，目前已经有很多优秀的量子算法，其中对大数因子分解，离散对数问题以及更一般的隐含子群问题的解决有着开创性和重大影响的量子算法便是本文要详细分析的Shor算法。

本文将非常详细的分析Shor算法来让各位明白量子计算在解决特定问题上的巨大优势。

在费曼提出量子计算机概念不到15年的时间，shor通过研究出的量子算法给世人了一剂强心针，自从shor算法出来后，人类开始加速了量子计算机的研制，各大头部企业也纷纷加入了量子计算机的量子竞赛行列。

shor算法最令人振奋的是直接将质因子分解以及离散对数问题以指数级速度提升，这给人们的启示是可以利用同样算法思想来解决更为广泛的隐含子群问题。

我们知道RSA是基于经典计算机大数质因式分解的指数复杂度的困难而设计的一种非对称加密算法，目前最优的因子分解算法为指数复杂度

而通过shor量子算法可以以多项式复杂度完成大数因式分解，从而可以快速破解RSA算法。那么Shor算法是如何发挥如此威力的，简单来说，Shor算法的核心依赖于三个变换即H变换,U变换,QFT(量子傅立叶)，接下来我们一步一步的分析。

Shor算法量子实现线路简图：

Shor算法量子实现线路图

我们设RSA的公钥为 (e,N) ，私钥为 (d,N) ,那么生成公私钥的过程如下：

生成两个足够大的素数p,q，得到合数N=p*q，然后计算得到p-1和q-1的最小公倍数L。

生成e,使得e和L互质，且满足1<e<L

生成d，使得d*e%L=1且1<d<L

那么加密解密操作如下

我们知道RSA是基于大数N的因子分解的困难而设计的非对称加密算法，因此我们只要能够实现大数N的因子分解，就可以破解RSA，这里不做证明了，网上有很多资料。这里你只需要知道，我们可以通过公私钥的N，然后通过Shor算法求得N的因子p,q就可以了。

首先我们需要将大数因子分解问题转化为以求待分解的合数N为模的函数 f(x)=a^x ( mod N) 的周期问题。

设周期函数f(x)=a^x（mod N） 的周期为r（这里a为小于N，且与N互质的整数），则有：f(x)=f(x+r) , 那么：

设整数 

则 

那么 x-1， x+1 都能被 kN 整除，那么一定存在 gcd(x+1,N)>1 或者 gcd(x-1,N)>1 (gcd是一个用辗转相除法求公因子的函数)，也就说与N存在一个大于1的公约数，这个公约数就是N的分解因子。

例如：设 N=15，a=7 ,则：

由此，我们只要求出f(x)的周期，就能轻而易举的分解合数了。而shor算法的精髓就是利用量子特性来快速求解得到周期r.

设量子比特长度为 L, 则总共可以表示的 q=2^L 个基态, 设N为要分解的合数，为了确保 2^L 长度内有足够的周期数，我们需要满足

然后，我们利用Hadamard门来构造等概率的量子叠加态 |x>存入寄存器reg1，然后利用U门来构造 |f(x)> 的叠加态存入寄存器reg2，且使这两个寄存器处于纠缠态。

两个寄存器展开形式如下：

由于 f(x) 为周期函数，设周期为r，A为总长2^L中存在的周期数，则

设l为小于一个周期内的x的值, x=l+Ar, 则整个系统的态实际为

因此，x可以表示为

然后对reg2进行计算基上的测量，设测量结果设为 Z ，测量Z在reg1中的投影变化为

例如 N=15，a=7 ，测量后的整个系统的态为：

经过投影后

这里，当测量得到一个γ 值后，由于寄存器reg1和寄存器reg2是处于纠缠态，所以Z值测量后寄存器reg1会塌陷为相同Z值的|x>叠加态，如果reg2测量的值为1，那么reg1则处于 (|0>}+|4>}+|8>+...) 的叠加态，那么周期 r 的信息就包含在reg1中，因此对reg1进行量子傅里叶变化：

上式可以变换为：

这里为什么要这么变换，因为当测量Reg2时，Reg2坍塌为了r个值中的一个值，所以每一个值对应reg1中的A个叠加态。这里设：

这里，我们需要考虑两种情况，一种是 2^L 能够整除 r 的情况，也就是在 2^L 内刚好有整数个周期，一种是不能整除的情况。如果能够整除，那说明每个波峰刚好位于 ϒ=k2^L/r ，不能整除时，波峰位于非常接近波峰的两侧，因为波峰处的 ϒ 本应该为非整数，而我们测量得到 ϒ只能是整数，所以这时候我们需要加入微调的参数。接下来我们分别对这两种情况进行分析。

A.整数周期

在(2)式的[ ]中，在 ϒ 是 2^L/r 的整数倍情况下变成，出现相长干涉，求和后为 A=2^L/r ，如果不为整数，则为相消干涉，其值趋于0. 所以

当 γ≠ k2^L/r 时，我们通过等比数列转化得到：

带入（0）式得：

由于

，也就是说，当γ≠ k2^L/r ，也即不为整数时，为相消干涉，其值为0。

通过量子傅里叶变换后得到如下叠加态：

[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入！