Shor算法

来源

$1994$年，应用数学家$Shor$提出了 一个实用的量子算法，通常称为$Shor$算法。其思想是将整数质因子分解问题转化为求解量子傅里叶变换的周期, 将多个输入制备为量子态叠加, 进行并行处理和操作, 从而达到了量子加速的目的，可以在多项式时间内完成大整数质因数分解。所以$Shor$算法从诞生之时，就和以$RSA$算法为根基的加密技术形成了不可调和的矛盾。

Shor算法的大致流程

完整的$Shor$算法需要经典计算机和量子计算机协作完成。其中量子计算机实现一个周期查找的函数，经典计算机负责整个算法流程的控制，以及调用量子算法。我们可以简单的讲$Shor$算法分成两个部分：
1.第一部分是讲因子分解问题转化为成周期问题，这部分可以用传统方式实现。
2.第二部分则是使用量子手段来搜寻这个周期，这一部分是$Shor$算法中体现量子加速的主要部分！

因数分解

假设待分解的整数为$N$，分解步骤为：
1.选择任意数字$1<a<N$；
2.计算$gcd(a,N)$，要满足$gcd(a,N)=1$，即$a$与$N$互质，否则返回第一步；
3.构造函数$f(x)=a^{x}modN$，并且寻找最小周期$r$，使得$f(x+r)=f(x)$；(此为量子计算步骤)
4.若$r$为奇数，则返回第一步；
5.若$a^{\frac{r}{2}}modN=-1$，返回第一步；若$a^{\frac{r}{2}}modN\ne -1$，则$gcd(a^{\frac{r}{2}}\pm 1,N)$所求的质因数为$p=gcd(gcd(a^{\frac{r}{2}}+1,N),q=gcd(gcd(a^{\frac{r}{2}}-1,N)$，至此，完成分解。

下面我们看一个具体的例子：
例用$Shor$算法对$N=15$进行分解。
不妨取$a=7$，其满足$gcd(7,15)=1$，因此，构造函数为$f(x)=7^{x}mod15$，有：
$$\begin{gathered} f(0)=7^{0}mod15=1,f(1)=7^{1}mod15=7,f(2)=7^{2}mod15=4,f(3)=7^{3}mod15=13, \\ f(4)=7^{4}mod15=1,f(5)=7^{5}mod15=7,f(6)=7^{6}mod15=4,f(7)=7^{7}mod15=13, \\ f(85)=7^{8}mod15=1,f(9)=7^{9}mod15=7,f(10)=7^{10}mod15=4,f(11)=7^{11}mod15=13. \end{gathered}$$
不难看出，周期$r=4$，且$a^{\frac{r}{2}}modN=7^{\frac{4}{2}}mod15=4\ne -1$，那么有
$$p=gcd(50,15)=5,q=gcd(48,15)=3$$
传统计算机储存的是数据，而量子计算机储存的是分解后的结果，这一步不需要任何计算成本。量子计算机再分解的时候其实就是储存的过程，每个正交状态对应一个素数，存储的过程天然就分解了这个数。尽量不要把$1,0$的传统概念套上去，并不利于理解。比如$15$怎么在量子态下表示？首先找到对应的正交态，则自然是素数了，$15=3\times 5$，那么，$|15⟩=|3⟩+|5⟩$就可以了，这里的正交态对应的就是传统的$1,0$。

周期求取与量子傅里叶变换(QFT)

对两组有$m$个量子比特的存储器进行幺正变换得到纠缠状态：
$$\sum _{i=0}^{2^m-1}|x_i⟩\otimes |f(x_i)⟩,f(x)=a^{x}modN$$
对量子位进行傅里叶变换，即：
$$QFT:|x⟩\to \frac{1}{\sqrt{2^m}}\sum _{k=0}^{2^m-1}{e}^{2\pi kx/2^m}|k⟩$$
可以看出，量子傅里叶变换就是将态前面的叠加系数变为原叠加系数的离散傅里叶变换。
将两个寄存器$R_1$和$R_2$初始化为$0$，即：
$$|{\Psi }_0⟩=|R_1⟩|R_2⟩=|0⟩|0⟩=|00\dots ⟩|00\dots ⟩$$
其中，$R_1$存放函数的输入变量，$R_2$存放计算结果。接着，对$R_1$中的每一位作$H$变换，有：
$$H:|{\Psi }_0⟩\to |{\Psi }_1⟩=\frac{1}{\sqrt{2^m}}\sum _{x=0}^{2^m-1}|x⟩|0\otimes f(x)⟩=\frac{1}{\sqrt{2^m}}\sum _{x=0}^{2^m-1}|x⟩|a^{x}modN⟩$$
此时，$R_1$和$R_2$处于纠缠状态。
测量$|R_2⟩$，并假设其态坍缩为$z=a^{l}modN$。因为$f(x)$的周期为$r$，所以$a^{l}modN=a^{l+jr}modN(l<r,j=0,1,\cdots ,A),A$是小于$(2^m-l)/r$的最大整数，因此有：
$$x=l,l+r,\cdots ,l+Ar$$
$|R_2⟩$坍缩时，$|R_1⟩$相对应地坍缩为：
$$|R_1⟩=\frac{1}{\sqrt{A+1}}\sum _{j=0}^A|l+jr⟩$$
可见，$|R_1⟩$是以$r$为周期的一组态的叠加。若$2^m$是$r$的整数倍，设$A=2^m/r-1$,有：
$$|R_1⟩=\sqrt{\frac{r}{2^m}}\sum _{j=0}^{2^m/r-1}|l+jr⟩=\sum _{x=0}^{2^m/r-1}f(x)|x⟩$$
其中，若$x-l$为$r$的整数倍，那么$f(x)=\sqrt{r/2^m}$；否则，$f(x)=0$.
此时，对$|R_1⟩$作量子傅里叶变换，有：
$$|R_1{⟩}_{QFT}={\sum }_c^{\sim }f(c)|c⟩,\tilde{f}(c)=\frac{\sqrt{r}}{2^m}\sum _{j=0}^{2^m/r-1}{e}^{2\pi (l+jr)c/2^m}=\frac{\sqrt{r}}{2^m}{e}^{2\pi jrc/2^m}c$$
当$c$为$2^m/r$的整数倍时，$\frac{\sqrt{r}}{2^m}\sum _{j=0}^{2^m/r-1}{e}^{2\pi (l+jr)c/2^m}=\frac{2^m}{r}$，否则$\frac{\sqrt{r}}{2^m}\sum _{j=0}^{2^m/r-1}{e}^{2\pi (l+jr)c/2^m}=0$
量子傅里叶变换增强了所需要的结果，使不需要的结果的概率为$0$。由此可得，若$c$为$2^m/r$的整数倍$k$时，有：
$$|R_1{⟩}_{QFT}=\frac{1}{\sqrt{r}}\sum _{k=0}^{r-1}{e}^{2\pi lk}|\frac{k{2}^m}{r}⟩$$
即周期从$r$变为$2^m/r$
此时测量$|R_1⟩$_{QFT}，得到$c^{{}^{\prime }}=\frac{k{2}^m}{r}$，故$\frac{c^{{}^{\prime }}}{2^m}=\frac{k}{r}$。因为$c^{{}^{\prime }}$和$2^m$均已知，若$gcd(k,r)=1$，则可求出$r$。最大的$r$记为所求的$f(x)$的周期。
将$Shor$算法用于例$1$可得：
$$\begin{gathered} |{\Psi }_3⟩=\frac{1}{\sqrt{2^4}}\sum _{x=0}^{2^4-1}|x⟩|a^{x}modN⟩=\frac{1}{\sqrt{2^4}}(|0,1⟩+|1,7⟩+|2,4⟩+|3,13⟩+|4,1⟩+\cdots +|15,13⟩) \\ =\frac{1}{\sqrt{2^4}}[(|0⟩+|4⟩+|8⟩+|12⟩)\otimes |1⟩+\cdots ] \end{gathered}$$
投影算符$P_{|1⟩}=|1⟩⟨1|$，有：
$$|{\Psi }_4⟩=\frac{1}{\sqrt{2^4}}=\frac{1}{2^4}(|0⟩+|4⟩+|8⟩+|12⟩)\otimes (|1⟩⟨1|)|1⟩$$
已知，对$|x⟩$作傅里叶变换为：
$$QFT:|x⟩\to \frac{1}{{\sqrt{2}}^m}\sum _{k=0}^{2^m-1}{e}^{2\pi ikx/2^m}|k⟩=\frac{1}{\sqrt{2^4}}\sum _{k=0}^{2^4-1}{e}^{2\pi ikx/16}|k⟩$$
那么对$|0⟩,|4⟩,|8⟩,|12⟩$分别做傅里叶变换，有：

将上述四个式子相加可得：
$$\frac{1}{\sqrt{4}}(|0⟩+|4⟩+|8⟩+|12⟩)$$
由此，可以得到周期为$r=4$，且$a^{\frac{r}{2}}modN=7^{\frac{4}{2}}mod15=4\ne 1$，那么有$p=gdc(50,15)=5,q=gcd(48,15)=3$。
$Shor$算法不能保证每次运行都能得到正确的结果。假设成功的概率是$1-j$，通过重复$k$次实验，至少成功一次的概率为$1-j^k$。不难看出，可以通过增加实验的次数来提高实验成功的概率。所以$Shor$算法是一种随机算法。

今天的文章《基于张量网络的机器学习入门》学习笔记8(Shor算法)分享到此就结束了，感谢您的阅读。