|
“推荐问题”最实际的例子之一就是亚马逊和 Netflix 这类商家如何判断客户可能需要哪些商品。计算机学家一直都将“能快速解决此类问题”看作是量子计算概念的标志，也是验证量子计算方法是否可行的经典手段。然而，Ewin Tang 的这篇论文横空出世，打破了人们对于用“推荐问题”验证量子计算可行性和优越性的执着。
论文作者，Ewin Tang 说：“这曾是最能体现量子计算优势的方法之一，但现已不复存在。”Ewin Tang 于今年春季毕业于德克萨斯大学奥斯汀分校，并将于秋季开始在华盛顿大学攻读博士学位。
2014 年，14 岁的 Ewin Tang 在跳级后就读于德克萨斯大学奥斯汀分校，主修数学和计算机科学。2017 年春，Tang 选了一门量子计算方向，由量子计算著名研究员 Scott Aaronson 教授所教授的量子信息课程。Aaronson 认为 Tang 是一位很有天赋的学生，给 Tang 提供了一个独立研究项目机会，并亲自担当项目顾问。Aaronson 给 Tang 提供的研究机会有包括“推荐问题”在内的许多课题可选，而 Tang 当时则有点不情愿地选择了“推荐问题”课题。
图｜Ewin Tang Tang 说：“我当时犹豫不决，因为它看上去很难，但这是所有课题中最简单的一个。”
“推荐问题”旨在为用户提供产品建议。比如 Netflix，它知道你看过哪部电影，它也知道其他数百万用户所观看过的内容，而 Netflix 需要根据这些信息为你做出影视推荐。
我们可以将这些数据想成一种信息量巨大的表格，表格的列为各部电影，表格的行为每个具体用户，而表格中每个数字格的值则用于量化用户对于某部电影的喜好程度。此时，一个好的算法可以通过快速准确地识别电影和用户之间的相似性来填充表格中的空白格，进而生成推荐。
2016 年，计算机学家 Iordanis Kerenidis 和 Anupam Prakash 联手发布了一种量子算法，该算法能以比任何已知的经典算法都快的速度解决“推荐问题”。具体来说，该算法通过简化问题实现这一“量子优势”：不用完成整个表格，而是将用户进行分类（如某一用户喜欢好莱坞大片还是小众电影），再对现有数据进行抽样，然后生成建议。
在 Kerenidis 和 Prakash 的开发这套算法时，还没有几个人能实际验证“量子优势”的可行方法，大多数方法都有着很大的局限性。当时 Kerenidis 和 Prakash 的研究结果令人兴奋，因为它提供了一个可实际验证“量子优势”的可靠方法。
巴黎计算机研究所科学家，Kerenidis 说：“据我所知，当时这是机器学习和大数据领域中的首个可靠方法，展示了量子计算机可以解决我们从经典计算上无从下手的一些问题。”
虽然 Kerenidis 和 Prakash 的研究证明了量子计算机能更快地解决“推荐问题”，但它并不能证明经典算法达不到这样的速度。而这也正是 Tang 所选择的课题——证明没有快速的经典推荐算法，从而验证 Kerenidis 和 Prakash 所展示的量子优势。
Tang 于 2017 年秋季开始研究工作，打算将“推荐问题”课题研究写成一篇毕业论文。几个月来，Tang 绞尽脑汁地想要证明快速经典算法并不存在，但随着时间的推移，Tang 发现这种算法或许是存在的。
Tang 说：“当时我开始相信快速经典算法的存在，但无法向自己证明这一点，因为当时包括 Aaronson 在内的权威人士都认为这不太可能。”
最后，随着论文的期限临近，Tang 写信给 Aaronson 阐述了他的观点，Aaronson 说：“Tang 当时写信给我，说他认为有一种可能存在的快速经典算法。”
于是，在今年春天，Tang 与 Aaronson 合作在论文中阐明了证明快速经典算法存在过程中的关键步骤。Tang 所发现的快速经典算法可以说是直接受到了 Kerenidis 和 Prakash 两年前发现的快速量子算法启发。Tang 表示，Kerenidis 和 Prakash 所使用的量子采样方法可以在经典环境中予以复制。与 Kerenidis 和 Prakash 的算法一样，Tang 的算法在多对数时间（polylogarithmic time）内完成运算，与量子算法的速度相当，比任何此前已知的经典算法都快。
Aaronson 当时希望在 Tang 公开发表算法前确认一遍它是否正确。Aaronson 说：“我现在仍然对此感到紧张，因为如果 Tang 所发表的论文中存在错误，他的学术生涯也会受到影响。”
Aaronson 于 6 月参加了一个加州大学伯克利分校的量子计算研讨会。包括 Kerenidis 和 Prakash 在内，该领域的许多大腕悉数出席。在正式会议结束后的几天里，Aaronson 邀请 Tang 来伯克利简单地介绍一下他的快速经典算法。
在 6 月 18 日和 19 日的早晨，Tang 在伯克利做了两次讲座，并接受了提问。在四个小时的讲座结束后，会场中的共识是 Tang 的经典算法似乎是正确的。然而，房间里的许多人都没有意识到演讲者的年龄。Kerenidis 说：“我不知道 Ewin 只有 18 岁。对我来说，Ewin 只是一个正在进行成熟的谈话的成年人”。
目前，该算法正在经同行评审准备正式发表。
Tang 的发现为量子计算与经典计算间的相互影响提供了理论依据。但这并不意味着量子计算与经典计算相比没有优势。有网友对此评论“量子计算机就像是现代版的‘炼金术’”。诚然，至今我们仍未造出任何与传统计算机有区别的所谓量子计算机，但就像炼金术启蒙了化学领域，对量子计算的研究也将引导未来更多的发现。
-End- |
|
|
