18岁天才华裔少年用一个经典算法，推翻量子加速神话！

新智元报道

来源：quantamagazine

编辑：大明

【新智元导读】一位年仅18岁的华裔少年提出了一种传统计算机AI算法，其运算速度可以与量子计算比肩，相对之前的传统算法实现了运算速度的指数级增长。这一发现不仅推翻了两位量子计算重量级人物的量子加速神话，而且证明了量子算法和经典算法研究之间存在富有成效的相互作用。

在本月早些时候在网上发表的一篇论文中，18岁的Ewin Tang证明用普通计算机可以解决一个重要的计算问题，其性能表现可能与量子计算机相当。

以最实际的问题“推荐问题”为例，这个问题中就涉及亚马逊和Netflix等服务是怎样确定用户想要尝试体验哪些产品的。计算机科学家认为，这个问题是量子计算应用的典型范例之一，和传统计算相比，量子计算解决这个问题速度可能呈指数级增长，这让该问题成为对未来量子计算性能的重要验证。现在Ewin Tang已经证明，事实不尽如此。

14岁上大学，18岁读博士，挑战量子计算领域示范问题

Ewin Tang今年春季毕业于德克萨斯大学奥斯汀分校，并将于今年秋季开始在华盛顿大学攻读博士学位。“这曾经是量子加速计算的最明确的范例之一，不过现在已经不是了。”Ewin Tang说。

Ewin Tang在小学曾从四年级跳级至六年级，2014年，年仅14岁的他进入德克萨斯大学奥斯汀分校就读，主修数学和计算机科学。2017年春，他选了量子计算方面的著名研究员Scott Aaronson讲授的关于量子信息的课程。Aaronson认为他是一位非常有才华的学生，并且自称是一个独立研究项目的顾问。Aaronson给了他一些可供选择的问题，其中就包括推荐问题。Tang有点不情愿地选择了这个问题。

“我当时曾一度犹豫不决，因为这似乎是一个难题，但这是他给我的最简单的问题了。”Ewin Tang说。

这类“推荐问题”旨在为用户喜欢的产品提供建议。以Netflix为例，它知道你看过哪部电影，也了解其他数百万用户所观看的内容。那么根据这些信息，你接下来可能想要观看什么电影？

你可以将这些数据视为在一张巨大网格或矩阵中排列，上方列出的是电影，侧方列出的是用户，而网络中各点的值用于量化每个用户对每部电影的喜爱程度。一个好的算法可以快速准确地识别电影和用户之间的相似度，并填充矩阵中的空白，为用户推荐喜欢的电影。

2016年，计算机科学家Iordanis Kerenidis和Anupam Prakash发布了一种量子算法，能够比任何已知经典算法更加快速地解决推荐问题。他们通过对问题模型的简化来实现这一量子加速过程：不用填满整个矩阵并确定唯一最佳推荐结果，而是开发一种将用户进行分类的方式：比如用户是喜欢商业大片还是独立电影？并对现有数据进行抽样，以生成质量足够高的建议。

在Kerenidis和Prakash开展研究时，量子计算机似乎能够以比经典计算机更快的速度解决一些示例问题。大部分示例问题都是专门的、旨在发挥量子计算机优势的狭隘问题。Kerenidis和Prakash的研究结果令人兴奋，因为该研究提出了一系列人们关心的实际问题，量子计算机在解决这些问题上的表现优于经典计算机。

“我认为，这是机器学习和大数据中的第一个范例，表明量子计算机可以解决一些我们用传统计算机尚无法解决的问题。”现任巴黎计算机科学基础研究所的计算机科学家Kerenidis说。

Kerenidis和Prakash证明了量子计算机能够比任何已知算法更快地解决推荐问题，速度呈指数级增长。但他们没能证明快速的经典算法是不存在的。因此，当Aaronson在2017年开始与Ewin Tang合作时，前者提出的问题就是，要证明在解决推荐问题上不存在快速的经典算法，从而确认Kerenidis和Prakash的量子加速是真实的。

“在我看来，这似乎是完成这个问题最重要的最后一步了。”Aaronson说。他当时认为并不存在快速的经典算法。

Ewin Tang将于今年秋天开始攻读博士

图片来源：Vivian Abagiu, The University of Texasat Austin

传统算法运算速度比肩量子计算，推翻权威学者的结论

Tang于2017年秋天开始这项研究，他打算将推荐问题作为一篇高级论文的题目。在几个月的时间里，他一直试图证明快速的经典算法是不存在的。但随着时间的推移，他开始认为，可能确实存在这样的算法。

“我开始相信确实存在一种快速的经典算法，但我无法向自己证明这一点，而且Scott似乎认为这样的算法不存在，而且他是权威。”Tang说。

最后，随着论文的最后期限越来越近，Tang写信给Aaronson，承认自己对这个问题的怀疑越来越深了：“Tang写信给我说，实际上，'我认为存在一种快速的经典算法'。”Aaronson说。

在2018年的整个春天，Tang写出了算法的结果，并与Aaronson一起理清算法证明中的一些步骤。 Tang发现的这一快速经典算法受到了Kerenidis和Prakash两年前发现的快速量子算法的直接启发。Tang表明，Kerenidis和Prakash在其算法中使用的量子采样技术可以在经典环境中复制。与Kerenidis和Prakash的算法一样，Tang的算法也是在多对数时间内运行的，也就是说计算时间是按照特征（如数据集中的用户和产品的数量）的对数进行缩放的，并且比任何之前已知的经典算法的速度呈指数增长。

在算法完成后，Aaronson希望在公开发表之前确定算法是正确无误的。“我仍然感到紧张，一旦在网上发表论文，如果算法出错了，那么他的职业生涯的第一篇重要论文的价值就会降低。”Aaronson说。

青出于蓝，少年老成

Aaronson计划于6月份参加于加州大学伯克利分校举办的量子计算研讨会。量子计算领域的许多重量级人物都将出席会议，其中就包括Kerenidis和Prakash。在官方会议结束后的几天后，Aaronson邀请Tang来伯克利非正式介绍他的算法。

在6月18日和19日的上午，Tang做了两次演讲，并接受了观众的提问。等到四小时的演讲结束时，在场的人达成了共识：Tang提出的经典算法似乎是正确的。然而，房间里的许多人都没有意识到演讲者的年龄。“我当时并不知道他只有18岁，从交流中完全看不出来。在我看来，他的演讲非常成熟。”Kerenidis说。目前，这一算法在正式发表之前尚待正式的同行评议。

对于量子计算而言，Tang的发现似乎是一个挫折。但也许并非如此。这一发现消灭了量子计算中优势最清晰范例之一。但与此同时，Tang的论文进一步证明了量子算法和经典算法研究之间存在富有成效的相互作用。

“Tang的发现推翻了Kerenidis和Prakash的量子加速神话，但在另一种意义上，这也是一次很大的改进，而且这种改进是在Kerenidis和Prakash研究的基础上做出的。如果没有他们的量子算法作为基础，Tang不可能成功做出这个经典算法。”Aaronson说。

参考链接：

https://www.quantamagazine.org/teenager-finds-classical-alternative-to-quantum-recommendation-algorithm-20180731/