20 行 Python 代码说清量子霸权！( 五 )_作者|马超虽然这次谷歌的论文中声称他

量子霸权的由来

由于量子计算的性质十分复杂，需要非常高超的数学知识才难设计量子算法，而且应用的领域不广，所以在很长一段时间里人们还没有太重视量子计算机的发展，直到用于因式分解的量子算法shor横空出世，说起来其基本并不复杂，具体如下：

步骤1.随机取正整数a ， aN ，且与N互质。一般由辗转相关法可得

步骤2.定义函数，求函数f(x)的周期r如果r为奇数则重取a ，再求r ，直到r为偶数为止。

步骤3.由和可用的辗转相除法求与N的最大公约数n1 ， n1即为N的一个因子。至此N的因式分解即完成。

这个算法的精髓就是步骤2 ，它将因式分解问题转化为了求周期r的问题，而求周期的小能手傅里叶变换恰是量子计算的擅长所在。我们知道傅里叶变换是将函数由时域映射到频率域的过程，而频率就是周期的倒数，所以周期问题可以以用傅里叶变换求解，而傅里叶变换的算子与量子比特契合度较高，是量子计算的拿手好戏。所以所谓量子霸权的逻辑是SHOR算法能够攻破rsa算法，而rsa算法又是整个信息安全的基石，所以掌握了量子计算机就等于破解了整个信息安全身份认证体系，从而实现霸权。可以说如果没有SHOR算法的提出，那么也就没有量子霸权的概念了。