简介?

算法实现?

简介?

秀尔算法（Shor's Algorithm），以数学家彼得·秀尔命名，是一个在1994年发现的，针对整数分解这题目的的量子算法 (在量子计算机上面运作的算法 )。比较不正式的说，它解决题目如下：给定一个整数N，找出他的质因子。

在一个量子计算机上面，要分解整数N, 秀尔算法的运作需要多项式时间 (时间是log N的某个多项式这么长,log N在这里的意义是输入的档案长度)。 更精确的说，这个算法花费O((log N))的时间，展示出质因子分解问题可以使用量子计算机以多项式时间解出，因此在复杂度类 BQP里面。这比起传统已知最快的因子分解算法, 普通数域筛选法, 其花费次指数时间 -- 大约O(e (log log N))，还要快了一个指数的差异。

秀尔算法非常重要，因为它代表使用量子计算机的话，我们可以用来破解已被广泛使用的公开密钥加密方法，也就是RSA加密算法。RSA算法的基础在于假设了我们不能很有效率的分解一个已知的整数。就目前所知，这假设对传统的(也就是非量子)电脑为真；没有已知传统的算法可以在多项式时间内解决这个问题。然而，秀尔算法展示了因子分解这问题在量子计算机上可以很有效率的解决，所以一个足够大的量子计算机可以破解RSA。这对于鼓吹我们去建立量子计算机和去研究新的量子计算机算法，是一个非常大的动力。

在2001年，IBM的一个小组展示了秀尔算法的实做, 使用NMR实做的量子计算机，以及7个量子位元，将15分解成3 × 5。 然而，对IBM的实验的是否是量子计算的真实展示，则有一些疑虑出现，因为没有缠结现象被发现。 在IBM的实做之后，有其他的团队以光学量子位元实做秀尔算法，并强调其缠结现象可被观察到。

算法实现?

我们要试着解决的问题是：给定一个合成数 N,找到整数p在1和N之间且不包含1和N, 并且 N整除于p。

秀尔算法包含两个部份：

1.一个以传统的电脑运作的简化算法，将因子分解简化成搜寻目的问题。2.一个量子算法，解决搜寻目的问题。

传统部份：

1.选择任意数字a < N

2.计算gcd(a, N)。这里可以使用辗转相除法来计算。

3.若 gcd(a, N) ≠ 1，则我们有了一个N非显然的因子，因此这部份结束了。

4.否则，利用下面的周期寻找副函式(Period-finding subroutine，下面会列出)来找出下面这个函数的周期r: ?f(x) = a^x mod N。换句话说，找出a在里面的目 r，或者最小的正整数r令 f(x + r) = f(x)。

5.若r是奇数，回到第一步。

6.若a^(r/2) ≡-1 (mod N), 回到第一步。

7. gcd(a^(r/2)? ± 1, N) 是N非平凡的一个因子。分解完成。

量子部份：周期寻找副函式(Period-finding subroutine)

这个算法使用的量子线路是为了在给定一个固定常数 N 以及一个任意常数 a之下，找出f(x) = a^x mod N所设定的。给定N, 找出Q = 2^q且合乎N^2≤Q≤2N^2??(这同时表示Q / r > N)。输入和输出量子位元暂存器需要储存从0到Q-1所有值的叠加态，因此分别需要q个量子位元。这里使用看起来比所需的数量还要更多一倍的量子位元，保证了即使周期r的大小逼近N/2，也至少有N个不同的x会产生相同的 f(x)。

算法如下：

1.将暂存器初始化成

?

x从0到Q - 1。所以这一个初始态是Q 个状态的叠加。

2.建立量子函式版本的f(x) ，并且应用于上面的叠加态, 得到

?

这里仍旧是Q个状态的叠加。

3. 对输入暂存器进行 量子傅立叶转换。这个转换（操作于二的幂次即Q = 2^q个叠加态上面）使用一个Qth 单位根 例如 ω = e^(2pi*i/Q)将任意给定态|x>的振幅平均分布在所有Q个态|y>上。另一个方法是对于每个不同的|x>：

?

由此得到最终状态：

?

这是一个远多过Q个状态的叠加态，但是远低过Q^2个。虽然在和中有Q^2项，但只要x0 和 x的值相同，态|y>f(x0)就可被提出来。令

ω = e^(2pi*i/Q)? 为 Qth 的一个单位根，

r 为 f 的周期，

x0为一个产生相同 f(x) 的 x 的集里面的最小元素（我们已经有x0 < r），以及

b在0到[(Q-x0-1)/r]之间使得x0 + rb < Q。

那么ω^ry则是复平面的一个单位向量（ω是一个单位根，r 和 y 是整数），而?Q^(-1)|y>|f(x0)>在最终状态下的系数则为?

?

这一求和的每一项代表一个获得相同结果的不同路径，而量子干涉发生。在单位向量ω^ryb几乎与复平面指向同一方向（要求ω^ry指向正实数轴）时，干涉将是相长的。

4.进行测量。我们由输入寄存器取得结果 y，由输出寄存器取得f(x0)。而既然f 是周期，对某对y和 f(x0)进行测量的概率则由

?

给出。分析显示这个概率越高，单位向量ω^ry就越接近正实数轴，或者yr/Q就越接近一个整数。除非r是2的乘方，否则它不会是Q的因子。

5.对y/Q进行连分数展开来计算其近似值，并生成满足下列两个条件的c/r′：

A: r′<N

B: |y/Q - c/r′| < 1/2Q

借着满足这一些条件，r′ 有很高的机率会是我们要找的周期r 。

6. 检查f(x) = f(x + r′) ，由此可得

?

?

如果成功了，我们就完成了。

7.否则，以接近y左右的数值作为r的候选，或者说多取几个r′. 如果任何候选成功了，我们就完成了。

8.否则，回到第一步骤(也就是全部重新作一次)。?