肖尔算法（Shor's algorithm）

假设你想把一个大数还原成相乘得到它的那两个质数。对于一个几百位的数字，我们已知最好的经典方法所花的时间会超过宇宙的年龄，而 RSA 加密的全部安全性正是建立在这一难度之上。肖尔算法是一套量子「配方」，能把这件事做得快得多。它的高明之处在于不去正面强攻因数分解，而是把问题换成另一个：挑一个数，让它对你想分解的那个数取模、不断升到更高的幂，这个序列最终会以某个周期重复出现。只要你能找到这个周期，再做一点普通的算术，就能把因数交到你手上。

找出这个周期，正是量子部分大显身手的地方。算法会准备一个寄存器，让它同时容纳许多输入，再施加量子傅里叶变换（QFT）——它的构造使得错误答案的振幅相互抵消，而揭示周期的那些振幅彼此增强。当你测量时，极有可能读出一个指向周期的数值。这并不是说机器「把每个幂都试一遍、并行地全部检查」——若真如此，测量后什么有用的东西都留不下来。加速的来源，是把干涉安排得让问题的周期结构变得「响亮」，而其他一切都安静下去。对于这个特定、高度结构化的任务，这相对于我们目前已知的每一种经典方法，都带来了指数级的优势。