Shor量子算法推演与分析

一、前言

很多人对于量子计算的普遍感受是：在网上一搜量子计算就一股脑地开始阅读，好像啥都懂了又好像啥也不懂，还有很多科普文章除了给人留下了一个“相当牛逼”的印象后，还是一脸懵逼：为什么量子叠加态还能参与计算？量子计算机又是怎样实现并行运算的？量子计算机又是如何解决特定问题的？

本文就从量子计算最为重要的算法—Shor算法开始做详细探讨，看他是如何破解RSA的？先废话几句，多年前看了Shor的论文，还是云里雾里的，最后结合各种资料，自己亲手推了一把，算是明白其中的精髓。之后几年没碰过了基本忘得差不多，没想到前段时间在旧箱子里找文件时，还发现了手稿，看了一遍，又懵了，所以吧，写篇更详细的文章记录一下，以后可能用得着，分享出来也算是给想要了解量子算法的小伙伴一些启示。

为了更通俗易懂，本文涉及的公式推导都尽量详细，力求高中水平就能看懂，你既不需要懂密码学，也不需要懂量子力学也能明白算法的精髓。本文将详细分析Shor算法的实现过程，整数周期数及非整数周期数下Shor算法分析，Shor算法概率评估，实例分析。不得不说，量子计算以及量子计算机是一个很庞大的知识体系，个人水平有限，此处我们仅仅就单纯地围绕Shor算法本身进行探讨分析，不考虑退相干对算法的影响，也不考虑物理实现。

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

1、为什么量子叠加态还能参与计算

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

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

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

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

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

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

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

还有一个比较重要的复合门是受控U(a,x)门，想深入了解的看这篇文章：一只冰牙喵：4.2 受控操作。

不过这里看不懂没关系，我们只需要知道受控U门可以用于计算以a为基底的幂，其一般用于生成指数函数值。

2、量子如何做并行运算

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

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

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

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

3、量子计算能做什么

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

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

二、Shor算法分析

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

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

我们知道RSA是基于经典计算机大数质因式分解的指数复杂度的困难而设计的一种非对称加密算法，目前最优的因子分解算法为指数复杂度 。而通过shor量子算法可以以多项式复杂度完成大数因式分解，从而可以快速破解RSA算法。那么Shor算法是如何发挥如此威力的，简单来说，Shor算法的核心依赖于三个变换即H变换,U变换,QFT(量子傅立叶)，接下来我们一步一步的分析。

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

1、RSA算法

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

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

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

（3）生成d，使得d*e%L=1且1<d<L 那么加密解密操作如下：

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

2、问题转化

首先我们需要将大数因子分解问题转化为以求待分解的合数N为模的函数 的周期问题。

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

设整数 ，则

1 " data-formula-type="block-equation" >

那么 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。

3、通过Shor算法求周期r

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

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

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

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

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

因此，x可以表示为

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

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

经过投影后

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

上式可以变换为：

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

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

A.整数周期

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

当 时，我们通过等比数列转化得到：

带入（0）式得：

由于 ，也就是说，当 ，也即不为整数，则为相消干涉，其值为0。

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

测量 的值， 等概率 地选择出一个态。由 得：

如果有 , r 就可以从 的不可约分数求出。

B. 非整数周期

不能整除 r 的情况下,那么在x值范围内的周期数A便不是整数，此时我们加入微调参数 稍作调整，使得 为整数，设

因此(2)式的[ ]为：

这里 的值极小，该值用于逼近函数的峰值，我们再令

因此(3)式的平方表示为

由于

因此

所以得到 的概率为

这里，为了严谨讨论，我们设 小于等于1/2（如果大于1/2，可以认为是下一个整数 ） ，所以这是适用于所有情况的

由(4)(5)得：

当

， 必位于原点与点 连线的上方，所以

而对于任意 ， 为凸函数，有：

又因 ,因此：

所以，测量 的概率为

最后，我们来讨论测量值 ,有

所以

这里 已测得，这里严格存在一个分数 ,可由 的连分数展开求出（下一个节将通过实例说明），通过约分满足 就可得到 r 的值，gcd算法的成功率为

\\frac{1}{logr}\\\\ \\Rightarrow Prob[N]=Prob(gcd(k,r))\\cdot Prob(\\gamma)>\\frac{1}{logr}\\cdot\\frac{4}{\\pi^2r}=\\frac{4}{\\pi^2rlogr} " data-formula-type="block-equation" >

也就是说我们能以大于 的概率分解N的因子再加上量子傅里叶变换的复杂度为 ,所以shor算法的时间复杂度为 。

三、实例分析

虽然上面已经分析得很透彻了，但是估计还是有人觉得会太抽象，所以下面我以一个例子来进行实例分析，以帮助理解。

对于 ，N=91，a=4，那么

f(1)=4,f(2)=16,f(3)=64,f(4)=74,f(5)=23,f(6)=1

所以周期为 r=6， , ，然后根据2，3式我们计算得到：

这里， 是我们测量得到值，如果这个值为0，那么对于我们求周期r是没有意义的，所以除开这种情况下，测得其他值的概率和为0.623。如果测量的值为13653，那么我们来计算0.833312的连分数。

1/0.833312=1.200031,

1/0.200031=4.999225,

1/0.999225=1.000775,

1/0.000775=1290.322580

这里遇到大数1290，我们就终止，最后我们得到连分数为

那么我们就可以确定 k=5,r=6 了吗，那有没可能 k=10,r=12 呢，所以，我们不能单纯的通过一次测量来确定周期，我们来考察其他几项，我这里不再一一去展开了，懒人可以在这里去计算(连分数计算 -连分数计算器-分数计算器)。

因此，如果我们将shor算法多执行几次，最后求出各个分母的最小公倍数，那么这个最小公倍数就是我们要找的周期r，有了周期r，我们就不难求出合数N的质数因子了，进而也能够比较容易破解RSA算法了。

四、离散对数问题简析（不感兴趣可以略过，有时间补充）

通过对shor算法原理的剖析，我们可以知道，对于任何具备转化为求周期函数的周期为目标的问题都可以用同样算法以指数加速来快速解决，比如离散对数(ElGamal), ECC之类的非对称加密算法都可以用同样的思想来解决。

离散对数多说两句，Shor在其原始论文中对于素域上的离散对数问题，给出了一个基于整数求阶量子计算算法求解算法,成功率为1/480。Shor指出在解决素域上的离散对数问题时，其实并没有利用到素域的特性，因而对有限域上的离散对数问题也同样成立。后来Eicher和Opku给出了一个在多 项式时间内以1/480的成功率攻击椭圆曲线离散对数问题的量子计算算法。

设一个阶为 p ,且生成器 为g 的群 （ ） ,如果 ,那么对于部分 ,我们希望得到 r ,那么 r 就是离散对数 .

比如EIGamal加密，对于随机大大素数P,以及随机数x,满足

这里 (y,g,P) 为公钥， x 为私钥。我们将长度为我们将长度为 ， 的消息分组为

那么计算密文

这里c1,c2为加密后的密文,那么解密过程如下：

简单推一下

考虑abelian 群 (每一个因子对应于值的模加)。那么函数

这给我们呈现了一个abelian 隐含子群问题，同时可以看出映射 f 是一个群同态。kernel为 (r,1) 的倍数，所以如果我们能找到kernel，我们就能够找 r。

对于函数 ,设周期为 和 ，那么

因此，我们只要通过量子算法求得周期 就可以得到 r 。使用量子算法处理离散子群问题，和我们前面讲解的方法非常类似，后续有时间再分析吧。

参考文章：

Shor, P.W. (1994). "Algorithms for quantum computation: discrete logarithms and factoring". Proceedings 35th Annual Symposium on Foundations of Computer Science. IEEE Comput. Soc. Press: 124–134

https://authors.library.caltech.edu/2179/1/BECpra96.pdf

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

https://en.wikipedia.org/wiki/Shor%27s_algorithm

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

https://zhuanlan.zhihu.com/p/106923175

声明：本文来自ADLab，版权归作者所有。文章内容仅代表作者独立观点，不代表安全内参立场，转载目的在于传递更多信息。如有侵权，请联系 anquanneican@163.com。