18岁华裔少年打破量子计算神话?他的算法更快(图)

今日头条
Toutiao
最新回复:2018年8月10日 19点38分 PT
  返回列表
26175 阅读
11 评论
科研圈

最近,一名得州(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 岁,我整场讲座都没听出来,他演讲的时候显得很成熟。”目前,只要等到同行评议做完,这项算法就可以正式发表了。

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

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

m
mmnn66777
1 楼
量子计算就是个大忽悠。
唐爽粉丝团
2 楼
周立波一定会记住他的样貌,下次在餐馆遇到才会认出他来。然后他不认识周是哪个。
轻松轻松
3 楼
人家研究的是在一条崎岖的杂草斜坡上,骑驴比宝汽车快,这媒体就说车过时了,骑驴更快,现在的媒体,断章取义,一知半解,忽悠夸大,不看也罢,就像这里
酒酿圆子羹
4 楼
最近去超市买完东西付账拿收据时会给一张下礼拜采购推荐的副券,我猜说不定就是这个量子计算搞出来的新东东,不过我发现好多推荐是这次刚买的东西,事实上很多食品我不会每个礼拜都买,譬如奶酪我会一个多月才买一块,如果我刚买了一块奶酪那下个礼拜肯定不会买,所以把奶酪作为下礼拜推荐食品就很不合理了,看来这个超市量子计算还没达到对每个消费者数据进行更合理化运算
b
baixunhuan
5 楼
一个崎岖陡峭的山路,常见的陆地交通工具,譬如操控极好的汽车把一个邮包送上山顶需要10分钟。一种即将面世的交通工具速度将是汽车速度的10倍,可以1分钟到达。导师让小伙子证明目前在着地的路上运输工具不可能有达到这个速度的,小伙子研究了一段时间发现健壮的山羚羊可以1分钟左右把邮包送到山顶。 小编:新兴的交通工具可能没有羚羊跑的快
S
Sam大树
6 楼
只是论证某一状况下经典算法可以与量子算法一样快, 不是更快。
维真
7 楼
牛啊。看看NP-completeness问题是不是迎刃而解了,有O(N logN)或更好的算法解决掉所有这类千禧年世纪难题。
真爷们不折腾
8 楼
少年班?
M
Morphin
9 楼
amazon的推荐还是不够聪明, 我看过没买的,应该推荐,但是我买过的,再给我推荐,岂不是很烦人? 我总想为啥搞这个算法的不修正一下
f
fengrmi
10 楼
看都不用看知道是胡说八道。
J
JustAsked
11 楼
华人之光!好!