18岁的尤文·谭（Yuvin Tan）证明，经典计算机可以几乎与量子计算机一样快地解决“推荐问题”。 该结果使计算的量子加速度的最佳示例之一无效。
得克萨斯州的一位青少年围攻了量子计算的发展。 在本月在互联网上发表的一篇文章中
，年仅18岁的Yuvin Tan证明了普通计算机可以以
与量子计算机
相当的速度解决重要的计算问题。
在最实际的形式中，推荐问题与诸如Amazon和Netflix之类的服务如何确定您可能喜欢的产品有关。 计算机科学家认为这
是在量子计算机上以指数方式更快解决任务
的最好例子之一 ，它强调了这些未来派机器的潜在
功能 。 现在谭驳斥了这一观点。
Tang说：“这是量子加速的定义性例子之一，现在已经消失了。” Tang于春季从德克萨斯大学奥斯汀分校毕业，并开始在华盛顿大学攻读博士学位。
2014年，Tang在14岁那年升入4、5和6年级，进入德克萨斯大学学习数学和计算机科学。 在2017年春季，Tan参加了量子信息课程，由量子计算领域的著名研究员
Scott Aaronson教授。 亚伦森（Aaronson）认识了谭（Tan）一位非凡的才华学生，并邀请他成为独立研究项目的顾问。 亚伦森给了谭几项任务供您选择，其中包括建议问题。 Tan不情愿地选择了她。
谭说：“我犹豫了，因为它看起来相当复杂，但这是他向我提出的所有任务中最简单的一项。”
推荐的目的是为用户可能喜欢的产品提供推荐。 考虑Netflix。 他知道你看了什么电影。 他知道数百万用户观看了什么。 有了这些信息，是否有可能找出您想要进一步查找的内容？
该数据可以以巨大的网格或矩阵的形式表示，上面列出了所有电影，侧面是所有用户，并且内部有值来衡量每个用户对每部电影的喜欢程度。 一个好的算法将产生推荐列表，快速准确地检测电影和用户之间的相似性，并填充矩阵的空白单元格。
2016年，计算机科学家
Iordanis Kerenidis和
Anupam Prakash发布了一种
量子算法 ，该
量子算法比任何已知的经典算法都以指数方式更快地解决了推荐问题。 他们特别是由于问题的简化而获得了这样的量子加速度。 他们没有填写整个矩阵并确定要推荐的唯一最佳产品，而是想出一种将用户划分为少量类别的方法-他们喜欢大片还是独立电影院？ -处理现有数据，以给出非常好的建议。
到Kerenidis和Prakash的工作出现时，量子计算机本应比传统计算机以指数速度更快解决问题的例子很少。 在大多数情况下，这些任务是专门的-狭义的问题，旨在利用量子计算机的优势而设计（包括我们已经写过的“
相关性 ”问题）。 Kerenidis和Prakash的工作很有趣，因为它突出了一个对人类很重要的实际问题，量子计算机已取代了经典计算机。
“从我的角度来看，这是机器学习和大数据处理的第一个例子，其中我们证明了量子计算机可以做一些我们尚不知道如何使用经典方法来做的事情，”研究专家Kerenidis说。巴黎计算机科学研究所的计算机科学。
Kerenidis和Prakash证明了量子计算机比任何已知算法都能以指数方式更快地解决建议问题，但他们尚未证明没有快速经典算法。 因此，当Aaronson在2017年开始与Tan合作时，他提出了一项任务-证明不存在快速经典算法，从而确认了Kerenidis和Prakash的量子加速度。
“在我看来，这将是我们准备完成该故事的重要点，”亚伦森说，当时他认为快速经典算法不存在。
Tang于2017年秋天开始工作，希望建议的任务将成为他的论文的主题。 几个月来，Tan试图证明不可能存在经典算法。 时间过去了，Tan开始认为也许确实存在这样的算法。
谭说：“我开始相信经典算法的存在，但我无法相信这一点，因为斯科特（Scott）认为他不存在，他是我的权威。”
最终，当论文的截止日期已经用尽时，Tan写了一封信给Aaronson，他在信中承认了自己的怀疑。 “ Tan基本上向我写了以下内容：我认为存在一种快速的经典算法，” Aaronson说。
整个春季，Tang写下了结果，并与Aaronson一起阐明了证明的一些步骤。 由Tan发明的快速经典算法的灵感来自两年前Kerenidis和Prakash发现的快速量子算法。 Tan证明了他们算法中使用的量子采样可以在经典条件下重现。 像Kerenidis和Prakash算法一样，Tan算法是在多对数时间中执行的-也就是说，计算时间是通过诸如用户和产品数量之类的参数的对数来估计的-并且它比其他任何已知的经典算法都快得多。
Tan完成该算法后，Aaronson希望在发布之前确保它是正确的。 阿伦森说：“我仍然担心，如果在谭发表作品后，事实证明这是不正确的，那么谭职业上的第一份大工作将变成零头。”
亚伦森计划于6月参加在加州大学伯克利分校举行的量子计算研讨会。 该地区的名人聚集在此，包括Kerenidis和Prakash。 Aaronson邀请Than和他一起去伯克利，以便在会议正式会议之后非正式地介绍他的算法。
Tan于18日上午和6月19日上午进行了两次演讲，回答了观众的提问。 四小时后，人们达成了共识：经典的Tan算法看起来像是正确的算法。 在场的许多人不了解Tan是如何年轻的。 “我不知道尤文18岁，从对话的结果看，我当然不这么认为。 在我看来，朱文是一个成年男子，正在谈话。 现在，该算法将在发布之前进行正式的同行评审。
对于量子计算，Tan结果是倒退的一步。 还是不行 Tang消除了量子优势最可理解和最好的例子之一。 同时，Tan的工作又证明了经典算法和量子算法
之间存在
卓有成效的相互作用 。
“ Tang消除了Kerenidis和Prakash的量子加速，但是从另一个意义上讲，Tang做出了巨大的贡献，并基于他们的工作。 如果Tang没有发表自己的研究成果，Tang就永远不会提出他的经典算法。” Aaronson说。