量子计算机不是万能加速器。它的优势来自于特定量子算法与特定问题结构的深度匹配。理解哪些算法有量子优势、优势有多大，是判断量子计算实际价值的关键。
## Shor 算法：RSA 的终结者
1994 年，Peter Shor 提出了整数分解的量子算法。整数分解（将大整数 N 分解为质因子）是 RSA 加密的数学基础。经典计算机分解 N 的最优算法（数域筛法）需要亚指数时间——足够大的 N 让其无法完成。Shor 算法在量子计算机上只需多项式时间，即 O((log N)³) 次量子门操作。
对于 2048 位 RSA 密钥，经典计算机需要超过宇宙年龄的时间；理想量子计算机（约 400 万物理比特）理论上可以在数小时内完成。这就是为什么全球密码学界都在紧锣密鼓地部署[后量子密码学（PQC）](https://sunqi.org/quantum-cryptography-zh/)标准。
Shor 算法的核心是量子傅里叶变换（QFT）和量子相位估计，这两个子程序也是其他许多量子算法的基础。参见 [arxiv: Shor 算法原始论文](https://arxiv.org/abs/quant-ph/9508027)。
## Grover 算法：无结构搜索的平方根加速
1996 年，Lov Grover 提出了无结构数据库搜索的量子算法。经典计算机在 N 个选项中搜索目标，平均需要 O(N) 次查询；Grover 算法只需 O(√N) 次，实现平方根级别的加速。
这听起来没有 Shor 那么戏剧化，但影响广泛：密码学中的暴力破解时间也因此被开方。一个 128 位对称密钥，面对量子计算机的 Grover 攻击，等效安全性降为 64 位——这也是为什么 AES-256 被认为是后量子时代的安全对称加密标准。
Grover 算法是量子搜索领域的最优算法（已被证明无法在无结构搜索上做到更好）。
## HHL 算法：线性方程组的量子加速
2009 年由 Harrow、Hassidim 和 Lloyd 提出的 HHL 算法，在特定条件下可以指数级加速求解线性方程组 Ax=b，理论复杂度从 O(N³) 降至 O(log N)。线性方程组是几乎所有工程和科学计算的核心。
然而，HHL 的指数加速附带严苛条件：矩阵 A 必须是稀疏且条件数良好的，输入数据必须以量子态形式给出（数据读取本身可能是瓶颈），输出也是量子态（难以完整读出）。因此，HHL 的实际加速效果在许多具体应用场景下是存疑的。
## 变分量子算法：NISQ 时代的务实选择
在等待完整量子纠错的过程中，研究者提出了一类适合当前嘈杂硬件的”变分量子算法”（Variational Quantum Algorithms，VQA）：
**VQE**（变分量子本征值求解）：用于量子化学和材料模拟。
**QAOA**（量子近似优化算法）：用于组合优化问题（最大割、旅行商问题等），提供近似解。
**量子机器学习算法**：量子神经网络、量子核方法等，适合特定数据结构的机器学习任务。
这些算法的量子优势尚未在实用规模上被证明，但它们是当前量子硬件能实际运行的最接近有用的算法。
## 量子算法优势地图
| 问题类型 | 经典复杂度 | 量子复杂度 | 加速类型 |
|——–|———|———|——-|
| 整数分解 | 亚指数 | 多项式 | 指数级 |
| 无结构搜索 | O(N) | O(√N) | 平方根 |
| 线性方程组 | O(N³) | O(log N) | 指数级（有条件） |
| 量子模拟 | 指数级 | 多项式 | 指数级 |
| 组合优化 | 指数级 | 近似/待定 | 尚未确定 |
更多内容参见[量子计算硬件](https://sunqi.org/quantum-computing-hardware-zh/)与[量子模拟应用](https://sunqi.org/quantum-simulation-zh/)。
—
