18岁华裔少年挑战“量子计算优势”
作者：徐令予
量子计算的一个重要成果被一个18岁少年推翻。
自古英雄出少年！18岁的美国德克萨斯州华裔少年Ewin Tang的论文证明，经典计算机几乎可以像量子计算机一样快速地解决“推荐问题”。量子优势（又称量子霸权）的一个最佳案例如今却被拉下了神坛[1]。
推荐算法是计算机领域中的一种重要算法，它可以用来为客户可能喜欢的产品和服务提供建议。例如影视网站从海量数据中获取到用户数据，根据用户过去喜欢或搜索过的影视内容，为用户推荐与之相似的影视作品，而内容相似性的度量，是算法运用的关键。
我们可以将这些数据视为一个矩阵，横向代表电影，竖向代表用户，而网格中各点是某用户对某电影的喜好程度的量化值。一个好的算法可以通过快速准确地识别电影和用户之间的相似性，并填充矩阵中的空白以生成推荐。
2016年，计算机科学家Iordanis Kerenidis和Anupam Prakash发布了一种量子算法，该算法解决推荐问题的速度比任何已知经典算法要快得多。他们通过简化问题来实现量子加速：不是填写整个矩阵并确定推荐单一最佳产品，而是先将用户根据他们的喜好分类为人数不多的小组，并对现有数据进行抽样，从而生成足够好的建议。
在这之前，量子计算机解决某些问题比经典计算机有指数式加速优势的例子已经存在，但这些问题都比较专门和单一，量子计算机的优势有很大局限性。 Kerenidis和Prakash的研究结果令人兴奋，因为这是一种具有普遍意义的算法，而且又有着人们非常关心的实际应用价值。
“据我所知，它是机器学习和大数据中的一个好例子，我们展示了量子计算机可以做一些我们仍然不知道如何用经典办法解决的事情。”巴黎计算机基础科学研究所的科学家Kerenidis说。
一个18岁的少年有何能耐改变量子计算的历程？希望的种子埋下于四年之前。2014年，14岁的Ewin连跳几级后入读于德州大学奥斯汀分校，主修数学和计算机科学。2017年春天，Ewin选修了斯科特·亚伦森（Scott Aaronson）教授的量子信息课程，亚伦森教授是量子计算专家。亚伦森教授慧眼识英雄，很快发觉Ewin是匹千里马，于是主动提出愿意为Ewin同学担任独立研究项目的顾问。
亚伦森教授给了Ewin一些可供选择的课题，这其中就包括了“推荐问题”，Ewin选择了它，但有点不情不愿。“我有些犹豫不决，因为当我初看时，这似乎是一个难题，但这又是他给我的问题中间最简单的一个。”Ewin说。
2017年秋季开始，Ewin全身投入工作，打算将“推荐问题”作为自己的大学毕业论文。亚伦森教授和Ewin的原始想法是：通过证明不存在快速的经典推荐算法，从而确认Kerenidis和Prakash的量子加速算法的真实价值。几个月来，Ewin一直拚着命想证明关于“推荐问题”不存在任何快速经典算法。“山穷水尽疑无路，柳暗花明又一村。”随着时间的推移，Ewin开始看到了构建快速经典算法的一线希望。
“我开始相信有一种快速的经典算法，但我无法向自己证明这一点，因为亚伦森教授似乎认为这不可能，而他是权威，”Ewin说。随着毕业论文的最后期限接近，Ewin写信把自己的怀疑告诉了教授。
在今年整个春天里，Ewin把自己的想法变成严格的算法，并与亚伦森教授合作把算法中的一些步骤作出澄清和证明。Ewin发现的快速经典算法直接受到Kerenidis和Prakash两年前发现的快速量子算法的启发。Ewin发觉他俩的算法中使用的那种采样技术也可以在经典环境中复制。与Kerenidis和Prakash的算法一样，Ewin的经典算法在多重对数时间内运行，这意味着计算时间与数据量（例如数据集中的用户和产品的数量）的关系是对数函数，它比任何先前已知的经典算法要快指数倍，与量子算法速度对等。
算法完成后，亚伦森教授希望在公开发布之前确定它是正确的，他真心希望自己的爱徒的学术生涯有一个好的开端。
亚伦森教授对Ewin同学的培养和提携真可谓不遗余力，为此他作出了一个重要的决定。6月份，亚伦森教授出席在加州大学伯克利分校举行的量子计算研讨会。该领域的许多大腕都将出现在那里，其中包括了Kerenidis和Prakash。在正式会议结束后的几天里，由亚伦森教授出面邀请Ewin同学来伯克利大学非正式地介绍他的新算法。
在6月18日和19日的早晨，Ewin做了两次讲座，同时接受观众提问。四小时的讲座结束时，人们已经有了共识：Ewin的创新经典算法似乎是正确的。然而，会议室的许多听众都没有意识到这位演讲者的真实年龄。 “我不知道Tang先生是18岁，从他的演讲中完全感觉不到这一点。对我来说，他就是一个非常成熟的演讲者。”这位量子计算专家Kerenidis如是说。目前，Ewin的论文正式发布之前正在面临同行的评审。
下面谈谈我的几点不成熟的看法。
1）Ewin同学的研究结果给量子计算投下了阴影。他的结果消除了量子优势中最清晰、最有说服力的一个例证。不过我们也应同时认识到，Ewin同学的论文进一步证明了量子算法和经典算法研究之间存在富有成效的相互作用。
正如亚伦森教授所说：“Ewin正在消除[Kerenidis和Prakash的]量子加速，但在另一种意义上，Ewin所做的经典算法改进正是在他俩的工作基础上进行的。没有他们的量子算法，Ewin可能想不出这种新的经典算法。”
所以应该进一步加强对量子计算的基础科学研究。研制量子计算机不是为了取代现有的经典电子计算机，而是为了促进、支持和辅助经典电子计算机。
2）Ewin Tang的论文标题是：推荐系统的量子启发经典算法。他的算法是受“量子启发的”，所以他能够看到量子算法技巧实际上并不真正需要量子计算机，他可以在经典计算机上复制那些“依赖于量子计算机的聪明想法”。有可能长期以来我们扭曲和放大了量子计算机和经典计算机之间的差异。
他的这个发现或许具有更普遍的意义。当然也不是从Tang的结果中直接得到更多的经典算法去代替量子算法，但另一方面，他确实为挑战更多的量子算法提供了新的思路。不过这仅是我的感觉。
3）必须认识到目前所有的量子算法仅仅停留在算法的理论研究阶段，说白了就是纸上谈兵，最多也只能在经典的电子计算机上做做模拟。可以实际运用这些量子算法的量子计算机距离我们依旧十分的遥远。
量子计算机目前面临的不止只是工程困境，现在有些科学家甚至认为从原理层面上来看，建造用来运行许多量子算法的量子计算机就是不可能完成的任务。2018年初的量子杂志连载有三篇质疑量子计算机可行性的相关报导，其中的一篇介绍了以色列数学家Gil Kalai和他的研究工作。
Gil Kalai和其他专家合作发表了一篇论文[2]。Kalai的文章是关于Boson sampling的噪声分析，结论是Boson sampling对噪声相当敏感，在容错量子计算机中很难实现明显的量子加速。量子态的退相干现象实质上是有关噪声的物理过程，Kalai通过数学建模和分析得出两条结论：1）把物理过程的噪声抑制趋向于零的代价是无法承受的，换言之，要得到精确稳定的逻辑量子比特，需要的物理量子比特数会有指数型的增加；2）过程的噪声减少是以系统灵敏度减少为代价的，就是说，量子纠错会限制量子态承载信息的丰富多样性。总而言之，我们不能既要量子态的丰富多样，又要量子态的可控和稳定。Gil Kalai的观点有待进一步的实验验证，但是他的研究至少让我们进一步认识到，研制实用的量子计算机的道路十分艰难遥远。
可实用的量子计算机还在未定之天，而必须运行在量子计算机上的一个重要的量子算法对经典电子计算机又不具备任何速度优势。由此可知，在可预见的未来量子计算的实用意义不宜过分夸大，用量子计算机的威胁作为现阶段工程建设的决策依据更不合适。
4）Ewin Tang的故事再一次告诉我们：“世有伯乐，然后有千里马。千里马常有，而伯乐不常有。故虽有名马，祇辱于奴隶人之手，骈死于槽枥之间，不以千里称也。”
[1]https://arxiv.org/abs/1807.04271
[2]“Gaussian Noise Sensitivity and BosonSampling” https://arxiv.org/abs/1409.3093
