18岁华裔少年颠覆量子加速优势，推动量子算法经典化

选自quantamagazine，作者：Kevin Hartnett，参与：机器之心编辑部。

据国外媒体 Quantamagazine 报道，来自 UT Austin，刚刚年满 18 岁的 Ewin Tang 最近证明了经典算法能以和量子计算机相近的速度解决推荐问题。该结果淘汰了量子加速的最佳案例之一。这位天才少年的惊人成就已在社交网络中引发了激烈的讨论。

国内量子计算专家也对此事发表了不同观点。如百度量子实验室负责人段润尧在朋友圈评论说，「这是有关经典推荐算法的非常有意思的进展。原先 Kerenidis 和 Prakash 证明了量子计算机能够比任何已知算法以指数级的速度解决推荐问题，但他们并没有证明快速的经典算法不存在。而 18 岁的 Ewin 则给出了一个快速的经典推荐算法，从而说明 KP 量子算法其实相对于经典算法并无实际优势。这是典型的因量子算法思想激发经典快速算法发现的例子，相信这样的例子还会有一些，所谓『量子快速算法的经典化』。」

南科大研究副教授郑盛根对机器之心表示，「这个算法如果能实用，个人觉得并不会挑战量子计算，而是会推高量子算法的理论研究，把量子算法有效经典化将成为热点。也就是多年前有些学者提出的 plan B: 如果量子计算机造不出来，那么我们可以用量子计算的思想证明经典的东西。」

以下是对 Quantamagazine 相关报道内容的编译：

一位来自德克萨斯州的少年将量子计算「拉下神坛」。在上月初发布在网上的一篇论文《A quantum-inspired classical algorithm for recommendation systems》中，18 岁的 Ewin Tang 证明普通计算机可以解决一个重要的计算问题，且其性能可与量子计算机媲美。

「推荐问题」在实践层面上类似于 Amazon 和 Netflix 等服务商如何确定你喜欢的产品。计算机科学家曾认为这是利用量子计算机快速解决问题的最佳案例之一——这也成为量子计算机这种未来机器的力量验证标准。但是现在 Tang 推翻了这个验证。

「推荐问题是量子加速最直观的案例，但现在已经不成立了。」Tang 说，他今年春天从德克萨斯大学奥斯汀分校毕业，并将于今年秋天前往华盛顿大学攻读计算机科学博士学位。

Ewin Tang 从很小的时候就显露出了天才的一面。据介绍，他在 13 岁时就成为了 UT Arlington 有史以来最年轻的 4.0GPA（以及全 A）学生。2014 年，14 岁的 Tang 连跳三级，直接进入德州大学奥斯汀分校（UT Austin）学习数学和计算机科学。

在量子计算领域的之外，Ewin Tang 还参与发表过四篇生物材料领域的论文。他也是发表在《Journal of Biomedical Nanotechnology》上论文「In Vivo Imaging of Infection Using a Bacteria-Targeting Optical Nanoprobe」的第一作者。

2017 年春天，Tang 选修了量子信息课程，该课程由量子计算领域的杰出研究者 Scott Aaronson 讲授。Aaronson 认为 Tang 是个非常优秀的学生，并让他担任一个独立研究项目的技术顾问。Aaronson 给 Tang 出了一些棘手的问题，包括推荐问题。Tang 有些不情愿地选择了推荐问题。

Tang 说：「我当时很犹豫，因为我觉得推荐问题很难，但这已经是他给我的最简单的问题了。」

推荐问题是指给用户推荐他们喜欢的产品。以 Netflix 为例。它知道你看过什么电影。它也知道其他数百万用户看了些什么。有了这些信息，它就能推断你接下来最想看什么。

你可以把这些信息想象成一个巨大的网格或矩阵，顶部列出电影，底部列出用户，网格交点的值量化了每个用户对每个电影的喜爱程度。一个好的算法可以通过快速准确地识别出用户和电影间的相似性、填补矩阵中的空白（做出相应的矩阵计算）来生成推荐内容。

2016 年，计算机科学家 Iordanis Kerenidis 和 Anupam Prakash 发表了一种量子算法，能以任何已知经典算法的指数级速度解决推荐系统问题。他们能实现量子加速，部分原因在于简化了问题：他们没有填充整个矩阵并确定单个最佳推荐产品，而是开发了一种将用户分为少数几个类别的方法（例如，他们喜欢大片还是独立电影），并采样已有数据来生成足够好的推荐。

他们在《Quantum Recommendation Systems》提出的算法实现了 O(poly(k)polylog(mn)) 的幂对数计算时间复杂度，当时任何已知的经典推荐算法都只能实现矩阵维数的多项式时间复杂度。其中 k 是推荐项的数量，m 是用户数，n 是产品数。推荐算法需要通过 mxn 的偏好矩阵计算出 k 个用户最喜欢产品的排序。

在 Kerenidis 和 Prakash 发表他们的研究时，仅有少数几例量子计算机有可能实现比经典计算机指数级快的求解速度的问题。大部分这类问题都是特定的，即它们是发挥量子计算机威力的狭窄范畴（这些问题包括「forrelation」）。Kerenidis 和 Prakash 的研究结果令人激动，因为它提供了一个真实世界中人们所关心的量子计算超越经典计算的问题。

「在我看来，这是机器学习和大数据领域中最早展示量子计算可求解经典计算尚未解决的问题的案例之一。」巴黎计算机科学基础研究所的计算机科学家 Kerenidis 说。

Kerenidis 和 Prakash 证明了量子计算机比任何已知经典算法在解决推荐问题时都要快得多，但他们没有证明不存在快速的经典算法。因此当 Aaronson 在 2017 年和 Tang 开始合作时，他提出了这个问题：证明不存在快速的经典推荐算法，继而证实 Kerenidis 和 Prakash 的量子加速是真实的。Aaronson 当时确实是这么认为的。

Tang 在 2017 年秋天开始进行该研究，想要用推荐问题的研究作为毕业论文。几个月后，他证明了不存在适用于该问题的快速经典算法。但随着时间的推移，Tang 开始思考或许这样的算法可行呢。

「我开始认为存在一种可解决推荐问题的快速经典算法，但我自己也不太确定，因为 Scott 似乎认为这样的算法并不存在，而他是这方面的权威。」Tang 说道。

最终，随着毕业论文 deadline 临近，Tang 向 Aaronson 写信，坦诚了他的疑问：「我认为存在一种快速的经典算法。」

整个春天，Tang 为找到这一算法而努力，他与 Aaronson 一起理清证明步骤。Tang 发现的快速经典算法受到 Kerenidis 和 Prakash 两年前发现的快速量子算法的启发。Tang 展示了 Kerenidis 和 Prakash 在他们算法中使用的量子采样技术可以在经典计算机设置中重现。与 Kerenidis 和 Prakash 的算法类似，Tang 的算法也以幂对数时间运行，这意味着计算时间会因特征值（如数据集中用户和产品的数量）的对数而发生伸缩，它比之前已知的所有经典算法都要快上指数倍。

Tang 完成该算法后，Aaronson 想在公开之前先确认其正确性。「我仍然很担心，这篇论文被放到网上后，万一该研究是错误的，那么 Tang 学术生涯中第一篇「伟大」论文就将遭遇滑铁卢。」Aaronson 说道。

Aaronson 计划参加六月份在加州大学伯克利分校举办的一场量子计算研讨会。该领域很多大牛都将出席这次研讨会，包括 Kerenidis 和 Prakash。Aaronson 邀请 Tang 来到伯克利，在正式会议结束后非正式地展示其算法。

6 月 18 日、19 日上午，Tang 进行了两次演讲，同时回答了观众的提问。四小时的演讲结束后，大家达成了共识：Tang 的经典算法似乎是正确的。但是，当时身处现场的很多人都没有意识到这位演讲者是多么年轻。「我不知道 Ewin 只有 18 岁，演讲时并没有得到这个信息。对我来说，Ewin 的演讲非常成熟。」Kerenidis 说道。现在该算法正面临正式的出版前的同行评议。

Tang 在《A quantum-inspired classical algorithm for recommendation systems》中提出的经典推荐算法实现了 O(poly(k)polylog(m,n)) 的计算时间复杂度，比之前实现和 m、n 呈线性关系的时间复杂度的经典算法速度有指数级提高。

论文地址：https://arxiv.org/abs/1807.04271

对于量子计算来说，Tang 的结果是一种倒退。抑或不是。Tang 去除了量子算法最明确的一个优势。同时，他的论文进一步证明了量子算法和经典算法研究之间密切的相互作用。

「Tang『杀死了』Kerenidis 和 Prakash 的量子加速，但从另一种角度来看，他也极大地改进了后者，而且 Tang 的算法也建立在后者基础上。如果没有他们的量子算法，Tang 也不可能发现该经典算法。」Aaronson 说道。

在 HackNews 上网友对此议论纷纷；有人认为即使是 Tang 他们在论文中求解的问题也过于简化，推荐算法本身也不是很重要的问题类，能不能给学术界带来深刻影响尚有疑问；有人甚至大胆假设经典计算和量子计算在广义上是等价的，当然这已经被之前的「forrelation」问题所否定了（科学家近期证明了存在量子计算机能解决而经典计算机不可能解决的问题）；还有人则持更加开放的态度，猜测仍然存在其它类型的量子算法可以转换为相似计算复杂度的经典算法。

机器之心的小伙伴怎么看呢？