18岁天才准博士用经典算法推翻量子加速

编译:chux

出品:ATYUN订阅号

来自德克萨斯州的一名青少年将量子计算降低了一个档次。在网上发表的一篇论文中,18岁的Ewin Tang证明普通计算机可以解决一个重要的计算问题,其性能可能与量子计算机相当。

在最实际的形式中,“推荐问题”涉及亚马逊和Netflix等服务如何确定你可能想要尝试的产品。计算机科学家认为它是量子计算机上解决速度快得多的问题的最佳例子之一,这也使其成为这些未来机器功能的重要验证。现在Tang已经推翻了验证。

“这是量子加速的最明确的例子之一,现在已经不成立了,”Tang说,他在春季毕业于德克萨斯大学奥斯汀分校,秋天将在华盛顿大学开始攻读博士学位。

2014年14岁时,在跳过四年级到六年级之后,Tang就读于UT奥斯汀,主修数学和计算机科学。2017年春天,Tang在量子计算方面的着名研究员Scott Aaronson教授量子信息课程。Aaronson认为Tang是一位非常有才华的学生,并且自称是一个独立研究项目的顾问。Aaronson给了Tang一些可供选择的问题,包括推荐问题。唐有点不情愿地选择了它。

Tang说,“我犹豫不决,因为当我看着它时,这似乎是一个难题,但这是他给我的最简单的问题。”

推荐问题旨在为用户喜欢的产品提供建议。考虑一下Netflix的情况。它知道你看过哪部电影。它知道其他数百万用户所观看的内容。根据这些信息,你接下来可能想要观看什么?

你可以将这些数据视为以巨大网格或矩阵排列,顶部列出的电影,侧面列出的用户,以及网格中各点的值,用于量化每个用户是否喜欢每部电影的程度。一个好的算法可以通过快速准确地识别电影和用户之间的相似性并填充矩阵中的空白来生成推荐。

2016年,计算机科学家Iordanis Kerenidis和Anupam Prakash发布了一种量子算法,该算法以比任何已知经典算法更快的速度解决推荐问题。他们通过简化问题来实现这一量子加速:不是填写整个矩阵并确定推荐的单一最佳产品,而是开发了一种将用户分类为少数类别的方式,如他们喜欢大片还是独立电影?并对现有数据进行抽样,以便生成足够好的建议。

在Kerenidis和Prakash的工作时,量子计算机似乎能够以比经典计算机指数更快的速度解决问题的例子。大多数这些例子都是专门的,它们是旨在发挥量子计算机优势的狭隘问题(包括今年早些时候广达所涵盖的“相关”问题)。Kerenidis和Prakash的结果令人兴奋,因为它提供了人们关心量子计算机优于经典计算机的真实问题。

巴黎计算机科学基础研究所的计算机科学家Kerenidis说,“据我所知,它是机器学习和大数据中首个展示量子计算可以做一些我们仍然未解决的事情。”

Kerenidis和Prakash证明了量子计算机能够比任何已知算法以指数方式更快地解决推荐问题,但它们并不能证明快速经典算法不存在。因此,当Aaronson在2017年开始与Tang合作时,这就是他提出的问题,证明没有快速的经典推荐算法,从而确认Kerenidis和Prakash的量子加速是真实的。

Aaronson说他当时也认为不存在快速的经典算法。

Tang于2017年秋季开始工作,打算将推荐问题作为高级论文。几个月来,Tang想办法证明快速的经典算法是不可能的。随着时间的推移,他开始认为也许这样的算法是可能的。

“我开始相信有一种快速的经典算法,但我无法向自己证明这一点,因为Scott似乎认为没有,而且他是这方面的权威,”Tang说。

最后,随着高级论文的最后期限结束,Tang写信给Aaronson指出了他的怀疑:“实际上,我认为有一种快速的经典算法。”

在整个春天,Tang写了结果并与Aaronson合作理清证明中的一些步骤。Tang发现的快速经典算法直接受到Kerenidis和Prakash两年前发现的快速量子算法的启发。他表明,他们在算法中使用的那种量子采样技术可以在经典环境中复制。与Kerenidis和Prakash的算法一样,Tang的算法在多对数时间内运行,这意味着计算时间与特征的对数(如数据集中的用户和产品的数量)进行缩放,并且比任何先前已知的经典算法快指数倍。

一旦Tang完成了算法,Aaronson希望在公开发布之前确定它是正确的。“我仍然感到紧张,一旦在网上发表论文,如果这是错的,那么Tang的职业生涯的第一篇大论文就会惨遭失败。”

Aaronson计划于6月份参加加州大学伯克利分校的量子计算研讨会。该领域的许多大腕都将出现在那里,包括Kerenidis和Prakash。在官方会议结束后的几天里,Aaronson邀请Tang来伯克利非正式地介绍他的算法。

在6月18日和19日的早晨,Tang做了两次讲座,同时向观众提出了问题。到四小时结束时,出现了一个共识:Tang的经典算法似乎是正确的。然而,房间里的许多人都没有意识到演讲者的年龄。“我不知道Ewin只有18岁,对我来说,Ewin是演讲非常成熟。”Kerenidis说。该算法现在在发布之前面临正式的同行评审。

对于量子计算,Tang的结果是一个倒退。或者并不是。Tang已经消除了量子优势中最清晰,最好的例子之一。与此同时,唐的论文进一步证明了量子算法和经典算法研究之间富有成效的相互作用。

Aaronson表示,“Tang杀死了Kerenidis和Prakash的量子加速,但在另一种意义上,这是一个很大的改进,并且是在他们所做的基础上进行。如果没有他们的量子算法,Tang也不会想出这种经典算法。”

论文:arxiv.org/abs/1807.04271

原文发布于微信公众号 - ATYUN订阅号(atyun_com)

原文发表时间:2018-08-02

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏专知

【下载】Python迁移学习实战书籍和代码《Hands-On Transfer Learning with Python》

【导读】英特尔数据科学家Dipanjan Sarkar等人最新撰写的Python迁移学习实战书籍《Hands-On Transfer Learning with...

5225
来自专栏AI科技大本营的专栏

Yann LeCun:距离“真正的” AI,我们还缺什么?

【AI科技大本营导读】今天是 GMIC Beijing 2018 大会第一天,首个演讲者是 Facebook 首席 AI 科学家 Yann LeCun。他讲述...

1262
来自专栏AI科技评论

视频 | 没有博士学位和顶会论文,我如何拿到DeepMind的offer?

AI 科技评论按:这里是,油管 Artificial Intelligence Education 专栏,原作者 Siraj Raval 授权雷锋字幕组编译。 ...

4427
来自专栏ATYUN订阅号

IBM研究人员通过探索缺失的事物来解释机器学习模型

在《白额闪电》(The Adventure of the Silver Blaze)中,福尔摩斯并不是通过能看到的线索解决了案件,而是通过注意到某一事物的缺失...

1204
来自专栏腾讯高校合作

CCF-腾讯犀牛鸟基金项目课题介绍(一)——机器学习&计算机视觉及模式识别

3378
来自专栏新智元

Geoff Hinton 专访:Waston 系统和深度学习有什么区别?

关键词还没输入完毕,Google已经返回了你想要的搜索结果;Facebook能将你上传的照片自动打上标签;无人驾驶汽车都已经开上路了。这些所有令人觉得不可思议的...

3696
来自专栏新智元

【独家】前百度资深科学家夏粉创业研发中国版Auto ML,两轮融资估值4亿

---- 新智元报道 作者:张乾 【新智元导读】创建先进的机器学习模型既需要专业的技术人员,也非常耗时耗力,是企业在应用机器学习中的一大痛点。现在包括...

4156
来自专栏量子位

视频版ImageNet?快手搞了一场用户兴趣建模大赛 | 附前三名干货

或许你多少有些了解,在以深度学习为核心的AI算法大杀四方,机器在理解图像、语音等方面都取得了很大的进步时,理解视频内容仍还是一件很困难的事情。

2073
来自专栏人工智能快报

专家展望未来5年深度学习技术的发展

2015年12月29日,美国科技资讯网Re-work发文,总结了多位深度学习专家对未来5年深度学习技术的发展预测。 (1)人工智能研究机构OpenAI的研究主任...

3356
来自专栏ATYUN订阅号

赫尔辛基大学AI基础教程:人工智能的相关领域(1.2节)

除了人工智能本身外,还有其他几个与之密切相关的领域,包括机器学习,数据科学和深度学习。

1273

扫码关注云+社区

领取腾讯云代金券