谷歌提出“超大数相乘”算法，量子版递归有望成真！( 四 )_图1

“选择性遗忘”就好比：一个2G的内存条实际上的容量或许只有1.95G。但对于量子计算机，它只能含泪说道：“臣妾做不到哇！”

而在Gidney的论文中所讨论的乘法算法利用了一项发现，这是数千年来乘法领域的首次进步。传统的小学乘法方法中，位数是n的两个数字相乘需要n2步。几千年来，数学家们一直认为没有更有效的方法了。

但是，正如我们最近在《极限速度！10 亿位超级大整数相乘仅需 30 秒，半个世纪的猜测终被证明》一文中所报道的，1960年，一位名叫阿纳托利·卡拉苏巴(Anatoly Karatsuba)的数学家发现了一种更快乘法方法。

他的方法是把长数字分成较短的数。例如，假如要将两个8位的数字相乘，首先要将每个8位数字拆分为两个4位的数，然后将每个4位数拆分为两个两位数。然后对所有两位数进行计算，最后将结果重组，就是最终的乘积。对于涉及大数的乘法， Karatsuba的方法比小学法的步骤要少得多。

谷歌提出“超大数相乘”算法，量子版递归有望成真！( 四 )