9、整数分解的量子算法：从Shor算法到变体探索

整数分解的量子算法：从Shor算法到变体探索

1. Shor整数分解算法

Shor算法是量子计算领域中用于整数分解的开创性算法，在密码学等领域具有重要意义。

1.1 概率与阶的计算

对于概率 $Prob(c; C_k \pmod{n})$，有如下公式：
[
Prob(c; C_k \pmod{n}) =
\left|
\frac{1}{q}
\sum_{a = 0}^{q - 1}
C_{a - C_k \pmod{n}}
\exp(2\pi iac/q)
\right|^2
=
\left|
\frac{1}{q}
\sum_{B = 0}^{\lfloor (q - k - 1)/r \rfloor}
\exp(2\pi i(Br + k)c/q)
\right|^2
=
\left|
\frac{1}{q}
\sum_{B = 0}^{\lfloor (q - k - 1)/r \rfloor}
\exp(2\pi i{rc}B/q)
\right|^2
]
其中 ${rc}$ 是 $rc \bmod n$。当 $-\frac{r}{2} \leq {rc} \leq \frac{r}{2}$ 时，意味着 $-\frac{r}{2} \leq rc - dq \leq \frac{r}{2}$（对于某个 $d$），此时有 $Prob(c; C_k \pmod{n}) > \frac{1}{3r^2}$，并且可以得到 $\left|\frac{c}{