量子计算机很神？18岁华裔少年用经典计算机算得一样快

 电商平台和视频网站该给用户推荐哪些产品和新片？这背后的算法，被称为“推荐问题”。推荐问题曾是量子计算“秒杀”经典计算机的最佳案例，然而，美国一位18岁华裔少年唐（Edwin Tang）近日提出了一种经典算法，其性能表现和量子计算相当。

　　这再次掀起了量子计算机到底能在多大程度上实现“量子加速”乃至“量子霸权”，超越经典计算机的讨论。

　　“这曾是量子加速的最好例证，但现在不成立了。”这位得州大学奥斯汀分校的毕业生告诉Quanta Magazine杂志。毕业几周后，唐在导师阿伦森（Scott Aaronson）的带领下，在加州大学伯克利分校的一个重磅量子计算会议上公布了这个成果。

华裔少年Edwin Tang “量子位”微信公众号 资料图给神童布置的作业

　　今年九月，唐将去华盛顿大学攻读博士学位。他的学习经历颇有神童色彩，14岁时就连跳三级，直接进入得州大学奥斯汀分校就读计算机和数学专业。

　　阿伦森是顶尖的量子计算专家，专注于测试“量子霸权”。这是一个由加州理工学院教授John Preskill在2012年提出的概念，即量子计算机在特定问题上表现超过世上最好的经典计算机。传统的计算机运用要么是“0”，要么是“1”的二进制比特进行计算，量子计算机使用的量子比特则可以是“0”或“1”。理论上，10个量子比特就可以同时计算2的10次方次。

　　他估计，“量子霸权”需要超过49个量子比特。

　　阿伦森在教授一堂量子信息课程时，很快就发掘了唐的天赋。他交给唐一些需要独立解决的问题，由他自己挑选。

　　唐不太情愿地选择了“推荐问题”：“这看起来是个难题，但这已经是他给我的问题最简单的一个了。”

　　一个视频网站拥有的数据，就是所有用户曾在上面浏览过的影片。据此，它要如何猜出你可能想要观看的新影片？

　　这些数据等于一个网格，横向是不同的电影，纵向是不同的用户，依据用户对该电影的喜好程度，可以在网格中填入相应的数值。

　　一个聪明的算法所要做的，就是快速而准确地找到其中的相似性，在空白的网格上填上数值。

　　2016 年，法国巴黎七大的Iordanis Kerenidis 和 新加坡南洋理工大学Anupam Prakash公布了一种“量子推荐算法”，比经典算法有了指数级的提高。这种算法并不企图填满整张空白网格，而是把用户简化成几个大类。

　　这个案例当时是激动人心的。此前虽有人利用量子算法获得了指数级的速度提升，但都是在很窄的应用问题上，更像是精致的小游戏。量子推荐算法则是在一个日常人都会接触到的领域证明了量子计算的价值。

　　不过，这两名计算机科学家只证明了量子推荐算法要比已知的任何经典推荐算法都要快得多，但却没有证明不存在更快的经典推荐算法。

　　阿伦森布置给唐的作业，就是要补上这个漏洞，证明没有比得上量子算法的经典推荐算法。

　　题目本身就错了

　　唐在研究的过程中，却越来越觉得这样的经典算法是存在的，他反复地自我质疑，因为阿伦森是领域里的权威。

　　最终，唐向阿伦森去信坦白了自己的想法。

　　在量子推荐算法的启发下，唐发现他们所用的量子采样技术完全可以在经典算法里复制。具体来讲，把用户数量、产品数取对数后，计算时间就会大大减少。

　　阿伦森反复验证了这个经典算法的正确性，确保唐不会出道即“出糗”。

　　最终，在加州的量子计算会议上，面对着一众领域内的“大佬”，唐连做了两场报告，并得到了普遍的认可，包括提出量子推荐算法的Kerenidis。他表示，唐的报告很成熟，他完全意识不到唐才18岁。

　　下一步，唐的论文将接受正规的同行评议，以争取正式发表。

　　“杀死”量子计算？

　　进入2018年，各大科技巨头竞争“量子霸权”的格局越发激烈。IBM完成了50比特原型机；谷歌发布了研制高质量72比特量子计算机的计划；微软则宣布在5年内造出拥有100个拓扑比特的量子计算机。

　　不过，这不是个简单的比谁比特数多的问题。一部分科学家对量子计算的前景仍持保守态度：在基础量子理论层面上，学界还没有解决量子比特的质量问题，即保持长时间、噪音少的量子纠缠。

　　在这个节骨眼上，唐的研究可以算是重创了量子计算，证伪了一个最能显示量子计算机优势的成果。但不能否认的是，唐的经典算法是在量子算法的基础上演化而来的，这点亮了两者之间的互动潜力。

　　正如阿伦森所说：“唐抹杀了Kerenidis 和Prakash的量子加速，但换个角度，唐的巨大成就是建立在他们的基础上的。要不是先有了他们的量子算法，唐永远做不出他的经典算法。”

　　在其他问题上，我们也完全可以期待由量子算法启发出更多更好的经典算法。这或许是发展量子计算的“曲线救国”方案：就算短时间内造不出量子计算机，量子计算的思路本身就能创造价值。