谷歌提出「超大数相乘」算法，量子版递归有望成真！
新智元原创
来源：QuantaMagazine
编辑：小芹、金磊
【新智元导读】前不久，史上最快的超大数相乘方法轰动业界。近日，借由这个思路，谷歌一名软件工程师提出了另一种优化方式，使得量子版“递归”算法或将成为可能！
上个月，两位研究人员发现的史上最快的超大数相乘方法，在业界掀起了不小的风波，有望破解存在了近半个世纪的数学难题。
而就在前几日，著名科普网站QuantaMagazine发表了一篇文章称，另一种新乘法运算方式为量子计算机打开了一扇新大门。
文章地址：
https://www.quantamagazine.org/a-new-approach-to-multiplication-opens-the-door-to-better-quantum-computers-20190424/
这篇论文作者是Google AI Quantum的软件工程师Craig Gidney，于4月15日将文章《渐近有效的量子Karatsuba乘法》发表于arXiv。
论文地址：
https://arxiv.org/pdf/1904.07356.pdf
论文作者
在他的新论文中，Gidney描述了一种实现Karatsuba乘法的量子方法，这种方法不会产生巨大的内存开销。他没有先生成中间值，再得到最终值，而是使用一种称为“尾调用优化”(tail call optimization)的方法来直接将输入变为输出。这使得算法可以避免创建量子计算机永远无法丢弃的中间信息。
Gidney希望他的方法能够使许多经典的递归算法适应量子计算机。目前，量子计算机还很初级，几乎不能进行个位数乘法。但起码有一个算法已经准备好了，只要它们的设计继续改进，它们将能够做更多的事情。
数学处处充满惊喜：大数乘法世纪难题或将破解，又有益于量子计算
先来思考一下这么一个问题：
我9岁的时候，我家有了一台新电脑。这台电脑在各方面都比我们的旧电脑好，除了一点：它不能运行我最喜欢的赛车游戏。我记得我当时就想，如果一台漂亮的新电脑不能运行我最喜欢的程序，那它还有什么意义呢?
同样的问题也适用于量子计算机。理论上，量子计算机可以做经典计算机所能做的所有事情。然而，在实践中，量子计算机的量子性质使它基本上不可能有效地运行一些最重要的经典算法。
而这又是什么原因呢？
我们知道，一台经典计算机能做加法，它就能做乘法，而后可以处理许许多多更加复杂的信息。而量子计算机却可能连非常基本的运算也难以做到，其间原因就是——无法做到“选择性遗忘”。
“选择性遗忘”就好比：一个2G的内存条实际上的容量或许只有1.95G。但对于量子计算机，它只能含泪说道：“臣妾做不到哇！”
而在Gidney的论文中所讨论的乘法算法利用了一项发现，这是数千年来乘法领域的首次进步。传统的小学乘法方法中，位数是n的两个数字相乘需要n²步。几千年来，数学家们一直认为没有更有效的方法了。
但是，正如我们最近在《极限速度！10 亿位超级大整数相乘仅需 30 秒，半个世纪的猜测终被证明》一文中所报道的，1960年，一位名叫阿纳托利·卡拉苏巴(Anatoly Karatsuba)的数学家发现了一种更快乘法方法。
他的方法是把长数字分成较短的数。例如，假如要将两个8位的数字相乘，首先要将每个8位数字拆分为两个4位的数，然后将每个4位数拆分为两个两位数。然后对所有两位数进行计算，最后将结果重组，就是最终的乘积。对于涉及大数的乘法， Karatsuba的方法比小学法的步骤要少得多。
如何快速地将两个大数相乘(Lucy Reading-Ikkanda/Quanta Magazine)
数千年来，将两个n位的数字相乘，需要n²个步骤。1960年，俄罗斯数学家Anatoly Karatsuba提出了一种更好的方法。
比如，在25×63这个算式中，使用小学乘法方法需要4个单位数乘法步骤，并将4步所得的积相加，才能得到最后的结果。
同样的算式使用Karatsuba的方法，只需要做3次乘法，以及少量的加法操作和移位操作。
随着数字位数的增加，Karatsuba方法可以重复使用，将大的数字分割成较小的数字，从而节省更多的单位数乘法操作。
类似“尾调用优化”，量子版“递归算法”或将实现！
经典计算机运行Karatsuba方法时，它会随着运行进行而删除信息。例如，在将两位数重组为四位数之后，它会忘记之前的两位数，只关心四位数本身。经典的Karatsuba方法就像登山者在上山的路上脱下装备一样——不需要一路携带所有东西时，你可以走得更快。
但量子计算机无法随时“脱下”信息。
量子计算机通过操纵量子比特系统来执行计算。“这些量子比特彼此交织或纠缠。这种纠缠使量子计算机拥有巨大的能量——量子计算机利用了所有量子比特之间存在的复杂关系，而不只是以单个比特存储信息。因此，对于某些特定的问题，量子计算机可以具有经典计算机指数级倍数的处理能力。
量子纠缠，看似荒谬的超距感应
但是使量子计算机强大的这种特性也使它们变得脆弱。因为量子比特纠缠在一起，你不可能在不影响其他量子比特的情况下改变其中的一些量子比特。这使得不可能像经典计算机那样有选择地删除信息。扔掉某些量子比特就像剪断蜘蛛网上的某几股线——即使只“咔嚓”一下也可能导致整个蛛网分崩离析。
保留信息的这种要求使得难以创建“递归”算法的量子版本，因为“递归”意味着它们会反馈给自身。递归算法在计算机科学中有很广泛的应用，但为了达到最佳效果，它们要求计算机在每一步都要丢弃信息。没有这种能力，计算很快就会变得不切实际。布里斯托尔大学(University of Bristol)量子信息科学家Ashley Montanaro说，“如果每次进行一项操作都会存储信息，那么空间的大小就会随着操作的数量而变化。”任何机器都会很快耗尽内存。
Gidney的工作在保持O(nlg3)门集程度(gate complexity)的同时，提高了量子计算机上从O1到O2的Karatsuba乘法的空间复杂度。他通过确保递归调用可以将其输出直接添加到输出寄存器的子部分来实现此目的。这避免了存储和不计算中间结果的需求。
他使用Q#的跟踪模拟器实现并测试了他的算法，并获得具体的计数。
针对各种输入尺寸的Karatsuba乘法和教科书乘法的Q＃implementation所使用的Toffoli gate和量子位数的双对数坐标图
值得注意的是，在作者的实现中，Karatsuba乘法比教科书乘法更高效的交叉点(约10000位)比现代RSA密钥的大小(2048到8192位)更大，这表明Shor算法在实践中应该更倾向于使用简单的乘法。
不过，这篇论文关注的是渐近参数，而不是试图优化常数因子。论文还忽略了一些重要的实际考虑，比如为了让量子比特相互作用而将量子比特相互routing的成本。
此外，作者分析的情况(两个量子整数的乘法)不同于Shor算法中的情况(一个量子整数与一个经典整数的受控模乘法)。因此，对于Karatsuba乘法在Shor算法中的实际应用，作者并没有得出任何结论。
他表示，这种类似于经典尾调用优化的优化应该适用于各种递归量子算法。但在Gidney发表这篇论文之前，还不清楚是否有可能对这类算法进行改造，让量子计算机也能运行。
Gidney希望他的新技术能让量子计算机实现这类算法，而到目前为止，这类算法在量子计算机中使用似乎是缓慢而复杂的。
参考链接：
https://www.quantamagazine.org/a-new-approach-to-multiplication-opens-the-door-to-better-quantum-computers-20190424/
https://arxiv.org/pdf/1904.07356.pdf