量子算法（Grover, Shor）

💥 让经典密码学”颤抖”的两个算法

经典计算机在某些问题上很慢——不是因为计算机不够快，而是因为问题的本质决定了它需要指数级时间。

量子计算机在解决两类问题上展现了超越经典的能力：搜索（Grover） 和质因数分解（Shor）。

---

🔍 Grover 算法——搜索的”平方加速”

问题

在一个无序的电话本里找一个电话号码——经典计算机需要逐个查，平均查 N/2 次（O(N)）。

Grover 的加速

Grover 算法把搜索复杂度从 O(N) 降到 O(√N)。

100 万个条目：
经典：平均 500,000 次查询
Grover：约 1000 次查询

1 亿个条目：
经典：5000 万次
Grover：10,000 次

Grover 的思想：不是”一次查一个”，而是用量子叠加同时考虑所有条目，然后放大”正确”答案的概率幅，压缩错误答案的幅值。 重复 O(√N) 次后——测量得到正确结果的概率接近 100%。

对密码学的影响：

AES-128：经典破解 2¹²⁸ → Grover 2⁶⁴ → 仍不可行（2⁶⁴ 也是天文数字）
AES-256：经典破解 2²⁵⁶ → Grover 2¹²⁸ → 仍安全

对策：从 AES-128 升级到 AES-256

---

🧮 Shor 算法——RSA 的终结者

问题

RSA 加密的安全性基于”大整数分解很困难”：

给定 N = p × q（p 和 q 是大质数）
找出 p 和 q

经典计算机：最好的算法也需要亚指数时间
N 为 2048 位 → 需要 10¹² 年

Shor 的突破

Shor 算法可以在多项式时间内完成这个分解：

Shor 分解 N 的时间复杂度：O((log N)³)

N 为 2048 位 → 如果有足够多的 qubit → 几小时

这意味着什么？

当你用 HTTPS 访问网站时——你的浏览器用 RSA 加密了一个对称密钥发给服务器。
如果有人记录了今天的加密通信，未来量子计算机成熟了——Shor 算法可以解密过去的所有记录！

这就是"存下来以后破解"（Store Now, Decrypt Later）的威胁。

Shor 的高层思路

1. 把分解问题转化为"求函数周期"问题
2. 用量子傅里叶变换（QFT）高效求周期
3. 从周期反推出 p 和 q

关键：第 2 步在经典计算机上很慢，但在量子计算机上很快

💡 Shor 算法不破坏所有加密：对称加密（AES）和哈希函数（SHA）受影响小得多——只需加大密钥长度。真正被”终结”的是公钥加密——RSA 和 ECC。

---

📊 量子算法的实际现状

Shor 算法：
- 理论上：可以破解 2048 位 RSA
- 实际上：2024 年分解了 48 位的 RSA（离 2048 位还很远）
- 需要：约 2000 万个物理 qubit（当前最好 ~1000 个）

Grover 算法：
- 需要纠错后的逻辑 qubit——目前还没实现
- 平方加速挺好，但不够"颠覆性"

当前量子计算机（2026 年）：
- 处于 NISQ（含噪声中等规模量子）时代
- 数百到数千 qubit——但都有噪声
- 还没有实现"量子霸权"级别的实用算法

---

📝 小结

算法	问题	经典	量子	意义
Shor	分解大整数	指数级	O((log N)³)	破解 RSA/ECC——互联网安全的威胁
Grover	无序搜索	O(N)	O(√N)	减弱对称加密（AES 加长密钥即可）
当前状态	—	—	—	NISQ 时代——有量子但不够用

为什么先学这个？ 量子算法展示了量子计算”能做经典做不了的事”。但量子比特很容易出错——需要量子纠错。