实际上，许多为经典计算机设计的程序无法在量子计算机上运行，因为它们无法选择性地忘记信息。 新的乘法算法显示了如何解决此问题。
经典位是黑白的，量子位更复杂我9岁那年，父母买了一台新电脑。 在几乎所有方面，他都比旧赛车更好，唯一的例外是：我最喜欢的比赛并不是从此开始的。 我记得我的想法-如果我没有启动我喜欢的程序，为什么我需要一台新计算机？
量子计算机也有同样的问题。 从理论上讲，它们具备经典产品所能提供的一切。 实际上，它们的量子性质使得几乎不可能运行某些最重要的经典算法。
这就是为什么4月15日出版的
作品包含好消息的原因。 加利福尼亚州圣塔芭芭拉市Google AI Quantum的计算机科学家
Craig Gidney描述了经典算法的量子版本，该算法可快速将非常大的数字相乘。 在经典计算机上，该算法已经运行了一段时间。 但是在吉德尼（Gidney）开展工作之前，尚不清楚是否有可能将其应用于量子机器。
更重要的是，乘法算法属于普遍存在的计算机科学算法的类别。 吉德尼（Gidney）相信，他的新技术将使量子计算机能够实现这些算法的整个类别，到目前为止，这些算法都被认为太麻烦了，无法在量子计算机中使用。
这种乘法算法利用了发现的优势，这是几千年来乘法的第一个突破。 传统的学校乘法方法需要n
2个步骤，其中n是相乘数字中的字符数。 几千年来，数学家认为没有更有效的方法。
但是，正如我们最近在1960年发表的“
数学家发现乘数的理想方法 ”一文中阐明的那样，苏联数学家阿纳托利•唐津巴（Anatoly Karatsuba）发现了一种更快的方法。 他的方法是将长整数分成短整数。 例如，要将两个八位数字相乘，必须先将它们分解为两个四位数字，然后再将它们分解为两个两位数。 然后，您需要用两位数执行几个运算，并恢复最终乘法的结果。 要乘以非常大的数字，唐津法要比学校法少得多的步骤。
当经典计算机运行Karatsuba算法时，它将在此过程中删除信息。 例如，将两位数字恢复为四位数字，他会忘记两位数字。 现在，他只对四位数的数字感兴趣。 该算法的经典版本类似于登山者在攀登时将其设备扔掉-如果他不随身携带所有垃圾，他可以更快地移动。
但是量子计算机不能丢弃信息。
量子计算机通过对量子位或“量子位”的操作来执行计算。 它们相互缠绕或混淆。 这种混乱为量子计算机提供了巨大的机会-量子计算机不是将信息存储在单独的位中，而是使用所有量子位的复杂相互作用。 结果，对于某些任务，与经典计算机相比，量子计算机能够展现出指数级的计算能力。
但是，使量子计算机如此强大的相同属性也使它们易碎。 由于量子位是纠缠的，因此在不影响其他所有人的情况下更改某些位是不可能的。 这使得不可能有选择地删除经典计算机可用的信息。 敲回量子比特就像切割网的一部分一样-即使单次切割也可以破坏整个网。
保留信息的这种要求使递归算法的量子版本的创建变得复杂-即转向他们自己。 在计算机科学中，递归算法的使用非常广泛，但是，为了以最佳方式工作，它们需要计算机在每一步都丢弃信息。 没有这个，计算将很快变得不切实际。 布里斯托大学的量子信息专家
阿什利·蒙塔纳罗说：“如果每次执行操作时都保存信息，则其占用的空间将随着操作次数的增加而增加。” 任何实用的计算机都将很快耗尽内存。
Gidney在一项新工作中描述了一种实现Karatsuba乘法的量子方法，该方法不需要大量的内存消耗。 它没有使用中间值来获得最终结果，而是使用“
尾部递归优化 ”方法将输入直接转换为输出。 这允许算法避免创建量子计算机无法丢弃的中间信息。 克里顿大学的量子信息专家
托马斯·沃恩说：“他摆脱了额外的量子位的问题，却又不产生额外的量子位。”
吉德尼（Gidney）相信他的方法将适用于量子计算机的许多经典递归算法。 到目前为止，量子计算机还处于起步阶段，以至于它们几乎无法应付一位数的乘法。 但是，算法已经准备就绪，并且当他们的方案得到改进时，它们将具有更多的功能。