「别人家的孩子」又在搞事情，18岁华裔少年推翻权威量子算法研究

源济

「别人家的孩子」又在搞事情，18岁华裔少年推翻权威量子算法研究

造就  2018-08-06

尤因·唐将于今年秋季进入研究生院攻读博士学位

一位18岁的华裔天才少年给向来高高在上的量子计算「泼了一盆冷水」。

在7月上旬发表于网络的一篇论文中，来自得克萨斯州的尤因·唐（Ewin Tang）证明，传统计算机能够以接近量子计算机的速度解决一个重要的计算问题。这个问题最常见的形式为「推荐问题」，它涉及亚马逊和Netflix这样的服务如何确定用户可能想要尝试的产品。

计算机科学家认为，在量子计算机能够以指数级的更快速度加以解决的问题中，「推荐问题」是最佳实例之一，并且提供了对这些未来机器能力的重要验证。现在，唐推翻了这一验证。

“这是量子加速最明确的实例之一，但现在已经不复存在了，”唐说道。

01

「推荐问题」的量子算法

「推荐问题」旨在就用户可能喜欢的产品提供建议。

以Netflix为例，它知道你看过哪些电影，它还知道另外数百万用户看过的节目。根据这些信息，是不是可以算出你接下来最有可能想要观看什么内容呢？

你可以想象一下，这些信息被排列在一个巨大的网格当中，其中顶部列出的是电影，底部侧边列出的是用户，网格中各个点的值用于量化各个用户是否喜欢各部电影，或者喜欢到何种程度。一种好的算法可以通过快速和准确地识别电影和用户之间的相似性并填充矩阵中的空白，以此生成推荐内容。

2016年，计算机科学家艾奥丹尼斯·科伦尼迪斯（Iordanis Kerenidis）和阿努帕姆·普拉卡什（Anupam Prakash）发明了一种量子计算算法，它能够以快过任何已知传统计算算法的速度解决「推荐问题」。

从某种程度上说，这两位科学家实现量子加速是通过简化问题来实现的：不是填充整个矩阵以及确定要推荐的单个最佳产品，而是把用户归类到少数几个类别（比如用户是喜欢大片还是独立电影），并对现有数据进行采样，以此生成足够好的推荐。

在科伦尼迪斯和普拉卡什发表他们研究成果的时候，相较于传统计算机，量子计算机似乎只能在少数几个问题上以指数级的更快速度进行解决。而且，大多数问题实例都是专门化的——它们都是被设计来发挥量子计算机优势的狭隘问题。

科伦尼迪斯和普拉卡什的研究成果令人振奋，因为「推荐问题」是人们关心的现实问题，而量子计算机在解决它时的表现优于传统计算机。

“据我所知，这是机器学习和大数据领域的第一个实例，让我们得以展示量子计算机能够完成一些传统计算机无法完成的事情，”供职于巴黎计算机科学基础研究所（Research Institute on the Foundations of Computer Science）的科伦尼迪斯说道。

02

“我认为存在一种快速的传统算法”

用现在流行的话来说，唐从小就是那个「别人家的孩子」。

2014年，在从四年级直接跳到六年级之后，14岁的唐被德州大学奥斯汀分校录取，主修数学和计算机科学。今年春季，他从该校毕业，并将在秋季前往华盛顿大学攻读博士学位。

2017年春，唐开始学习由著名量子计算研究员斯科特·亚伦森（Scott Aaronson）教授的量子信息课程。亚伦森认为唐是一位天赋异禀的学生，并亲自担任后者一个独立研究项目的顾问。亚伦森列出一些问题给唐挑选，其中就包括「推荐问题」，唐有点不情愿地选中了它。

“我当时犹豫不决，因为当我看着这个问题时，看上去似乎很难，但这已经是他给我的问题中最简单的了，”唐说道。

科伦尼迪斯和普拉卡什证明，相较于任何已知算法，量子计算机能够以指数级的更快速度解决「推荐问题」；不过，他们没有证明不存在一种快速的传统推荐算法。因此，当亚伦森在2017年开始跟唐合作开展研究时，这就是他提出的问题：证明不存在快速的传统推荐算法，从而确认科伦尼迪斯和普拉卡什实现的量子加速是真实的。

“在我看来，为了让这件事板上钉钉，这似乎是一个需要完善的重要细节，”亚伦森说道。当时他认为并不存在一种快速的传统推荐算法。

2017年秋季，唐开始了自己的研究工作，他打算把「推荐问题」当成毕业论文的主题。在几个月的时间里，唐难于证明快速的传统算法是不可能存在的。但随着时间的推移，他开始认为，或许这样的算法真有可能存在。

“我开始相信存在一种快速的传统算法，但我无法向自己证明这一点，因为斯科特倾向于认为它不存在，而他是权威人士，”唐如是说。

最后，在毕业论文截稿日逼近的情况下，唐给亚伦森写了一封信，将自己日益增长的怀疑和盘托出。“唐写信给我说，事实上，‘我认为存在一种快速的传统算法’，”亚伦森回忆道。

整个春季，唐都在做这项研究，他把结果写了出来，并跟亚伦森合作阐释证明中的一些步骤。唐发现的快速传统算法受到了科伦尼迪斯和普拉卡什在两年前发现的快速量子算法的直接启发，他证明两人在算法中使用的量子采样方法可以被复刻到传统计算环境当中。

唐的算法也是一种对数多项式时间算法——这意味着计算时间跟特征的对数（比如数据集中用户和产品的数量）成比例关系——而且它的速度要比任何之前已知的传统算法快得多。

在唐完成了这个算法之后，亚伦森希望在公开发表前确定它是正确的。“我仍然感到紧张，一旦唐在网上发表了论文，如果它是错的，那么（唐）学术生涯的第一篇重要论文就会折戟,”亚伦森说道。

当时，亚伦森计划于6月份参加在加州大学伯克利分校举行的一场量子计算研讨会。届时该领域的很多大腕都会出现在那里，包括科伦尼迪斯和普拉卡什。在正式会议结束之后，亚伦森邀请唐来到伯克利，对他的算法做非正式介绍。

在6月18日和19日的上午，唐做了两场讲座，并对听众提出的问题进行解答。4小时的讲座结束后，大家有了一个共识：唐的传统算法似乎是正确的。然而，在座的很多人并没有意识到这位演讲者有多年轻。“我之前不知道尤因才18岁，当然我也没有从演讲中了解到这一点。在我看来，尤因的演讲非常成熟稳重。”科伦尼迪斯说道。

现在，唐的算法正在接受正式的同行评审。

“唐推翻了（科伦尼迪斯和普拉卡什的）量子加速，但另一个意义上来说，他实现了一项重大改进，在他们的研究成果上更进了一步。如果没有他们的量子算法，唐也不会想出这种传统算法。”亚伦森如是评价说。