21、量子计算算法与应用：从整数分解到化学与蛋白质折叠

量子计算算法与应用：从整数分解到化学与蛋白质折叠

1. Shor算法与ProjectQ实现

1.1 Shor算法步骤

Shor算法是一种用于整数分解的量子算法，其步骤如下：
1. 若N为偶数，返回因子2。
2. 经典地判断是否存在p ≥ 1和q ≥ 2使得N = pq，若是则返回因子p（在经典计算机上可在多项式时间内完成）。
3. 选择一个随机数a，满足1 < a ≤ N – 1。使用欧几里得最大公约数算法，判断gcd (a, N) > 1是否成立。若是，则返回因子gcd(a,N)。
4. 使用量子电路寻找a模N的阶r。在量子计算机上，此步骤可在多项式时间内完成。
5. 若r为奇数，或者r为偶数但ar/2 = -1 (mod N)，则返回步骤(3)。否则，计算gcd(ar/2 - 1, N)和gcd(ar/2 + 1, N)。测试其中是否有N的非平凡因子，若是则返回该因子（在经典计算机上可在多项式时间内完成）。

1.2 受控乘法器Ua

受控乘法器Ua将 ∣x⟩ 映射为 ∣ ax (mod N)⟩，其中：
- a是用于ax (mod N)的经典互质数。
- x是量子寄存器。
- c是控制量子比特的寄存器，当c = 1时，Ua = ax (mod N)；否则为x。
- 控制器乘法器Ua由一系列双控模加法门实现：
- 若两个控制量子比特c1 = c2 = 1，输出为f(x) = ∣φ(a + b mod N)⟩，即在傅里叶空间中的a + b (mod N)。此门用于将互质数(a)和量子数(b)相加。
- 若任一控制量子比特(c1, c2)