艰难的因式分解

肖尔算法（Shor's Algorithm）由美国数学家彼得·肖尔（Peter Shor）于1994年提出，它能够以多项式时间完成大数的质因数分解。这看起来似乎是一个简单的问题——毕竟我们在中学时就学过如何将一个数表示为质因数的乘积。按照同样的方法，我们可以将数字15分解为 $15 = 3 \times 5$，或将另一个数如1748分解为 $1748 = 2^2 \times 19^1 \times 23^1$。

然而，当面对更大的数字时，这个问题并不容易解决。事实上，目前我们最快速、最高效的经典质因数分解算法的时间复杂度是指数级的。具体来说，对于大于一“古戈尔”（$10^{100}$）的整数，目前已知最快的算法——通用数域筛法（General Number Field Sieve），其时间复杂度为

来分解一个整数 $N$。

正如彼得·肖尔在1994年所发现的，量子计算机可以更快地解决这一问题。实际上，肖尔算法相比其经典版本实现了指数级加速。它消除了指数项，整体渐近时间复杂度约为

或等价于 $O((\log N)^3)$，即关于输入位数 $n=\log N$ 的立方时间复杂度。

这一优势极为显著，因为一旦能够对包含数百位的大数进行多项式时间内的因数分解，便足以破解当前广泛使用的加密算法，例如RSA算法。这些算法的安全性依赖于这样一个假设：对大整数进行质因数分解对计算机而言是一项极其困难的任务。因此，我们可以利用这一特性构建公钥-私钥加密体系，保障互联网通信的安全。

然而，尽管目前我们的#key#量子体积：衡量现有硬件可成功实现的最大方形量子电路规模的指标#key#尚未达到数千个量子比特，不足以实际破解加密标准，但肖尔算法仍不可忽视。

因此，接下来我们将逐步建立理解肖尔算法所需的初步概念。在下一课中，我们将从傅里叶变换的量子版本开始学习。