18岁华裔少年打破量子计算神话 他的算法更快?(图)
量子计算机(图片来源:Adobe stock)
【看中国2018年8月13日讯】现年18岁的华裔少年埃文・唐(Ewin Tang)7月初公布在arXiv上的一篇论文,使得经典计算机也能“媲美”量子计算机,解决重要计算问题。
据《科研圈》报道,在Amazon及Netflix等服务商给客户推荐可能喜欢的产品时,算法工程师会面临一个“推荐问题”(recommendation problem)。计算机科学家认为如果将这种问题交给量子计算机,计算时间能够大大缩短,并且彰显出这种还未出世的计算机运算速度之快。但唐改变了这一假设。
今年春季刚从德克萨斯大学奥斯汀分校(the University of Texas,Austin)毕业,准备秋季攻读华盛顿大学(the University of Washington)博士的唐说:“以前推荐问题能很直接地证明量子计算能够提高运算速度,但现在不再是这样了。”
少年天才
2014年,14岁的唐跳级进入德克萨斯大学奥斯汀分校学习数学和计算机科学。2017年春季,他选了量子计算领域专家斯科特・阿伦森(Scott Aaronson)的量子信息课。阿伦森觉得唐很有天分,主动担任了唐的独立研究项目的指导教师:他给唐提供了一大堆研究备选题目,唐勉勉强强地选了其中的推荐问题。
唐表示:“我当时很犹豫,攻克推荐问题在我看来困难重重,可这已经是备选课题里最简单的一个了。”
推荐问题的初衷,是为用户推荐可能感兴趣的产品。就拿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岁,我整场讲座都没听出来,他演讲的时候显得很成熟。”目前,只要等到同行评议做完,这项算法就可以正式发表了。
唐的算法给了量子计算一记重拳?可能是也可能不是。唐改变了能表明量子计算优越性的一个最清晰、最直白的例子;但同时,唐的论文也能很好地证明,量子算法与经典算法之间是相互影响、相辅相成的。
阿伦森评价:“唐扼杀了(克里尼迪斯与普拉卡什的)量子计算优越性,但从另一个角度来看,正是他们的算法孕育出了唐的新算法。没有他们的量子算法,就不会有今天的经典算法。”
责任编辑:傅美萱
短网址: 版权所有,任何形式转载需本站授权许可。 严禁建立镜像网站.
【诚征荣誉会员】溪流能够汇成大海,小善可以成就大爱。我们向全球华人诚意征集万名荣誉会员:每位荣誉会员每年只需支付一份订阅费用,成为《看中国》网站的荣誉会员,就可以助力我们突破审查与封锁,向至少10000位中国大陆同胞奉上独立真实的关键资讯,在危难时刻向他们发出预警,救他们于大瘟疫与其它社会危难之中。
看完这篇文章您觉得
- 【贯明专栏】台湾最美的海湾 人间仙境七星潭(视频)
- 水果皇后——草莓(组图)
- 战火无情 造化弄人 那一代人的离合沧桑(组图)
- 千年前的人类抵御矮人“他”化为恶龙(图)
- 龙年龙抬头地龙翻身 世界已现动荡不祥之兆(组图)
- 世界上最贵的歌 4句歌词火遍全球(组图)
- 被中共刻意掩盖的两个华国锋的重大秘密(图)
- 深度:北京封杀范冰冰牵出娱乐黑势力(组图)
- 【中国时局】范冰冰“落难”内幕(图)
- 李鹏有二个特点 两记重拳要了江泽民的命(组图)
- 港媒:北戴河搞不定乱局 习近平党内打拖延战(图)
- 薄熙来谷开来各自淫乱 离婚后各说一句话狂笑(图)
- 看客:北戴河内讧 王沪宁替罪 黄海军演 老虎抱团(图)
- 中国债务和楼市泡沫结局大猜想……(组图)
- 中共肺炎(又称武汉肺炎)
- 拜登
- 病毒
- COVID-19
- 疫苗
- 川普
- 特朗普
- 国安法
- 贸易战
- 习近平
- 华为
- 台铁
- 三峡大坝
- 新疆棉
- 长江
- 洪水
- 袁弓夷
- 港版国安法
- 汉光演习
- 国民党
- 退党
- 弗洛伊德
- BLM
- 中共
- 阎丽梦
- 金正恩
- 王岐山
- 赖清德
- 孟晚舟
- 关税
- 边境墙
- 彭斯
- 美国
- 贸易谈判
- 刘鹤
- 王沪宁
- 江泽民
- 崔永元
- 中南海
- 内幕
- 中共
- 反送中
- 贪官
- 情妇
- 腐败
- 反腐
- 打虎
- 官场
- 看中国
- 一国两制
- 法广
- 社交媒体
- 往事微痕
- 出卖国土
- FB
- 六四
- 朝鲜
- 加拿大
- 脱欧
- 央行
- 债务
- 杠杆
- 美元
- 货币
- 人民币
- 欧元
- 日元
- 港币
- 房地产
- 楼市
- 财政
- 财富
- 中产
- 海参崴
- 台湾
- 蔡英文
- 北京
- 刘强东
- 大妈
- 房价
- 疫苗
- 非洲猪瘟
- 大陆
- P2P
- 雾霾
- 基因编辑
- 防火墙
- 维权
- 709律师
- 上访
- 法轮功
- 网络审查
- 活摘器官
- 江东六十四屯
- 唐努乌梁海
- 长白山
- 白龙尾岛
- 江心坡
- SARS
- 新疆劳改营
- 言论自由
- 女主播
- 央视
- 华人
- 移民
- 华人
- 留学
- 海关
- 遣返
- 签证
- 回国
- 入籍
- 绿卡
- 民生
- 海外
- 加拿大
- 澳洲
- 民国
- 桂军
- 抗战
- 孙中山
- 蒋介石
- 宋美龄
- 邓小平
- 林彪
- 刘少奇
- 中共
- 皇帝
- 诸葛亮
- 易经
- 幽默人生
- 智慧
- 感悟
- 手机
- 预言
- 奇闻
- UFO
- 外星人
- 寿命
- 文革
- 养生
- 紫凤
- 贯明
- 李道真
- 轶飞
- 李云飞
- 云中君
- 辛思
- 夏闻
- 时代漫谈
- 沧海
- 东方纵横
- 唐柏桥
- 王尚一
- 江枫
- 黄清
- 李唐风
- 园丁
- 今涛拍暗
- 李青城
- 秦就石
- 中经研
- 秦天靖
- 江浩
- Eagle Vision
- 李子壬
- 马新宇
- 马来启
- 紫君
- 秦山
- 陈破空
- 戴东尼
- 曹长青
- 邢仁涛
- 瑜正
- 简易
- 肖川
- 伍凡
- 顾言
- 归瑜
- 乙欣
- 陈泱潮
- 徐沛
- 若建国愿解除武装?哈马斯发布美国人质影片(图)
- 俗话“穷柴火 富水缸”跟穷富有啥关系?(图)
- 张学良对老蒋流泪忏悔说:我是幼稚愚鲁(组图)
- 习近平要拯救烂尾的西部大开发?(组图)
- “红杏出墙”居然被人们误读了千年(图)