22、量子计算算法与应用：从整数分解到分子基态计算

量子计算算法与应用：从整数分解到分子基态计算

1. Fourier采样与整数分解

1.1 Fourier采样原理

Fourier采样是一种数据处理过程，具有以下特性：
- 允许输入移位而不改变输出分布。
- 能形成周期性叠加，非零振幅是周期的倍数。

Fourier采样的输出是M/r的随机倍数。例如，当M = 100，r = 4时，输出是25的随机倍数。

1.2 结合欧几里得最大公约数求周期

多次运行Fourier采样会得到M/r的随机倍数，如50、75、25等。通过对这些随机输出应用欧几里得最大公约数（gcd），再用M除以gcd，就能得到周期r。例如，r = M/gcd(50, 75, …) = 100 / 25 = 4。

1.3 以N = 21为例进行整数分解

我们的任务依赖于两个高效操作：
- 模运算：a = b (mod N)，例如3 = 15 (mod 12)。
- 最大公约数gcd(a, b)，例如gcd(15, 21) = 3。

对于N = 21，需要求解方程x² ≡ 1 (mod 21)，即找到非平凡平方根x，满足：
- N能整除(x + 1)(x - 1)。
- N不能整除(x ± 1)。
- 最后通过gcd(N, x + 1)恢复质因数。

随机选取x = 2：
- 2⁰ ≡ 1 (mod 21)
- 2¹ ≡ 2 (mod 21)
- 2² ≡ 4 (mod 21)
- 2³ ≡ 8 (mod 21)
- 2⁴ ≡