年仅18岁的尤因·唐（Ewin Tang）已证明，典型计算机能够与量子计算机几乎一样快地解决“推荐问题”。这个重大研究结果否定了量子计算机可大幅提速的最佳例子之一。

尤因•唐的近照

尤因•唐将在今年秋季进入研究生院。

图片来源：Vivian Abagiu摄于得克萨斯大学奥斯汀分校

来自美国得克萨斯州的一名天才少年给量子计算界泼了一盆冷水。在本月早些时候发表于网上的一篇论文（）中，年仅18岁的尤因·唐（Ewin Tang）证明了普通计算机能解决一个重要的计算问题，而性能可能与量子计算机相当。

举个最实际的例子，“推荐问题”涉及亚马逊和Netflix等服务如何确定你可能想要尝试哪些产品。计算机科学家们之前认为，这是最佳例子之一，证明了用量子计算机来解决要快得多，因而推荐问题成为证明这些未来机器强大功能的重要例子。现在唐否定了这个证明。

唐说：“这曾是证明量子计算机可大幅提速的最经典例子之一，现在再也立不住脚。”他在今天春季毕业于得克萨斯大学奥斯汀分校，秋季将攻读华盛顿大学的博士学位。

唐在2014年14岁那年，直接跳过四到六年级后，入读得克萨斯大学奥斯汀分校，主修数学和计算机科学。2017年春季，唐报名就读量子计算领域的著名研究人员斯科特·阿伦森（Scott Aaronson）所教的量子信息课程。阿伦森认为唐是特别有才华的学生，主动表示愿意在一个独立研究项目当他的顾问。阿伦森扔给了唐几个问题来选择，包括推荐问题。唐有点不情愿地选择了推荐问题。

唐说：“我之所以犹豫不决，是因为我看到推荐问题的第一眼觉得这似乎是个难题，但这其实是他给我的最简单的问题。”

推荐问题旨在为商家推荐用户可能喜欢的产品。不妨以Netflix为例。它知道你看过哪些电影。它知道其他数百万用户观看哪些电影。结合这些信息，你接下来可能想要观看什么电影？

你可以想象这些数据排列在巨大的网格或矩阵中，顶部列出了电影，一侧列出了用户，网格中各点的值量化了每个用户是否喜欢每部电影或喜欢的程度。一种好的算法会快速准确地识别电影和用户之间的相似之处，填充矩阵中的空白，以此推荐电影。

2016年，约尔达尼斯•克伦尼迪斯（Iordanis Kerenidis）和阿努帕姆•普拉卡什（Anupam Prakash）这两位计算机科学家发布了一种量子算法，该算法解决推荐问题的速度比任何已知的经典算法都要快得多。他们实现这种速度的提升一方面得益于简化问题：不是填写整个矩阵、确定需要推荐的单一最佳产品，而是开发了一种将用户分成少数类别的方法：他们喜欢大片还是独立电影？然后对现有数据采样，以便推荐的内容足够合适。

在克伦尼迪斯和普拉卡什发表研究成果时，只有少数几个例子表明量子计算机似乎能够以比经典计算机快得多的速度解决问题。那些例子大多数是专门的，它们旨在充分发挥量子计算机优势的狭窄问题，这包括今年早些时候《Quanta》报道的“傅换关联”（forrelation）问题。克伦尼迪斯和普拉卡什的结果之所以令人兴奋，是因为它提供了人们关注的、量子计算机比经典计算机更胜一筹的一个实际问题。

巴黎计算机科学基础研究所的计算机科学家克伦尼迪斯说：“在我看来，这是机器学习和大数据领域的首批例子之一，表明了量子计算机可以做一些我们仍然不知道如何用经典计算机来做的事情。”

克伦尼迪斯和普拉卡什证明了量子计算机能够以远超任何已知算法的速度解决推荐问题，但他们并没有证明不存在一种快速的经典算法。因此，当阿伦森在2017年开始与唐合作时，这就是他提出的那个问题：证明没有一种快速的经典推荐算法，从而证实克伦尼迪斯和普拉卡什认为量子计算机可大幅提速的观点属实。

阿伦森产：“在我看来，这是故事的一个重要细节。”他当时认为，不存在快速的经典算法。

唐于2017年秋季开始研究这项工作，打算将推荐问题作为高级论文课题。唐花了几个月努力证明不可能存在快速的经典算法。随着时间的推移，唐开始认为可能存在这种一样算法。

唐说：“我开始相信有一种快速的经典算法，但没法向自己证明这一点，因为斯科特似乎认为没有这样的经典算法，他可是权威人士。”

最后，随着高级论文的最后期限渐渐临近，唐写信给阿伦森，承认自己越来越感到怀疑：“唐写信跟我说‘我认为有一种快速的经典算法’，”阿伦森如是说。

在整个春季，唐都在撰写研究结果，并与阿伦森一起阐清证明中的几个步骤。唐发现的快速经典算法直接受到克伦尼迪斯和普拉卡什两年前发现的快速量子算法的启发。唐表明，他们在算法中使用的那种量子采样技术在经典环境中可以复制。与克伦尼迪斯和普拉卡什的算法一样，唐的算法以多重对数时间运行，这意味着计算时间随着特征（如数据集中的用户和产品数量）的对数而变化，而且比任何之前已知的经典算法快得多。

一旦唐完成了算法，阿伦森想要在公开发布之前确信结果是正确的。阿伦森说：“我仍然惴惴不安，一旦唐将论文放到网上，万一结果是错的，唐在其职业生涯上的第一篇重大论文就糗大了。”

阿伦森早就计划6月份参加加州大学伯克利分校的量子计算研讨会。这个领域的许多大腕都悉数到场，包括克伦尼迪斯和普拉卡什。阿伦森邀请唐前往伯克利，在正式会议结束后的几天里非正式地介绍他的算法。

在6月18日和19日这两天早上，唐做了两次讲座，从容地回答了听众抛出来的问题。四小时过后，大家达成了一个共识：唐的经典算法似乎是正确的。然而，在座的许多人没有意识到这位演讲者到底有多年轻。克伦尼迪斯说：“我不知道尤因才18岁，从谈话中我绝对听不出来。在我看来，尤因的谈话显得非常成熟。”该算法现正接受发布之前的正式的同行评审。

对于量子计算界而言，唐的结果可谓是一记重拳，也可以说不是。唐否定了证明量子计算优势的最清晰最典型的例子之一。与此同时，唐的论文进一步证明了量子算法研究和经典算法研究确实可以相互促进。

阿伦森说：“唐否定了克伦尼迪斯和普拉卡什认为量子计算机可大幅提速的观点，但是从另一个意义上来说，唐做出了一次重大的改进，在他们的成果上更进一步。要不是他们俩的量子算法，唐也许根本想不出这种经典算法。”