18岁华裔少年打破量子计算神话？他的经典算法更快！

　　来源：科研圈

　　最近，一名得州（Texas）的华裔少年将量子计算“拉下神坛”。现年 18 岁的埃文?唐（Ewin Tang）7 月初公布在 arXiv 上的一篇论文，使得经典计算机也能“媲美”量子计算机，解决重要计算问题。

　　日常生活中，在 Amazon 及 Netflix 等服务商给客户推荐可能喜欢的产品时，算法工程师会面临一个“推荐问题”（recommendation problem）。计算机科学家认为如果将这种问题交给量子计算机，计算时间能够大大缩短，并且彰显出这种还未出世的计算机运算速度之快。但唐改变了这一假设。

　　今年春季刚从德克萨斯大学奥斯汀分校（the University of Texas， Austin）毕业，准备秋季攻读华盛顿大学（the University of Washington）博士的唐说道：“以前推荐问题能很直接地证明量子计算能够提高运算速度，但现在不再是这样了。”

　　少年天才

　　2014 年，14 岁的唐跳级进入德克萨斯大学奥斯汀分校学习数学和计算机科学。2017 年春季，他选了量子计算领域专家
斯科特?阿伦森
（Scott Aaronson）的量子信息课。阿伦森觉得唐很有天分，主动担任了唐的独立研究项目的指导教师：他给唐提供了一大堆研究备选题目，唐勉勉强强地选了其中的推荐问题。


华裔少年埃文?唐。图片来源：Flickr

　　唐表示：“我当时很犹豫，攻克推荐问题在我看来困难重重，可这已经是备选课题里最简单的一个了。”

　　推荐问题的初衷，是为用户推荐可能感兴趣的产品。就拿 Netflix 来说，它记载了你看过的电影的信息，记载了它数百万用户看过的电影的信息。根据这些信息，如何为你做出影视推荐？

　　你可以把这些数据想成是放在一个超大的网格（即矩阵）中，网格上方是电影信息，下方是看过这些电影的用户，网格节点的值则表示用户对每部电影的喜爱程度。优秀的算法可以快速、精准识别用户与电影间的匹配度来填充空格，进而生成推荐。

　　量子算法

　　2016 年，计算机科学家约丹尼斯?克里尼迪斯（IordanisKerenidis）和阿努帕姆?普拉卡什（Anupam Prakash）提出了一种量子算法，该算法解决推荐问题的速度比任何已知经典算法都快。这种量子算法计算速度的提高，得益于他们对问题的简化：最佳推荐不再需要用填满整个矩阵的方式来获得――可以先将用户分成几小类（比如用户是喜欢大片还是小众电影），再从现有数据中抽样，生成合适的推荐。

　　在克里尼迪斯和普拉卡什提出上述算法之前，能体现出量子计算机优越性的例子并不多。而且大多是为体现量子计算机优越性而专门设计的，比如“相关（correlation）问题”（判断两个随机数字序列生成器生成的两组序列是完全独立的，还是以某种隐藏的形式相关联的）。但克里尼迪斯与普拉卡什提出的是一个现实生活中的问题，与之前的专业问题相比，量子计算机的优越性更能引起大众的关心。

　　巴黎计算机科学基础研究所（the Research Institute on the Foundations of Computer Science in Paris）的计算机科学家克里尼迪斯说：“我认为，这是在机器学习和大数据领域，量子计算机能解决，而经典计算机不能的第一批案例。”

　　克里尼迪斯和普拉卡什已证明，量子计算机解决推荐问题的速度，比任何已知算法都要快，但这并不能证明计算速度更快的经典算法一定不存在。所以2017年阿伦森给唐提出的研究课题是：证明任何经典推荐算法的计算速度都没有量子推荐算法快，克里尼迪斯与普拉卡什的量子算法确实能提高计算速度。

　　阿伦森当时坚信不存在速度更快的经典算法：“在我看来，这是完成整个故事很重要的一环。”

　　经典算法能更快？

　　2017 年唐开始了这项研究，打算将推荐问题作为自己毕业论文的课题。开始的几个月，唐都在努力证明更快的经典算法不存在。但随着研究的深入，唐不禁猜测，这样的算法没准是存在的。

　　唐表示：“我越来越觉得存在这样一个速度更快的经典算法，但我对自己的想法很怀疑，毕竟斯科特坚信不存在这样的算法，而他更权威。”

　　随着毕业论文截稿日期的临近，唐终于给阿伦森写信承认了自己的疑问：“唐写道，事实上‘我认为这样的算法存在’。”

　　2017 年春，唐写出了这个经典算法，并在阿伦森的指导下完善了其中的某些步骤。受两年前克里尼迪斯与普拉卡什算法的启发，唐发现量子算法中的量子抽样思想可以直接应用到经典算法中，进而完成了自己的算法。与量子算法相同，唐的算法也在多重对数时间内运行，即计算时间与特征量（如数据集中用户量、产品量等）的对数相关，运算速度与以往的经典算法相比有指数级提升。

　　唐写完算法之后，阿伦森希望能在发表之前确认算法的正确性：“我很是紧张，一旦唐公布在网上的论文存在错误，他的学术生涯会受到很大影响。”

　　阿伦森 6 月参加了加州大学伯克利分校（the University of California， Berkeley）的量子计算研讨会。包括克里尼迪斯、普拉卡什等在内的多名量子计算领域专家都将出席该会议。阿伦森打算在正式会议结束后，邀请唐到伯克利讲讲他的经典推荐算法。

　　唐分别在 6 月 18 日和 19 日上午举办了两场讲座，回答了听众的提问。在长达四小时的讲座结束后，大家达成了共识：唐的经典算法应该是对的。然而许多在场听众都没意识到，这位看似老成的演讲者年纪非常小。克里尼迪斯描述道：“真不敢相信唐只有 18 岁，我整场讲座都没听出来，他演讲的时候显得很成熟。”目前，只要等到同行评议做完，这项算法就可以正式发表了。

　　唐的算法给了量子计算一记重拳？可能是也可能不是。唐改变了能表明量子计算优越性的一个最清晰、最直白的例子；但同时，唐的论文也能很好地证明，量子算法与经典算法之间是相互影响、相辅相成的。

　　阿伦森评价：“唐扼杀了（克里尼迪斯与普拉卡什的）量子计算优越性，但从另一个角度来看，正是他们的算法孕育出了唐的新算法。没有他们的量子算法，就不会有今天的经典算法。”