Shor算法实现因子分解

Shor算法简介

Shor算法在量子计算机上分解整数N的时间复杂度为 \(logN\),几乎是对已知最有效的经典因数分解算法的 \(e\) 指数加速,这种加速有可能在量子计算机上中断如RSA的现代加密机制。

Shor算法基本思路

Shor算法要解决的主要问题是:给定一个整数N,找出它的质因数。即对一个给定的较大数 \(N\) 在多项式时间内确定两个素因子 \(p_1\)\(p_2\) 满足 \(p_1\cdot p_2=N\)。 在介绍shor算法步骤之前,先介绍一些数论知识。

因子分解涉及到数论里的一些知识,可以将因子分解问题归结为下列函数:

\[f(x) = a^x\mathrm{mod} N\]

对于 \(a\)\(a\)\(N\) 互质,否则通过调用 \(gcd (a,N)\) 就可以马上得到一个因子)的周期查找。 由于函数 \(f(x)\) 的周期 \(r\) 满足 \(f(x) = (x+r)\)。在这种情形下,就可得 \(a^x = a^{x+r}\mathrm{mod} N\forall x\)。 因此, \(a^r = 1+qN​\) 对于一些整数 \(q\)\(a^r-1 = (a^{r/2}-1)(a^{r/2}+1) = qN​\)。 这也表明对于 \(N​\) 使用 \(gcd​\) 就可以找到其因子。

因此,Shor算法的核心在于,将大数分解的问题转化为找周期的问题(如下数论知识所示)。我们可以通过构造一个酉矩阵 \(U_{x,N} \left| {j} \right\rangle \left| {k} \right\rangle -> \left| {j} \right\rangle \left| {x^jk \mathrm{mod} N} \right\rangle\), 最终的结果满足 \({x^r} = 1\left( {\bmod N} \right)\)

下面以 \(N = 15\) 为例,介绍shor算法在因子分解的步骤:

  1. 选择一个任意的数字,比如 \(a = 2\) (<15)
  2. \(gcd⁡ (a,N) = gcd (2,15) = 1\)
  3. 找函数 \(f(x) = {a^x}\bmod N\) 的周期,使得 \(f(x + r) = f\left( x \right)\)
  4. 通过量子电路图运算得到 \(r = 4\)
  5. \(gcd ({a^{\frac{r}{2}}} + 1,N) = gcd (5,15) = 5\)
  6. \(gcd ({a^{\frac{r}{2}}} - 1,N) = gcd (3,15) = 5\)
  7. \(N = 15\) 分解得到的质数结果为 3 和 5,分解完成。

Shor算法的量子电路如下图所示:

../images/shor.png