本节将详细介绍shor算法以及通过开源库qiskit实现该算法的详细过程，更细致全面的内容请移步https://www.bilibili.com/video/BV1a4411M7cU?p=5
Shor算法简介
算法执行步骤
设待分解的大数为N，它的平方用二进制表示有 L L L位，即 N 2 < 2 L < 2 N 2 N^2<2^L<2N^2 N2<2L<2N2,选用的周期性函数为余函数类
f ( x ) = a x m o d N （ 式 1 ） f(x) = a^x mod N（式1） f(x)=axmodN（式1）
这里 a ( a < N ) a(a
a(a<N)
明显可以看出， f ( x ) f(x) f(x)所取的值属于正整数集合 1 , 2 , … , N − 1 {1,2,\dots,N-1} 1,2,…,N−1，且是周期性函数。
那么一旦求出了周期T，设T为偶数(若求出T为奇数，则另选 a a a重来)，则令 A = a T 2 + 1 , B = a T 2 − 1 A=a^\frac{T}{2}+1,B=a^\frac{T}{2}-1 A=a2T+1,B=a2T−1，求 ( A , N ) (A,N) (A,N)和 ( B , N ) (B,N) (B,N)的最大公约数C和D。那么由数论的知识可知C和D就是N的素因子，算法执行完毕。
那么现在还剩下一个问题没有解决，那就是如何求周期T，一旦周期求出来，那么质因子也能够轻而易举的计算出来。
首先取两组各有L个量子比特的存储器，通过幺正变换实现以下的纠缠状态
∑ i = 1 n ∣ x 1 > ⨂ ∣ f ( x 1 ) > = ∣ x 1 > ⨂ ∣ f ( x 1 ) > + ∣ X 2 > ⨂ ∣ f ( x 2 ) > + . . . + ∣ x n > ⨂ ∣ f ( x n ) > \sum_{i=1}^n{|x_1>\bigotimes|f(x_1)>}\\ =|x_1>\bigotimes|f(x_1)> + |X_2>\bigotimes|f(x_2)>+…+|x_n>\bigotimes|f(x_n)> i=1∑n∣x1>⨂∣f(x1)>=∣x1>⨂∣f(x1)>+∣X2>⨂∣f(x2)>+...+∣xn>⨂∣f(xn)>
式子中的 f ( x ) f(x) f(x)就是式1定义的余函数。 n = 2 L n=2^L n=2L，为了找到整体的周期，我们把x也转换成周期为T的函数，通过离散傅里叶变换就可以实现。
∣ x > = 1 ( 2 L ) ∑ k = 0 2 L − 1 e 2 π i k x / 2 L ∣ k > （ 式 2 ） |x>=\frac{1}{\sqrt(2^L)}\sum_{k=0}^{2^L-1}e^{2\pi ikx/2^L |k>}（式2） ∣x>=(2L)1k=0∑2L−1e2πikx/2L∣k>（式2）
然后将 x x x代入量子比特纠缠态得到式3
∣ ψ > = 1 2 L ∑ x = 0 2 L − 1 ∑ k = 0 2 L − 1 e 2 π i k x / 2 L ∣ k > ⨂ f ( x ) > |\psi>=\frac{1}{\sqrt2^L}\sum_{x=0}^{2^L-1}\sum_{k=0}^{2^L-1}e^{2\pi ikx/2^L} |k>\bigotimes f(x)> ∣ψ>=2L1x=0∑2L−1k=0∑2L−1e2πikx/2L∣k>⨂f(x)>
这个式子看起来很复杂，其实只不过是将式2代入式1后合并整理得到的结果
由于 f ( x ) f(x) f(x)具有周期性，式子中可以合并同类项，并且由于正交基的存在，大部分项也可以相消，只有k取下列值时系数不为零：
k = [ m 2 L T ] （ m = 0 , 1 ， … , T − 1 ） k=[m\frac{2^L}{T}]（m=0,1，\dots,T-1） k=[mT2L]（m=0,1，…,T−1）
那么当 k ≠ 0 k\not=0 k=0时
2 L / k ≈ T m 2^L/k \approx \frac{T}{m} 2L/k≈mT
对k存储器进行测量，能够得到k的本征值， L L L和 m m m又已知，那么显然就能解出周期 T T T的值啦。随后就能根据之前已经说明的公式求出 A , B A,B A,B进而求出大数N的两个质因子。
上述公式中余函数是Shor精心挑选的用来处理此类问题的较合适的周期函数，记牢就可以了。其次就是函数转化为傅里叶级数这一部分需要去巩固一下高数相关的知识。事实上，非周期函数可以通过对称找到合适的变换。
Shor算法的简单实现(调包)
from qiskit import IBMQ from qiskit.aqua import QuantumInstance from qiskit.aqua.algorithms import Shor IBMQ.enable_account('ENTER API TOKEN HERE') # 输入自己的令牌 provider = IBMQ.get_provider(hub='ibm-q') backend = provider.get_backend('ibmq_qasm_simulator') # 指定量子设备 print('\nShors算法执行中') factors = Shor(21) # 分解551 result_dict = factors.run(QuantumInstance(backend, shots=1, skip_qobj_validation=False)) result = result_dict['factors'] # 获得分解结果 print(result) 运行之后返回一个数组，内容为[3,7]，也就是分解的结果。当分解的是大数时，运算速度与传统的方式就会出现很大的差别。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/212475.html原文链接：https://javaforall.net
