量子计算 [7].ext

2021-05-04 12:46 作者:nyasyamorina 0人读过 | 我要投稿

在本篇里讨论了Shor算法的原理, 在这里着手实现Shor算法. [arxiv.org/abs/quant-ph/0205095]

在下面将会大量用到QFT, 为了文本的简洁, 记

$QFT%3A%5Cbigotimes%5Cnolimits_%7Bl%3Dn%7D%5E1%7Cj_l%5Crangle%5Crightarrow2%5E%7B-%5Cfrac%7Bn%7D%7B2%7D%7D%5Cbigotimes%5Cnolimits_%7Bl%3Dn%7D%5E1(%7C0%5Crangle%2Bexp(2%5E%7B1-l%7D%5Cpi%20i(%5Csum_%7Bk%3D1%7D%5En2%5E%7Bk-1%7Dj_k))%7C1%5Crangle)$

为 $QFT%3A%7Cj%5Crangle%5Crightarrow%7C%5Cphi(j)%5Crangle$ . 注意这里QFT的定义为没有SWAP门.

并且会用到大量量子加法, 在给出一个已知的[或者说电子逻辑表示的]整数a, 有

$%5CPhi_a%3A%7C%5Cphi(x)%5Crangle%5Crightarrow%7C%5Cphi(a%2Bx)%5Crangle$

以及它的逆操作 $%5CPhi_a%5E%7B-1%7D$ .

下面开始正式构造Shor算法的量子电路.

Shor算法在第一版解释为对模幂函数进行周期分析, 但在第二版开始解释为对模乘函数进行相位估计. 两种解释只在"解释"会有差异, 计算结果是一样的. 因为暂时不存在很好的量子模幂位门, 所以使用第二种解释可以很大程度上化简电路 [化简版的相位估计]. 那么构造一个模乘位门 $U_%7Ba%2CN%7D%3A%7Cx%5Crangle%5Crightarrow%7C(ax)%5C%25N%5Crangle$ 即代表成功.

万物起源于微积分加法, 所以第一件事就是找到可行的模加位门

$%5CPhi_%7Ba%2C%5C%25N%7D%3A%7C%5Cphi(x)%5Crangle%5Crightarrow%7C%5Cphi((a%2Bx)%5C%25N)%5Crangle$

这并不是一件简单的事情, 因为模定义为全体整数到 [0,N) 的映射, 这明显是不可逆的. 为了保证模加位门的可逆性, 规定条件 $a%2Cx%5Cin%5B0%2CN)$ , 这时候 (a+x)%N 化简为 如果a+x<N, 则返回a+x; 否则返回a+x-N. 不难知道在给出a,N时, 这是一个x从[0,N)到[0,N)的满映射, 也就说这是可逆的.

如此, 可以先计算a+x-N, 如果计算结果小于0, 则加上N. 因为计算途中可能会出现负数, 需要使用额外的量子位来储存溢出[即电子计算机里整数的符号位]. 另外还需要一个量子位保存a+x-N小于0的结果再控制最后加上N的操作. 对于额外引入的两个量子位, 储存溢出的位还有使命仍未完成, 而控制加N操作的位在控制完之后需要被还原为|0❭. 又因为加法计算是在相位上的, 为了提取溢出位的结果, IQFT是必须的. 综上所述, 模加位门的构造为

红色部分计算(a+x)%N, 蓝色部分是为了还原最顶上的量子位. 实际上我们需要的 $%5CPhi_%7Ba%2C%5C%25N%7D$ 为红色和蓝色框, 框外的QFT只是表示输入和输出的形式. 下面给出模加位门的实现

模乘函数 $(ax)%5C%25N$ , 可以分解为 $(a%5Ctimes(2%5E%7Bn-1%7Dx_n%2B%5Ccdots%2B2%5E0x_1))%5C%25N$ , 又因为 $(x%2By)%5C%25N$ = $(x%5C%25N%2By%5C%25N)%5C%25N$ , 所以模乘函数可以写为

$(ax)%5C%25N%3D(((2%5E0ax_1)%5C%25N%2B2%5E1ax_2)%5C%25N%5Ccdots%2B2%5E%7Bn-1%7Dax_n)%5C%25N$

当某一步的 $x_l$ 为0时, 这步模加可以忽略不记, 所以可以简单地使用 $%7Cx_l%5Crangle$ 控制模加位门 $%5CPhi_%7B2%5E%7Bl-1%7Da%2C%5C%25N%7D$ 达到 $%7Cb%5Crangle%5Crightarrow%7C(b%2B2%5E%7Bl-1%7Dax_l)%5C%25N%5Crangle$ , 如此得到模乘位门 $M_%7Ba%2CN%7D%3A%7Cx%5Crangle%7Cb%5Crangle%5Crightarrow%7Cx%5Crangle%7C(ax%2Bb)%5C%25N%5Crangle$

需要注意的是这里输入的|b❭是含有溢出量子位的. 尽管溢出量子位在输入和输出都为|0❭.

现在离成功已经非常接近了, 如果模乘位门里的第二个寄存器为|0❭, 则有 $%7Cx%5Crangle%7C0%5Crangle%5Crightarrow%7Cx%5Crangle%7C(ax)%5C%25N%5Crangle$ , 可以看到所需的答案储存在第二个寄存器里, 而相位评估需要的位门必须是输出结果储存在输入寄存器里, 通过SWAP门可以将两个寄存器的信息交换. 交换完后需要对第二个寄存器进行还原, 否则它将带着错误的状态[不是0]进行下一次模乘.

因为模乘位门的逆为 $M_%7Ba%2CN%7D%5E%7B-1%7D%3A%7Cx%5Crangle%7Cb%5Crangle%5Crightarrow%7Cx%5Crangle%7C(b-ax)%5C%25N%5Crangle$ , 并且 $0%3Dx-a%5E%7B-1%7Dax$ , 所以还原第二个寄存器需要执行以a的逆元为基础的模乘位门的逆, 即 $M_%7Ba%5E%7B-1%7D%2CN%7D%5E%7B-1%7D%3A%7C(ax)%5C%25N%5Crangle%7Cx%5Crangle%5Crightarrow%7C(ax)%5C%25N%5Crangle%7C0%5Crangle$

于是相位评估里需要的模乘位门 $U_%7Ba%2CN%7D%3A%7Cx%5Crangle%5Crightarrow%7C(ax)%5C%25N%5Crangle$ 为

使用叠加特征态 $%7C1%5Crangle$ 对 $U_%7Ba%2CN%7D$ 进行相位估计, 就可以测得 $j_s%2F2%5En%5Capprox%20s%2Fr%2C%20s%5Cin%5B0%2Cr)%5Ccap%5Cmathbb%20Z$ , 求得r后就可以分解整数N了.

在相位估计里需要控制位门 $U%5E%7B2%5E%7Bl%7D%7D$ , 在无法进行化简的情况下, 这意味着需要运行 $2%5El$ 次位门U, 在精度要求比较高的情况下无疑会花费巨量的时间. 但对于多重模乘位门, 这是可以化简的:

$U_%7Ba%2CN%7D%5E%7B2%5El%7D%7Cx%5Crangle%3D%7C(%5Cunderbrace%7Ba%5Ccdots%20a%7D_%7B2%5El%7D%5Ctimes%20x%20)%5C%25N%5Crangle%3D%7C(a%5E%7B2%5El%7Dx)%5C%25N%5Crangle%3DU_%7Ba%5E%7B2%5El%7D%2CN%7D%7Cx%5Crangle$

在模乘位门里用到了a的逆元, 但直接计算1/a必定是小数, 而上述算法只能在整数下计算.

假设有一个整数b, 满足 $ab%5Cequiv1(%5C%25N)$ , 则称b为a在模N下的模逆元. 整数a有模逆元的充分必要条件为gcd(a,N)=1.

给出任意整数α和β, 使用扩展欧几里得算法可以在多项式时间里找到x, y和gcd(α,β), 并且满足 $%5Calpha%20x%2B%5Cbeta%20y%3Dgcd(%5Calpha%2C%5Cbeta)$ , 也就是 $%5Calpha%20x%5Cequiv%20gcd(%5Calpha%2C%5Cbeta)(%5C%25%5Cbeta)$ , 利用这个性质可以快速求得a在模N下的模逆元. 下面为求模逆元的算法 [实质上就是砍掉一部分的扩展欧几里得算法]

在Shor算法里有个挺严重的问题就是测量结果约为s/r, 在本篇里说过可以使用连分数展开去估计r的值. 但找了一圈都没有发现有什么比较直接的方法求得r, 下面是一种自制的暴力历遍的方法, 如果有什么更有效的方法欢迎在评论区补充.

首先需要分式和连分式互相转化的方法, 下面是一种可能的实现方法[只保证可以运行, 不保证效率.]

测量之后已知的数据有: 测量结果j, 测量精度n, 需要分解的整数N; 已知的条件为 r<N [尝试了几十种不同的a和N, 发现都有r<N/2, 是有什么我不知道的定理, 或者只是巧合?]. 对 $j%2F2%5En$ 进行连分式展开, 并逐段截断, 截断得到的分式的分母即有可能为r. 另外, 由于s/r有可能不是最简分式, 截断连分式得到的分母为r的概率约为φ(r)/r, φ(·)为欧拉函数, 即与r互质并且小于r的数字数量. It's that good enough? 确实, 对截断后的分母再乘上一些整数可以继续扩大r的候选列表, 但因为部分分母比较小, 把它的所有可能的整数倍[记得r<N]都放入候选列表之后, 虽然增加了单次运行量子程序得到r的概率, 但是花费在电子电路上的时间很有可能远远大于再次运行量子程序的时间, 并且很有可能引发新的问题[见下], 下面就是这一段昏睡咒语的代码实现

需要注意的是, 这里输出的列表的r的候选列表, 其中绝大部分都不是a(%N)的阶, 也就是说可能造成 $gcd(a%5E%7Br_%7B'%7D%2F2%7D-1%2CN)%3D1$ , 其中 $r_%7B'%7D$ 是上面函数输出的候选列表. 另外, 因为候选列表里可能含有阶r, 如果把候选列表里的数字乘上整数再放入候选列表[为了应对s/r不是最简分式的情况], 就会出现 $r_%7B'%7D%3D2r$ , 这时候计算 $gcd(a%5E%7Br_%7B'%7D%2F2%7D-1%2CN)%3DN$ , 因为 $a%5Er%5Cequiv1(%5C%25N)$ .

结合上面所有知识, 最后可以构造出Shor算法. 其实差了一步对 $N%3Dp%5Eq$ 特攻的传统算法, 就算不对这种情况过滤, 选取随机数时也有至少 $1%2F%5Csqrt%20N$ 的概率求得p的整数倍从而在计算gcd(a,N)时得到p. 如果有大佬知道p^q如何用传统算法求解的话, 欢迎在评论区补充.