Shor's Algorithm

传统部分成功率的数学证明参考 B 站视频 Shor算法 | 如何用量子计算机分解质因数？

构造素因子的传统方法（初等数论）

1: 找一个整数 \(1<a<N\) ，计算 \(\operatorname{gcd}(a, N)\)

2: 若 \(\operatorname{gcd}(a, N)>1\) ，则已经找到了 \(N\) 的一个非平凡因子

3: 若 \(\operatorname{gcd}(a, N)=1\) ，则用量子算法找到最小的满足 \(a^{r} \equiv 1(\bmod N)\) 的正整数 \(r\) （也称作 \(a\) 模 \(N\) 的阶， \(\left.r=\operatorname{ord}_{N}(a)\right)\)

4: 若 \(2 \nmid r\) ，或 \(a^{\frac{r}{2}} \equiv-1(\bmod N)\) ，则返回第一步重新找一个 \(a\)

5: 若 \(2 \mid r\) ，且 \(a^{\frac{r}{2}} \not \equiv-1(\bmod N)\) ，则有 \(N \mid\left(a^{\frac{r}{2}}+1\right)\left(a^{\frac{r}{2}}-1\right)\) ，可以证明，通过求出 \(\operatorname{gcd}\left(a^{\frac{r}{2}}+1, N\right)\) 或 \(\operatorname{gcd}\left(a^{\frac{r}{2}}-1, N\right)\) 一定可以找到 \(N\) 的一个非平凡因子

r为偶的成功率（算法成功率）

这里 \(a\) 为 \(a=1,2, \cdots ,N-1\) 中的随机数，令 \(r=\text{ord}_{N}(a)\) \(,P(\mbox{success})\)\(=P\left(2 \mid r \wedge a^{\frac{r}{2}} \not \equiv-1(\bmod N)\right)\)

分解 \(N\) 有 \(N=p_{1}^{\alpha_{1}} p_{2}^{\alpha_{2}} \cdots p_{m}^{\alpha_{m}}\) 由有限阿贝尔群的基本定理：

模 \(\mathrm{N}\) 乘法群 \((\mathbb{Z} / N \mathbb{Z})^{\times}\)可分解为若干循环群的直积。例如对下列表格，实际为中国剩余（孙子）定理的解

\(5\) 和 \(7\) 分别在模 \(7\) 和模 \(5\) 意义下的数论倒数为 \(3\) 和 \(3\)，所以对元素 \(a\in( \mathbb{Z} / 5 \mathbb{Z})^{\times},b\in( \mathbb{Z} / 7 \mathbb{Z})^{\times}\)

其直积的计算为 \(a\cdot 3\cdot 7+b\cdot 3\cdot 5=3(7a+5b)\)，如 \(a=4,b=6,3(28+30)=174=34\pmod{35}\)

\[ \begin{aligned} &\begin{array}{r|cccccc} (\mathbb{Z} / 5 \mathbb{Z})^{\times}\large {\backslash}\normalsize (\mathbb{Z} / 7 \mathbb{Z})^{\times} & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline1 & 1 & 16 & 31 & 11 & 26 & 6 \\ 2& 22 & 2 & 17 & 32 & 12 & 27 \\ 3& 8 & 23 & 3 & 18 & 33 & 13 \\ 4& 29 & 9 & 24 & 4 & 19 & 34 \end{array} \end{aligned} \]

\((\mathbb{Z} / N \mathbb{Z})^{\times} \cong\left(\mathbb{Z} / p_{1}^{\alpha_{1}} \mathbb{Z}\right)^{\times} \times\left(\mathbb{Z} / p_{2}^{\alpha_{2}} \mathbb{Z}\right)^{\times} \times \cdots \times\left(\mathbb{Z} / p_{m}^{\alpha_{m}} \mathbb{Z}\right)\) ，\(\left(\mathbb{Z} / p_{i}^{\alpha_{i}} \mathbb{Z}\right)^{\times} \cong C_{\varphi(p^{\alpha})}\left(p_{i}>2\right)\) \[ \begin{aligned} &a=1 \ldots N-1, r=\operatorname{ord}_{N}(a) \\ &P(\text { success })=P\left(2 \mid r \wedge a^{\frac{r}{2}} \not \equiv-1 \quad(\bmod N)\right) \\ &N=p_{1}^{\alpha_{1}} p_{2}^{\alpha_{2}} \cdots p_{m}^{\alpha_{m}} \end{aligned} \] 定义 \(r=\operatorname{ord}_{N}(a), r_{i}=\operatorname{ord}_{p_{i}^{\alpha_{i}}}(a)\) ，有 \(r=\operatorname{lcm}\left(r_{1}, r_{2}, \ldots, r_{m}\right) ， 2 \nmid r \Longleftrightarrow \forall i, 2 \nmid r_{i}\) 定义 \(v_{2}(n)=\max _{k}\left\{2^{k} \mid n\right\}\) 表示 \(n\) 中因子 \(2\) 的次数， \[ \begin{aligned} a^{\frac{r}{2}} \equiv-1 \quad(\bmod N) & \Longleftrightarrow \forall i, a^{\frac{r}{2}} \equiv-1 \quad\left(\bmod p_{i}^{\alpha_{i}}\right) \\ & \Longleftrightarrow \forall i, 2 \nmid r / r_{i} \\ & \Longleftrightarrow \forall i, j, v_{2}\left(r_{i}\right)=v_{2}\left(r_{j}\right) \end{aligned} \] 对于随机的 \(a\) ，不能通过 \(a\) 找到 \(N\) 的非平凡因子当且仅当 \(\forall i, j, v_{2}\left(r_{i}\right)=v_{2}\left(r_{j}\right)\)

\[ P\left(v_{2}\left(r_{i}\right)=t\right)= \begin{cases}\dfrac{1}{2^{v_{2}(\varphi(n))}} & t=0 \\ \dfrac{1}{2^{v_{2}(\varphi(n))-t+1}} & 1 \leq t \leq v_{2}(\varphi(n))\end{cases} \] 对于与 \(N\) 互质的所有 \(a\) ，失败概率 \[ P(\text { fail })=P\left(2 \nmid r \vee a^{\frac{r}{2}} \equiv-1 \quad(\bmod N)\right)=\sum_{t} \prod_{i} P\left(v_{2}\left(r_{i}\right)=t\right) \] 当 \(N=p^{k}, 2 p^{k},(k \geq 1)\) 时， \(P(\)\(\mbox{fail}\)\()=1\) ，否则 \(P(\)\(\mbox{fail}\)\() \leq \dfrac{1}{2}\)

这些情况也可以设计量子电路在更小的时间复杂度内得到判定，从而成功概率 \(>\dfrac{1}{2}\)

将求阶算法转换为相位估计法

对于酉变换 \(U:|y\rangle\mapsto|xy\pmod{N}\rangle\)，已知 \(r\) 为 \(x\) 模 \(N\) 的阶，即满足 \(x^{t}\equiv 1\pmod{N}\) 的最小正整数 \(t\)

任取 \(0\leq s\leq r-1\)，则可以构造性地给出 \(U\) 变换的一个特征向量 \[ |u_s\rangle=\large \dfrac{1}{\sqrt{r}}\sum_{k=0}^{r-1}e^{-\frac{2\pi isk}{r}}|x^{k}\bmod{N}\rangle \] 计算可知 \(U|u_s\rangle=\dfrac{1}{\sqrt{r}}\displaystyle \sum_{k=0}^{r-1}e^{-\frac{2\pi isk}{r}}|x^{k+1}\bmod{N}\rangle=\dfrac{1}{\sqrt{r}}e^{\frac{2\pi is}{r}}\sum_{k=0}^{r-1}e^{-\frac{2\pi is(k+1)}{r}}|x^{k+1}\bmod{N}\rangle\) 由 \(x^{r}=1\)

则 \(\{x,x^2,\cdots,x^{r-1},x^{r}\}=\{1,x,x^2,\cdots,x^{r-1}\}\) 则 \(\boxed{U|u_s\rangle=e^{\frac{2\pi is}{r}}|u_s\rangle}\)，故 \(e^{\frac{2\pi is}{r}}\) 为 \(U\) 的特征值

从而制备酉变换 \(U\)，只要确定 \(\epsilon\) 精度内的相位 \(\small\Delta \normalsize \varphi =\dfrac{2\pi s}{r}\)（误差分析给出比特数 \(t=n+\left \lceil \log \left(2+\dfrac{1}{2\epsilon}\right)\right\rceil\)）

便在一定精度内得到 \(s=\dfrac{ \small\Delta \normalsize \varphi r}{2\pi}\)，由连分式算法，任意有理数连分式经过有限步可以终止，从而 \(s\) 可求

相位估计法

在给定精度得到相应需要 \(t\) 比特后，搭建如下量子电路：

通俗来说，上面 \(t\) 比特给出一系列“平铺”的量子纠缠态，具体写成数学表达式有 \[ \begin{aligned} \frac{1}{2^{t / 2}}\left(|0\rangle+e^{2 \pi i 2^{t-1} \varphi}|1\rangle\right)\left(|0\rangle+e^{2 \pi i 2^{t-2} \varphi}|1\rangle\right) & \ldots\left(|0\rangle+e^{2 \pi i 2^{0} \varphi}|1\rangle\right) \\ &=\frac{1}{2^{t / 2}} \sum_{k=0}^{2^{t}-1} e^{2 \pi i \varphi k}|k\rangle . \end{aligned} \] 这里求和式的结果可以观察为二进制展开得到，用逆快速傅里叶变换便可以 \(t\) 位（概率为 $1-$）精度的 \(\varphi\)

只要设计上符合各精度要求，便可以逼近得到实例酉变换的相位 \(\varphi\)，进而用连分数算法逼近出一个随机数 \(a\) 模 \(N\) 意义下的阶 \(s\)，该 \(s\) 为偶数的概率也是可观的（ \(> \dfrac{1}{2}\)），实在不行的话多尝试几个随机数 \(a\)，只要找到一个阶数为偶数的 \(a\)，便可以使用欧几里得算法得到 \(N\) 的一个非平凡素因子。

至此，从理论上大数分解在量子计算机中可以有效（多项式时间复杂度）求出，具体复杂度上界为 \[ O(N^2\log N\log \log N) \] 远超经典计算机（目前为 \(O(2^{(\log N)^c}),c=\dfrac{1}{2}\ \mbox{or } c=\dfrac{1}{3}\) 后者基于一个数论猜想），达到指数加速

总结

根据当今密码学的应用，如果这个算法被真正实现于硬件（需要解决纯化、噪声等一系列问题）并证明有效，

当前的 \(\mbox{RSA}\) 公钥体系，以及基于椭圆曲线的加密体系都可以在 \(\mbox{Shor}\) 算法的框架进一步优化下得到有效破解

可以说，大部分互联网所谓的安全加密体系都会被崩塌，美国甚至成立了后量子密码协议，专门用于对抗量子算法对当前算法的威胁，不过至少当前经典密码学中的格密码学未被量子算法所破解，许多加密协议可以通过引入格密码学的方式更加安全。

我之所以费尽心思写这篇 \(\mbox{Shor}\) 算法，是因为我好久没有过被这种数理构思所折服的感觉了，上次应该是高一推导分析力学最终得到最小作用量原理 \(\delta S=0\) 的时候，希望探索世界总能带给我震撼……

不知道几十年后的发展怎么样，个人还是有所期待和充满信心吧，这些算法基本都是 \(25\) 年前提出的，不知道这些算法最后会对人类有害，还是有利，个人还是希望生产力的解放带来全球的福祉吧。