Shor 算法与 QFT

分解因数 = 寻找周期

分解一个大数——比如把 15 拆成 3 x 5——感觉像是一个搜索问题，而对于巨大的数，普通计算机做起来极其缓慢，于是我们把密码学建立在它的困难之上。Shor 的关键洞见是：你根本不必去搜索。分解因数可以被重新表述为另一个问题：寻找一个重复序列的*周期*。而寻找周期，恰恰是量子计算机能做得很好的那类有结构的任务。

这里是连接的桥梁。挑一个你想分解的数，叫它 N，再挑一个更小的数 a。现在看看 a^1, a^2, a^3, ... 这些数除以 N 之后所得余数构成的序列。这个序列最终总会重复，一个循环的长度就叫作周期 r。数论里一个了不起的事实是：一旦你知道了 r，再做一点普通的算术，就能把它变成 N 的因数。于是整个困难问题就收缩成一个问题：周期 r 是多少？

a^1 a^2 a^3 a^4 a^5 a^6 a^7 a^8 ...
 mod N: 7   4   13  1   7   4   13  1  ...
        \___________/\___________/
            period r = 4 (it repeats)

当 a=7、N=15 时，余数以周期 r=4 循环。知道 r 就是通往因数的入口——量子部分存在的唯一目的，就是快速找到 r。

量子傅里叶变换

怎么找出一个周期呢？想想音乐 App 是怎么识别一个音的音高的：它拿到一段抖动的信号，然后问*它由哪些频率组成*。一个重复的模式会在它对应的频率处呈现为一根尖锐的峰。量子傅里叶变换（QFT）做的是同一件事，只不过作用在一组量子比特寄存器的状态上：它把『每 r 步重复一次』转换成一个状态，对它测量时很可能落在与该周期相关的数值上。

它之所以强大，靠的是干涉，而不是并行猜测。这些量子比特被制备在一个叠加态里，悄悄地把这个周期性模式同时编码在许多数值上。随后 QFT 让错误的答案彼此抵消、让正确的答案彼此增强——就像池塘里的涟漪相遇，多数波峰被抹平，少数几个叠加得更高。只有在这番精心的相消之后，你才去测量。

      ___              ___
|0>--|   |--[ QFT ]--|   |==> measure
|0>--| U |          |   |==> measure
|0>--| a |          |QFT|==> measure
|0>--|___|--........-|___|==> (read out a value
                            related to the period r)

概念示意图：一个寄存器先经过 a 的幂次步骤（U_a 方框）的驱动，然后 QFT 把那个周期性结构聚焦起来，使一次测量能透露关于 r 的信息。这并非逐个门级别的真实细节。

把它们拼到一起

挑选 N（要分解的数）和一个比 N 小的随机数 a。先做一次快速的经典检查；有时你会走运，根本不用任何量子计算就找到一个因数。
在量子计算机上构建一个叠加态，并施加模幂运算这一步，使寄存器编码出 a 的各次幂对 N 取模后那个重复的余数模式。
施加 QFT，让干涉把振幅集中到与周期 r 相关的那些结果上。
测量一次。你得到一个单一的数值；经典的后处理（一步连分数计算）把它变成周期 r 的一个候选值。
用 r 做普通的算术，算出 N 的因数。如果这一次尝试失败了——这有时会发生——就换一个新的 a 再来一遍。试几次几乎总能成功。

留意这个节奏：经典的准备、一个专注的量子子任务、经典的收尾，再加上一个重试循环。量子那一步是唯一没有任何经典方法能高效完成的部分，而它之所以奏效，是因为周期是*QFT 能加以利用的结构*——并不是因为机器把每一种可能性都暴力试了一遍。

为什么 RSA 处于危险之中

RSA 以及相关的公钥系统建立在一个赌注上：分解一个大数（或者椭圆曲线密码学背后那个密切相关的问题）实在太慢，没有人能在一辈子之内做到。最好的经典分解方法所需的时间，几乎是随数的大小呈指数增长的，这正是为什么今天人们认为足够长的密钥是安全的。

Shor 打破了这个赌注。对于这个有结构的问题，它把近乎指数的经典开销变成只随数的大小多项式增长的开销——这是专门针对分解因数的一种货真价实的指数级加速。一台运行 Shor 的大型、可靠的量子计算机，原则上可以从公钥反推出私钥，这就是人们说它『攻破 RSA』的原因。应对之策是后量子密码学：建立在某些数学难题（比如某些格问题）之上的新型经典算法，而 Shor 的寻周期诀窍*破解不了*这些难题。

前提条件：你需要一台大型的容错机器

以上这些都是理论。现实中的实际情况则要让人清醒得多。今天的机器仍处在 NISQ 时代——充满噪声、只有不多的量子比特、相干时间也很短——它们犯的错误太多了，根本无法在一个具有密码学意义的数上运行 Shor。一台真实量子计算机老老实实运行 Shor 所分解过的最大的数，都小得可怜，远远谈不上接近一个真正的 RSA 密钥。

挡路的不是聪明才智，而是可靠性。在一个 2048 位的密钥上运行 Shor，需要数以百万计、行为规规矩矩的物理量子比特，因为你必须把脆弱的物理量子比特裹进纠错之中，才能造出区区几个稳定的逻辑量子比特。像表面码这样的方案，只有当物理错误率降到大约 1% 以下时才能达到容错，而那时每一个逻辑量子比特又要耗费上千个物理量子比特。我们还远没到那一步——攻破 RSA 的时间估计要落在几年到几十年之后。