05-Shor与Grover算法简介

Shor 与 Grover 算法简介

本节摘要:本节介绍两个最著名的量子算法:Shor 算法(1994)与Grover 算法(1996)。Shor 算法能在多项式时间内分解大数,直接威胁 RSA 密码;Grover 算法能在无序数据库搜索中获得平方加速。这两个算法展示了量子计算相对经典计算的根本优势,是"量子优势"的标志性示例。本节用直觉方式介绍它们的核心思想,不深入数学细节。

一、为什么量子算法重要?

量子计算的根本问题

量子计算自 1980s 提出后,面临一个根本问题:量子计算机能做什么经典计算机做不到的事?

如果量子计算机只是"另一种计算机",做同样的计算,那它没意义。量子优势(quantum advantage)是指量子计算机能在某问题上显著快于经典计算机。

Shor 与 Grover 算法是最早、最重要的两个展示量子优势的算法。

二、Shor 算法(1994)

任务:大数分解

问题:给定大整数 N(如 N = p × q,p、q 是大素数),找出 p 与 q。

这是大数分解问题。经典算法(如数域筛)需要的时间约为 exp(N^(1/3)),对大 N 是不可行的。这就是 RSA 密码的安全性基础。

Shor 的洞察

1994 年,彼得·绍尔(Peter Shor)发现:大数分解可以归约为"求周期"问题。

具体地,选一个随机数 a,研究函数 f(x) = a^x mod N。这个函数是周期的,周期 r 与 N 的因子有关。如果找到 r,就能用经典算法(最大公约数)找到因子。

量子加速:量子傅里叶变换

经典算法找周期 r 需要约 N 次操作(几乎线性)。但 Shor 用量子傅里叶变换(QFT)在量子计算机上找 r,只需约 (log N)² 次操作——指数加速!

QFT 利用量子叠加同时处理多个 x 值,量子干涉使正确的周期显现。

Shor 算法的影响

Shor 算法的影响巨大:

• 威胁 RSA 密码:RSA 基于大数分解的难度;量子计算机可以破解。
• 推动量子计算发展:Shor 算法使量子计算从理论兴趣变成实际重要性。
• 催生后量子密码学:为应对量子威胁,密码学界开始研究 PQC。

当前实验进展

实际运行 Shor 算法需要容错量子计算机,可能需要数百万物理量子比特。目前的量子计算机(几十到几百量子比特)只能分解很小的数(如 15 = 3×5,21 = 3×7)。

要破解 RSA-2048(当前标准),需要大规模容错量子计算机,可能还需 10-20 年或更久。

三、Grover 算法(1996)

任务:无序搜索

问题:给定一个无序数据库(有 N 项),找到一个特定项(满足某条件的项)。

经典算法:必须逐项检查,平均需要 N/2 次,最坏需要 N 次。

Grover 的加速

1996 年,洛夫·格罗弗(Lov Grover)发现:量子计算机可以用约 √N 次操作找到目标——平方加速!

Grover 算法的核心思想

Grover 算法的核心:振幅放大(amplitude amplification)。

1. 把所有项置于等量叠加(用 Hadamard 门)。
2. 应用"Grove 迭代"——一系列量子门,逐渐增大目标项的振幅,减小其他项的振幅。
3. 经过约 √N 次迭代后,目标项的振幅接近 1。
4. 测量:以高概率得到目标项。

加速的实际意义

Grover 算法的 √N 加速虽然"只是平方",但意义巨大:

• 对 N = 10⁶,经典需要 10⁶ 次,量子需要 10³ 次——千倍加速。
• 对 N = 10¹²,经典需要 10¹² 次,量子需要 10⁶ 次——百万倍加速。

平方加速不是指数加速,但对大规模问题仍然显著。

Grover 的应用

Grover 算法应用于:

• 数据库搜索:原始应用。
• 密码破解:对对称密钥(如 AES),Grover 算法把破解难度从 2^n 降为 2^(n/2)。这就是为什么后量子密码学建议用更长的密钥(如 AES-256 替代 AES-128)。
• 优化问题:Grover 思想可以加速某些优化任务。
• 量子机器学习:Grover 用于加速某些搜索任务。

四、量子算法的特征

Shor 与 Grover 的对比

量子加速的来源

量子加速来自几个量子特性:

1. 叠加:量子比特可以同时处于多个状态,允许并行处理。
2. 干涉:精心设计的算法使正确答案的振幅相长干涉,错误答案相消干涉。
3. 纠缠:多量子比特纠缠使某些任务(如 Shor)成为可能。

但要记住:叠加不等于直接并行计算。如果只是并行处理,测量只给一个结果,无法利用。量子算法的精妙在于设计干涉,使正确答案的概率最大化。

五、其他量子算法

除了 Shor 与 Grover,还有许多其他量子算法:

量子模拟

费曼最早(1982)提出:用量子计算机模拟量子系统,可能比经典模拟指数快。这是量子计算的最初动机。

应用:

• 化学:模拟分子结构与反应(如固氮酶、新型催化剂)。
• 材料科学:设计新材料(高温超导、新型电池)。
• 凝聚态物理:研究多体纠缠系统。

量子模拟可能是量子计算最早实用的领域之一。

HHL 算法(线性方程组)

HHL 算法(Harrow-Hassidim-Lloyd, 2009)能指数快地求解某些线性方程组。它应用于机器学习、优化等领域。但 HHL 有严格假设(稀疏矩阵、良好条件数等),实际应用受限。

量子机器学习

量子机器学习是热门领域:

• 量子支持向量机。
• 量子神经网络。
• 量子主成分分析。

但这些算法的实际优势仍在争论——某些"量子机器学习"算法的优势在经典算法改进后被消除。

VQE 与变分算法

变分量子本征求解器(VQE)等变分算法适合 NISQ 时代(下节)的量子计算机。它们用于量子化学、优化等任务,可能成为早期量子优势的来源。

六、量子优势的当代证据

"量子霸权"实验

2019 年,Google 团队(John Martinis 等)宣称"量子霸权"(quantum supremacy)——他们的 53 量子比特超导量子芯片(Sycamore)在 200 秒完成的任务,经典超级计算机需要约 1 万年。

虽然 IBM 对这一估计提出异议(他们认为经典可优化到几天),但这仍是量子优势的重要证据。

后续实验

2020 年,中国潘建伟团队用光子系统也展示了量子优势(玻色采样任务)。后续 Google、IBM、中国科大、初创公司等不断推进量子优势的边界。

当代争议

"量子优势"的宣称仍有争议:

• 经典算法不断改进,有时消除量子优势。
• "任务"是为量子计算机设计的,可能无实际用途。
• 实际有用量子优势(如 Shor)需要更大规模、容错的量子计算机。

但量子优势的物理可行性已被实验证实,只是实际应用还需时间。

本节要点回顾

1. 量子优势:量子计算机在某问题上显著快于经典计算机。
2. Shor 算法(1994):多项式时间内分解大数,指数加速,威胁 RSA。基于量子傅里叶变换找周期。
3. Grover 算法(1996):无序搜索 √N 次操作,平方加速。基于振幅放大。
4. Shor 加速 = 指数;Grover 加速 = 平方。
5. 加速来源:叠加 + 干涉 + 纠缠。
6. 叠加 ≠ 直接并行:量子算法的精妙在于设计干涉,使正确答案概率最大。
7. 其他算法:量子模拟(费曼最早动机)、HHL、量子机器学习、VQE。
8. 量子优势实验:Google Sycamore(2019)、中国科大(2020)等。
9. 当代争议:经典算法改进、任务实用性等。
10. Shor 破解 RSA 需要大规模容错量子计算机,可能还需 10-20 年。

下一节(本章与全书最后一节),我们讨论量子计算的现状与挑战——物理实现、NISQ 时代、退相干、纠错、可扩展性等。