18岁少年提出在性能上能与量子推荐算法相比拟的经典替代

18 岁的 Ewin Tang 上个月在预印本网站 arXiv.org 上发表论文,提出了在性能上能与量子推荐算法相比拟的经典替代。Tang 在 14 岁时跳了几级就读得州奥斯汀,主修数学和计算机科学,2017 年修了知名量子计算学家 Scott Aaronson 教的量子信息课程。

ewin.png

Aaronson 认识到 Tang 极具天赋,提议在一个独立研究项目上当他的导师。Aaronson 给了他多个问题去选择,Tang 最后选择了推荐问题。以流媒体网站 Netflix 为例,推荐问题就是在它了解了你已观看过的电影以及其他数百万人的观影历史之后,向你推荐你接下来想看的电影。你可以将这些数据排列到一个巨大的网格或矩阵里,顶部列出不同的电影,侧面是不同用户,网络中的交叉点根据喜好程度进行量化。推荐算法通过快速精确的识别其中的相似之处来产生推荐。2016 年,计算机科学家 Iordanis Kerenidis 和 Anupam Prakash 在预印本网站发表了量子推荐算法的论文,其运算速度比现有的任何经典推荐释放要高出几个数量级。他们证明了量子计算机能更快的解决推荐问题,但并没有证明不存在更快的经典推荐算法。因此 Aaronson 让 Tang 去证明不存在更快的经典推荐算法,Aaronson 相信量子推荐算法比经典算法要快得多。但 Tang 在研究中发现,更快的经典推荐算法是可能的。他发现的经典算法受到了量子推荐算法的启发。他在伯克利的研讨会上介绍了他的算法,与会者就包括了量子推荐算法的作者。与会者的共识是他的算法应该是正确的,量子计算的又一个优势被终止了。但这项研究也证明量子计算和经典计算可以互相促进。Aaronson 也在个人博客上谈论了 Tang 的工作