量子计算 [7] -- Shor算法

2021-05-01 20:24 作者:nyasyamorina 0人读过 | 我要投稿

本文是对Shor算法的原理进行讨论, 至于算法实现应该是放在附章里的.

Shor算法是一个在多项式时间内进行整数分解的算法. 整数分解就是给出一个整数N, 找到两个整数相乘后等于N. 在电子计算机里, 目前最好的方法依然需要指数时间对整数进行分解. 至于可以快速进行整数分解对密码学有什么影响这里也不说了, 看腻了好吧.

下面将会大量用到模运算和最大公因数两个概念, 简单复习一下.

在小学学习的除法定义为 a÷b=c...d, 其中a,b,c,d都为整数, 并且d<b. 则模运算定义为 a%b=d[其实应该写为 `a mod b = d`, 这里用python的模运算符号`%`代替`mod`了].

a与b的最大公因数(greatest common divisor)定义为同时整除a和b的最大数字, 写为gcd(a,b). gcd可以使用欧几里得算法快速求得. 这里也不详细叙述......ffffine, 下面贴出gcd的python代码

量子计算机并不能直接地对整数进行分解, Shor算法是把整数分解转化为求阶问题.

但在使用量子算法求阶之前, 符合某些条件的数字可以由传统算法很快地分解. 比如说如果数字的二进制表示的最小位为0, 那么这个数字是偶数, 2必定是它的因数. 还有对于整数 $N%3Dp%5Eq$ ; $p%5Cgeq1%2Cq%5Cgeq2$ , 使用传统算法可以以多项式时间求出因数p [具体实现我也不太清楚, 欢迎大佬在评论区补充]. 经过筛选之后, 剩下的就是Shor算法的讨论范围了.

记需要分解的整数为N, 给出一个整数 $a%5Cin%5B2%2CN)$ , 并且满足 $gcd(a%2CN)%3D1$ , 那么 $a(%5C%25N)$ 的阶r定义为函数 $f(x)%3Da%5Ex%5C%25N$ 的最小正周期, 其中 $x%5Cin%5Cmathbb%20Z$ .

因为r为f(x)的周期, 则有 $a%5Er%5Cequiv%20a%5E0%5Cequiv1(%5C%25N)$ ⇒ $(a%5Er-1)%5C%25N%3D0$ , 也就是说 $a%5Er-1$ 可以被N整除.

如果r为偶数, 有 $a%5Er-1%3D(a%5E%7Br%2F2%7D-1)(a%5E%7Br%2F2%7D%2B1)$ , 那么 $gcd(a%5E%7Br%2F2%7D-1%2CN)$ 和 $gcd(a%5E%7Br%2F2%7D%2B1%2CN)$ 都为N的因数. 其中 $gcd(a%5E%7Br%2F2%7D-1%2CN)$ $%5Cneq%20N$ , 如果 $gcd(a%5E%7Br%2F2%7D-1%2CN)$ $%3DN$ , 则有 $(a%5E%7Br%2F2%7D-1)%5C%25N%3D0$ ⇒ $a%5E%7Br%2F2%7D%5C%25N%3D1$ , 这与阶r的定义冲突: r为f(x)的最小正周期. 如果 $gcd(a%5E%7Br%2F2%7D-1%2CN)$ $%3D1$ , 因为 $(a%5E%7Br%2F2%7D-1)(a%5E%7Br%2F2%7D%2B1)%5Cequiv0(%5C%25N)$ , 则有 $a%5E%7Br%2F2%7D%2B1%5Cequiv0(%5C%25N)$ ⇒ $a%5E%7Br%2F2%7D%5Cequiv-1%5Cequiv%20N-1(%5C%25N)$ .

根据上面的推论, Shor算法过程为:

随机在 $%5B2%2CN-1)$ 中选择一个数字a
计算gcd(a,N), 如果不等于1, 则得到N的一个因数: $gcd(a%2CN)$
使用量子计算机得出a(%N)的阶r
如果r为奇数, 或 $a%5E%7Br%2F2%7D%5C%25N%3DN-1$ , 则返回第1步
得到 $N$ 的两个因数: $gcd(a%5E%7Br%2F2%7D-1%2CN)$ 和 $gcd(a%5E%7Br%2F2%7D%2B1%2CN)$

把 $N$ 写为质数的乘积, 即 $N%3D%5Cprod%5Cnolimits_%7Bi%3D1%7D%5Emp_i%5E%7Bq_i%7D$ , 其中 $p_i$ 为质数, $q_i%5Cgeq1$ . 记r_i为 $a(%5C%25p_i%5E%7Bq_i%7D)$ 的阶, 那么r为r_i的最小公倍数(least common multiple). 如果r_i全部都为奇数, 那么r也为奇数, 即r/2不存在[应该说不是整数]; 如果r_i全部都为偶数, 因为 $a%5E%7Br_i%2F2%7D%5Cequiv-1(%5C%25p_i%5E%7Bq_i%7D)$ , 有 $a%5E%7Br%2F2%7D%5Cequiv-1(%5C%25N)$ . r_i同时全为奇数或偶数的概率为 $%5Cfrac%7B1%7D%7B2%5E%7Bm-1%7D%7D$ , 也就是算法的成功率为 $1-%5Cfrac%7B1%7D%7B2%5E%7Bm-1%7D%7D$ . 当m=1时, 算法成功率为0, 也就是说最开始使用传统算法把 $N%3Dp%5Eq$ 筛选掉是必须的.

下面来讨论Shor算法里的第三步 -- 使用量子计算机得出a(%N)的阶r

考虑模乘函数 $(ay)%5C%25N$ , 并有相应的位门 $U_%7Ba%2CN%7D%3A%7Cy%5Crangle%5Crightarrow%7C(ay)%5C%25N%5Crangle$ , 为了满足可逆条件, 规定 $y%3CN$ . 对于 $y%5Cgeq%20N$ , 有 $U_%7Ba%2CN%7D%3A%7Cy%5Crangle%5Crightarrow%7Cy%5Crangle$ . [一般来说不考虑y>=N的情况]

观察下面电路, 并分析态 $%7Cy%5Crangle$ 的变化, $y%5Cleq%20N$ :

$%5Cbegin%7Barray%7D%7B9%7D%7Cy%5Crangle%5Crightarrow%20U%5E%7Bx_12%5E0%7D_%7Ba%2CN%7D%7Cy%5Crangle%5C%5C%5C%3B%5C%3B%5C%3B%5C%3B%5C%3B%5C%3B%3D%7C(a%5E%7Bx_12%5E0%7Dy)%5C%25N%5Crangle%5C%5C%5C%3B%5C%3B%5C%3B%5C%3B%5C%3B%5C%3B%5Crightarrow%20U%5E%7Bx_22%5E1%7D_%7Ba%2CN%7D%7C(a%5E%7Bx_12%5E0%7Dy)%5C%25N%5Crangle%5C%5C%5C%3B%5C%3B%5C%3B%5C%3B%5C%3B%5C%3B%3D%7C(a%5E%7Bx_22%5E1%7Da%5E%7Bx_12%5E0%7Dy)%5C%25N%5Crangle%20%5C%5C%5C%3B%5C%3B%5C%3B%5C%3B%5C%3B%5C%3B%5Cvdots%5C%5C%5C%3B%5C%3B%5C%3B%5C%3B%5C%3B%5C%3B%5Crightarrow%20U%5E%7Bx_n2%5E%7Bn-1%7D%7D_%7Ba%2CN%7D%7C(%5Ccdots%20a%5E%7Bx_22%5E1%7Da%5E%7Bx_12%5E0%7Dy)%5C%25N%5Crangle%5C%5C%5C%3B%5C%3B%5C%3B%5C%3B%5C%3B%5C%3B%3D%7C(a%5E%7Bx_n2%5E%7Bn-1%7D%7D%5Ccdots%20a%5E%7Bx_22%5E1%7Da%5E%7Bx_12%5E0%7Dy)%5C%25N%5Crangle%5C%5C%5C%3B%5C%3B%5C%3B%5C%3B%5C%3B%5C%3B%3D%7C(a%5E%7Bx_n2%5E%7Bn-1%7D%2B%5Ccdots%2Bx_22%5E1%2Bx_12%5E0%7Dy)%5C%25N%5Crangle%5C%5C%5C%3B%5C%3B%5C%3B%5C%3B%5C%3B%5C%3B%3D%7C(a%5Exy)%5C%25N%5Crangle%5Cend%7Barray%7D$

可以看到这个电路等价于模幂位门 $%7Cx%5Crangle%7Cy%5Crangle%5Crightarrow%7Cx%5Crangle%7C(a%5Exy)%5C%25N%5Crangle$ .

构造一个态 $%7Cu_s%5Crangle%3D%5Cfrac%7B1%7D%7B%5Csqrt%20r%7D%5Csum%5Cnolimits_%7Bk%3D0%7D%5E%7Br-1%7De%5E%7B-2%5Cpi%20iksr%5E%7B-1%7D%7D%7Ca%5Ek%5C%25N%5Crangle$ , $s%5Cin%5B0%2Cr)%5Ccap%5Cmathbb%20Z$ , 其中r为 $a(%5C%25N)$ 的阶, 容易证明这个态是位门 $U_%7Ba%2CN%7D$ 的特征态: $U_%7Ba%2CN%7D%7Cu_s%5Crangle$ = $%5Cfrac%7B1%7D%7B%5Csqrt%20r%7D%5Csum%5Cnolimits_%7Bk%3D0%7D%5E%7Br-1%7De%5E%7B-2%5Cpi%20iksr%5E%7B-1%7D%7D%7C(a%5Ccdot%20a%5Ek)%5C%25N%5Crangle$ = $%5Cfrac%7B1%7D%7B%5Csqrt%20r%7D%5Csum%5Cnolimits_%7Bk%3D1%7D%5E%7Br%7De%5E%7B-2%5Cpi%20i(k-1)sr%5E%7B-1%7D%7D%7Ca%5Ek%5C%25N%5Crangle$ = $%5Cfrac%7B1%7D%7B%5Csqrt%20r%7De%5E%7B2%5Cpi%20isr%5E%7B-1%7D%7D%5Csum%5Cnolimits_%7Bk%3D1%7D%5E%7Br%7De%5E%7B-2%5Cpi%20iksr%5E%7B-1%7D%7D%7Ca%5Ek%5C%25N%5Crangle$ , 当k=r时, 因为 $a%5Er%5Cequiv%20a%5E0(%5C%25N)$ , 则有 $e%5E%7B-2%5Cpi%20irsr%5E%7B-1%7D%7D%7Ca%5Er%5C%25N%5Crangle$ = $e%5E%7B-2%5Cpi%20i0sr%5E%7B-1%7D%7D%7Ca%5E0%5C%25N%5Crangle$ , 即 $U_%7Ba%2CN%7D%7Cu_s%5Crangle$ = $%5Cfrac%7B1%7D%7B%5Csqrt%20r%7De%5E%7B2%5Cpi%20isr%5E%7B-1%7D%7D%5Csum%5Cnolimits_%7Bk%3D0%7D%5E%7Br-1%7De%5E%7B-2%5Cpi%20iksr%5E%7B-1%7D%7D%7Ca%5Ek%5C%25N%5Crangle$ = $e%5E%7B2%5Cpi%20isr%5E%7B-1%7D%7D%7Cu_s%5Crangle$ . 从而得到特征值为 $e%5E%7B2%5Cpi%20isr%5E%7B-1%7D%7D$ . 因为不知道r, 所以任何独立的特征态都是无法制备的.

把全部特征态叠加起来, 得到 $%5Cfrac%7B1%7D%7B%5Csqrt%20r%7D%5Csum%5Cnolimits_%7Bs%3D0%7D%5E%7Br-1%7D%7Cu_s%5Crangle$ = $%5Cfrac%7B1%7D%7Br%7D%5Csum%5Cnolimits_%7Bs%3D0%7D%5E%7Br-1%7D%5Csum%5Cnolimits_%7Bk%3D0%7D%5E%7Br-1%7De%5E%7B-2%5Cpi%20iksr%5E%7B-1%7D%7D%7Ca%5Ek%5C%25N%5Crangle$ = $%5Cfrac%7B1%7D%7Br%7D%5Csum%5Cnolimits_%7Bk%3D0%7D%5E%7Br-1%7D%7Ca%5Ek%5C%25N%5Crangle%5Csum%5Cnolimits_%7Bs%3D0%7D%5E%7Br-1%7De%5E%7B-2%5Cpi%20iksr%5E%7B-1%7D%7D$ 后面的累加由等比数列和求出, 得 $%5Cfrac%7B1%7D%7Br%7D%5Csum%5Cnolimits_%7Bk%3D0%7D%5E%7Br-1%7D%7Ca%5Ek%5C%25N%5Crangle%5Cfrac%7B1-e%5E%7B-2%5Cpi%20ik%7D%7D%7B1-e%5E%7B-2%5Cpi%20ikr%5E%7B-1%7D%7D%7D$ . 在k=0时, 分式未定义, 对其取极限可以得到分式的值为 $r$ [不取极限, 直接计算累加式也可以得到相同的答案]; 而k≠0时, 分子为0, 由此化简叠加态为 $%5Cfrac%7B1%7D%7Br%7D%7Ca%5Er%5C%25N%5Crangle%20r$ = $%7C1%5Crangle$ .

由上可得, 以 $%7C1%5Crangle$ 为叠加特征态, 对位门 $U_%7Ba%2CN%7D%3A%7Cy%5Crangle%5Crightarrow%7C(ay)%5C%25N%5Crangle$ 进行相位估计可以测得s/r, 其中 $s%5Cin%5B0%2Cr)%5Ccap%5Cmathbb%20Z$ . 这Shor算法里的量子电路为

其中Modular Power为模幂位门: $%7Cx%5Crangle%7Cy%5Crangle%5Crightarrow%7Cx%5Crangle%7C(a%5Exy)%5C%25N%5Crangle$ , 并且 $m%3D%5Clceil%5Clog_2N%5Crceil$ , ⌈⌉为向上取整.

因为测量量子位的结果为整数, 并且相位估计算法也有可能不会给出最佳近似值, 所以测量结果与实际值之间会存在一定误差. 设测量结果为 $j_s$ , 那么有 $j_s%2F2%5En%5Capprox%20s%2Fr$ , 对 $j_s%2F2%5En$ 展开为连分数, 则在展开式的某一部分截断可能会得到准确的s/r. 并且注意到gcd(s,r)有可能不为1, 也就是说分式s/r有可能不为最简分式. 为了提高算法成功率, 可以对 $j_s-1$ 和 $j_s%2B1$ 也进行连分数展开. 得到r后执行Shor算法下面几步即可以得到N的分解结果.

定理: 如果满足 $%7Cj_s%2F2%5En-s%2Fr%7C%5Cleq1%2F(2r%5E2)$ , 那么s/r是 $j_s%2F2%5En$ 连分数的一个渐进值. 即 $2%5En%5Cgeq2r%5E2$ , 因为r<N, 所以可以取 $2%5En%3D2N%5E2$ , 得到 $n%3D1%2B2%5Clog_2N%5Capprox1%2B2m$ .

是Shor算法的量子求阶电路里, 模幂位门的实现方法各种各样, 有时间复杂度低的方法, 但使用了很多量子位; 有使用少量量子位的, 但时间复杂度很高.

附章将介绍一种只使用极少量子位的Shor算法实现. 因为在电子计算机上模拟量子计算所需的内存是随着量子位数量增长而指数增长的. 使用尽可能少的量子位可以确保电子计算机也可以进行模拟.

在第一版Shor算法里, 模幂位门定义为 |x❭|y❭ -> |x❭|(y+a^x)%N❭, 则导致下面的量子位应该初始化为|0❭而不是|1❭. 这是因为第一版Shor算法并不是使用相位估计方法求阶, 而是直接对模幂函数进行周期分析. 虽然两个版本之间存在差异, 但绝大部分都是一致的, 并且都是求得s/r.

封面pid: 66444938

"""你已经插入152张图片了, 目前最多支持插入100张哦~""". 口区

标签：

量子计算 [7] -- Shor算法

量子计算 [7] -- Shor算法的评论 (共条)

你可能也喜欢这些文章

最新发布的文章

量子计算 [7] -- Shor算法

本文作者的其他文章

量子计算 [7] -- Shor算法的评论 (共 条)

你可能也喜欢这些文章

最新发布的文章

量子计算 [7] -- Shor算法的评论 (共条)