解析Shor算法-量子人工智能引论

令N={0，1，2，3，...}表示自然数集。

素因子分解问题:给定一个复合的奇正整数N，找出它的素因子。

即给定一个正整数N，寻求整数1<r，s<N，使得N=r×s

寻求在传统计算机上运行的、复杂性为多项式时间内确定一个正整数N 的素因子问题，至今没有成功。Shor 算法问世以来，确定一个正整数N 的素因子问题得到解决，但算法的第2 步必须在量子计算机上运行，其余的1、3、4、5 步可以在传统计算机上运行。现在，我们将Shor 算法概述如下【27-29】：

步1 选择一个随机的正整数m，用复杂性为多项式时间的欧几里得算法计算m 和N 的最大公因子gcd（m，N）。如果gcd（m，N）≠1，则我们发现了N的一个非平常因子。算法结束。反之，如果gcd（m，N）=1，则处理转到步2；

步2 用量子计算机确定函数(www.xing528.com)

的未知周期P;

mp/2 + 1≠mod N，它能容易显示d是N的非平常因子，回答d，退出。

令r=mp/2 + 1，s=mp/2 - 1，则r 和s 是N的素因子。

Shor 算法的关键是量子部分（步2）。根据量子计算，量子傅立叶变换可求解函数的周期p。

2001 年，在IBM 的量子计算机ibmqx4 上，实现了Shor 算法，把整数15分解为3 和5，即15=3×5。