“九章”问世：量子计算机究竟有多快（四）

量子算法背后的理论

　　快速量子算法背后有几个重要理论。在运用相关理论时，我们具体要做的就是设计算法使得那些产生错误结果的计算路径相消干涉，用以降低得到错误答案的概率。让那些产生正确结果的计算路径相长干涉，这样就能极大地增大获得正确答案的概率。这也是导致设计一个量子算法很困难的原因。如此一来就很有必要介绍一下因数分解算法，其实我们要做的就是进行模运算。

　　一个数除以M得到的余数就是模运算的结果， 比如13加9除以17的余数是5，而5乘7除以17的余数是1，我们将在因数分解算法中用到它。现在来讲下所有快速分解算法背后的思路， 比如我前面讲过的数域筛法，它是经典算法。还比如量子分解算法，要分解一个大数N，需要找到两个数a和b， 它们满足a的平方等于b的平方除以N的余数，但是a不等于正负b除以N的余数，然后你可以得到这个方程，a的平方减b的平方等于a+b乘以a减b ，它又等于N的整数倍，因为a的平方减去b的平方除以N的余数为0。

　　现在我们还剩两项，其中一项给出一个因数，另一项给出另一个因数。现在我们来分解下33，令a等于13，b等于2，而169除以33的余数是4，所以2的平方等于13的平方除以33的余数，然后用13的平方减去2的平方的结果除以33，其余数为0。15除以3的余数是0，所以15就给出因数3， 11给出因数11。所以最终得到33=11×3。这是欧几里得两千年前发明的算法， 可以用来计算因数分解问题。

　　下面用量子分解算法来对大数N进行分解，首先要找到一个序列的周期，一个序列的周期就是经过多久它会重复，即经过多久再次出现。获得这个数后，就知道了周期r，而x的r次方除以N的余数就等于1，如果我们幸运的话，r刚好是偶数，然后计算这个公式就能得到因数。

　　我们现在通过取最大公约数得到两个因子， 最后就可以给出一些不错的结果， 至少对于随机选择的x中的一半是如此。我们再举一个分解33的例子，取x等于5，然后得到序列：1，5， 5的平方25，5的立方为26，5的四次方为31 （结果为除以33的余数），5的10次方除以33的余数是1，因此5的5次方除以33的余数是23，然后把33分解成（23+1）×（23-1），就等于24×22，最后24就给出一个因数3，22给出一个因数11，这样我们就分解了33，33=3×11。

　　因此我们需要找到x的次方除以N的余数的周期， 方法就是利用傅里叶变换，这样可以很容易找到周期性。在找x的次方除以N的余数的周期时会遇到问题，问题就是这些序列可能会有指数级长的周期，解决办法就是利用量子计算机的指数级增大的态空间，去指数级加速傅里叶变换。正如经典算法中用FFT（快速傅里叶变换）来计算傅里叶变换，我们可以改造成量子傅里叶变换。

　　那么因数分解算法呢？首先我们需要将第一个量子寄存器置为叠加态， 然后随机选择x。如果i在第一个寄存器中， 就在第二个寄存器中计算x的i次幂除以N的余数， 这儿还是经典计算机的计算。这里就可以使用经典方法来进行计算，再对第一个寄存器进行量子傅里叶变换，接着测量第一个寄存器，由此就得到了量子计算机的输出结果。然后在经典计算机上进行数据处理后，就可以得到因数。

　　在分解算法中有一些很重要的地方， 比如在第二步中，用了第二个寄存器进行计算， 但是之后就再也不用它了，为什么不把这一步去掉呢？ 这样不行，因为你去掉了这一步，就会去掉算法里面的干涉，最后就不会得到正确的答案了，这是因为量子力学定律。如果一个量子系统作用到另一个量子系统， 那么第二个量子系统也会反作用于第一个系统。

　　这个算法能成功的原因在于：当你进行完傅里叶变换后， 就在第一个寄存器中获得了干涉，如果第一个寄存器的值跟周期相近，那么所有的系数相加后得到相长干涉，而如果这个值不是周期，那么所有系数相加后就得到相消干涉，因此你最终得到的结果是接近周期的。

　　量子计算未来或许能够在很多具有实用价值的领域发挥巨大作用。领导团队开发“九章”的中国量子领域著名专家潘建伟曾在采访中说：“量子计算机在原理上具有超快的并行计算能力，可望通过特定算法在密码破译、大数据优化、天气预报、材料设计、药物分析等领域，提供比传统计算机更强的算力支持。” 奥地利科学院院长、沃尔夫奖得主、美国科学院院士Anton Zeilinger则认为，“我预测很有可能有朝一日量子计算机会被广泛使用。甚至每个人都可以使用。”

　　量子计算将给人类社会的发展带来什么样的变化，我们拭目以待。