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

Gidney的工作在保持O(nlg3)门集程度(gate complexity)的同时，提高了量子计算机上从O1到O2的Karatsuba乘法的空间复杂度。他通过确保递归调用可以将其输出直接添加到输出寄存器的子部分来实现此目的。这避免了存储和不计算中间结果的需求。

他使用Q#的跟踪模拟器实现并测试了他的算法，并获得具体的计数。

图7/8

针对各种输入尺寸的Karatsuba乘法和教科书乘法的Q＃implementation所使用的Toffoli gate和量子位数的双对数坐标图

值得注意的是，在作者的实现中，Karatsuba乘法比教科书乘法更高效的交叉点(约10000位)比现代RSA密钥的大小(2048到8192位)更大，这表明Shor算法在实践中应该更倾向于使用简单的乘法。

不过，这篇论文关注的是渐近参数，而不是试图优化常数因子。论文还忽略了一些重要的实际考虑，比如为了让量子比特相互作用而将量子比特相互routing的成本。

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