量子计算机编程：从入门到实践

197

第 12章

舒尔分解算法

如果你在阅读本书之前听说过量子计算的一个应用，那么这个应用很有可能就是舒尔分解

算法。

1994

年，彼得

•

舒尔（

Peter Shor

）发现，一台足够强大的量子计算机能够比任何传统计算

机都更快地找到一个数的质因数。在那之前，人们一直认为量子计算主要在学术上有用，

却不够实用。在本章中，我们将亲自体验舒尔分解算法的一个具体的

QPU

实现。

快速分解大数的能力不仅仅能满足人们在数学上的好奇心，还可以帮助破解

Rivest-Shamir-

Adleman

（

RSA

）公钥密码体系。无论何时启动

ssh

会话，你都要用到

RSA

。像

RSA

这样

的公钥密码体系的工作流程是这样的：任何人都可以使用一个免费的公钥来

加密

信息，但

是一旦加密之后，这些信息只能使用私人持有的密钥

解密

。人们通常把公钥密码体系比作

邮箱的电子版本。想象一下，任何人都可以将信通过一条缝投入一个锁着的邮箱（但不能

找回），但只有主人有邮箱钥匙。实践证明，作为公钥密码体系的一部分，寻找大数

N

的

质因数的任务效果很好。保证某人只能使用公钥加密而不能解密信息的前提是，找到

N

的

质因数是一项在计算上不可行的任务。

对

RSA

的完整解释超出了本书的范围，但关键点在于，如果舒尔分解算法提供了一种找

到大数

N

的质因数的方法，那么它将动摇现代互联网的根基。

除了对密码学的意义，理解舒尔分解算法还有其他重要的意义：它是解决所谓的

隐含子群

问题

（

hidden subgroup problem

）的算法中最著名的例子。在这类问题中，我们要确定给定

周期函数的周期性，这可能非常复杂。离散数学中的许多问题属于隐含子群问题 ...