来自德克萨斯州的一名青少年将量子计算降低了一个档次。在网上发表的一篇论文中，18岁的Ewin Tang证明普通计算机可以解决一个重要的计算问题，其性能可能与量子计算机相当。

在最实际的形式中，“推荐问题”涉及亚马逊和Netflix等服务如何确定你可能想要尝试的产品。计算机科学家认为它是量子计算机上解决速度快得多的问题的最佳例子之一，这也使其成为这些未来机器功能的重要验证。现在Tang已经推翻了验证。

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

2014年14岁时，在跳过四年级到六年级之后，Tang就读于UT奥斯汀，主修数学和计算机科学。2017年春天，Tang在量子计算方面的着名研究员Scott Aaronson教授量子信息课程。Aaronson认为Tang是一位非常有才华的学生，并且自称是一个独立研究项目的顾问。Aaronson给了Tang一些可供选择的问题，包括推荐问题。唐有点不情愿地选择了它。

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

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

你可以将这些数据视为以巨大网格或矩阵排列，顶部列出的电影，侧面列出的用户，以及网格中各点的值，用于量化每个用户是否喜欢每部电影的程度。一个好的算法可以通过快速准确地识别电影和用户之间的相似性并填充矩阵中的空白来生成推荐。

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

在Kerenidis和Prakash的工作时，量子计算机似乎能够以比经典计算机指数更快的速度解决问题的例子。大多数这些例子都是专门的，它们是旨在发挥量子计算机优势的狭隘问题（包括今年早些时候广达所涵盖的“相关”问题）。Kerenidis和Prakash的结果令人兴奋，因为它提供了人们关心量子计算机优于经典计算机的真实问题。

巴黎计算机科学基础研究所的计算机科学家Kerenidis说，“据我所知，它是机器学习和大数据中首个展示量子计算可以做一些我们仍然未解决的事情。”

Kerenidis和Prakash证明了量子计算机能够比任何已知算法以指数方式更快地解决推荐问题，但它们并不能证明快速经典算法不存在。因此，当Aaronson在2017年开始与Tang合作时，这就是他提出的问题，证明没有快速的经典推荐算法，从而确认Kerenidis和Prakash的量子加速是真实的。

Aaronson说他当时也认为不存在快速的经典算法。

Tang于2017年秋季开始工作，打算将推荐问题作为高级论文。几个月来，Tang想办法证明快速的经典算法是不可能的。随着时间的推移，他开始认为也许这样的算法是可能的。

“我开始相信有一种快速的经典算法，但我无法向自己证明这一点，因为Scott似乎认为没有，而且他是这方面的权威，”Tang说。

最后，随着高级论文的最后期限结束，Tang写信给Aaronson指出了他的怀疑：“实际上，我认为有一种快速的经典算法。”

在整个春天，Tang写了结果并与Aaronson合作理清证明中的一些步骤。Tang发现的快速经典算法直接受到Kerenidis和Prakash两年前发现的快速量子算法的启发。他表明，他们在算法中使用的那种量子采样技术可以在经典环境中复制。与Kerenidis和Prakash的算法一样，Tang的算法在多对数时间内运行，这意味着计算时间与特征的对数（如数据集中的用户和产品的数量）进行缩放，并且比任何先前已知的经典算法快指数倍。

一旦Tang完成了算法，Aaronson希望在公开发布之前确定它是正确的。“我仍然感到紧张，一旦在网上发表论文，如果这是错的，那么Tang的职业生涯的第一篇大论文就会惨遭失败。”

Aaronson计划于6月份参加加州大学伯克利分校的量子计算研讨会。该领域的许多大腕都将出现在那里，包括Kerenidis和Prakash。在官方会议结束后的几天里，Aaronson邀请Tang来伯克利非正式地介绍他的算法。

在6月18日和19日的早晨，Tang做了两次讲座，同时向观众提出了问题。到四小时结束时，出现了一个共识：Tang的经典算法似乎是正确的。然而，房间里的许多人都没有意识到演讲者的年龄。“我不知道Ewin只有18岁，对我来说，Ewin是演讲非常成熟。”Kerenidis说。该算法现在在发布之前面临正式的同行评审。

对于量子计算，Tang的结果是一个倒退。或者并不是。Tang已经消除了量子优势中最清晰，最好的例子之一。与此同时，唐的论文进一步证明了量子算法和经典算法研究之间富有成效的相互作用。

Aaronson表示，“Tang杀死了Kerenidis和Prakash的量子加速，但在另一种意义上，这是一个很大的改进，并且是在他们所做的基础上进行。如果没有他们的量子算法，Tang也不会想出这种经典算法。”

论文：arxiv.org/abs/1807.04271