Shor 的算法 一个重要的环节就是找到某种函数形式的周期性与需要因子分解的数之间所存在的联系

量子计算机是如何对数字进行因子分解的？

飞猪 星期四, 04/19/2012 - 10:21 发布

译者前言： 关于量子计算机中的Shor算法在之前的量子信息相关新闻翻译中已经多次提到了。这里我发现了一篇关于Shor算法的浅显的小文，作者用一个很简单的例子--对15的因子分解--来描述Shor算法的核心思想，读者们可以在此基础上自己做进一步的尝试。有时间的时候，我将更加详细的介绍相关的数学细节。
[原始出处]
如今，新一代科学家们探索出的器件的细节特征将作为量子计算机的先驱而在历史上留下印记。
Shor 的算法首次被应用于量子计算机是一件很特别的事因为它可以用超级快的速度对数字进行因子分解。 这项工作背后的团队用它来对数字“15”进行因子分解。虽然这只是一个很小的数字，但重要性在于它证明了算法的可行性。功能更强大的量子计算机终将出现，那更多的只是工程技术上的难题。 在物理本质上， 利用shor算法来实现量子计算中的快速因子分解是可行的。
那么，什么是 Shor 算法呢？
Shor 利用数论提供了寻找质因子的快捷方式。 其中，一个重要的环节就是找到某种函数形式的周期性与需要因子分解的数之间所存在的联系。定义这样一个函数的周期性并不那么直接。下面我们通过一个简单的例子来加以说明：找到和数字15相关的周期。
首先， 找到一个没有别的质因子的数，也就是质数（数字1除外），这个数需要和15有一些共同点，比方说 11。
然后， 11/15=0+余数11， 余数的平方得到 121。 121/15=8+余数1。  11的立方得到1331。1331/15=88+余数11。
如果我们继续这种操作，通过提高11的幂次并除以15，我们将发现一个关于余数的有趣现象： 它总是11或者1。 因此，我们找到了一个和11相关的函数，当它除以15时，周期是2。
但是这对求解15的因子分解来说有什么用呢？让我们先计算11的周期幂次，也就是11^2=121。 对121开方，我们得到11。 11加减1我们得到一对数10和12. 然后找出10或12与15的最大公约数，分别是5和3，这正是15的分解因子。
当然，用这种方法来处理这么简单的问题简直是杀鸡用牛刀。但是，当我们面对的是一个特别大的数的时候，这样的做法就远比猜测更为有效了。对于 RSA 加密算法中使用的巨大数字来说，要解出这样的问题，即使是很快的传统的计算机也将要花费相当长的时间，而对量子计算机来说，这只不过是小菜一碟。
参考文献：Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, arxiv:quant-ph/9508027v2