以下内容是 google 对[toggle=off]<br><br>[title]原文[/title]<br><br>[content]https://www.quantamagazine.org/teenager-finds-classical-alternative-to-quantum-recommendation-algorithm-20180731/<br><br>Major Quantum Computing Advance Made Obsolete by Teenager<br><br>A teenager from Texas has taken quantum computing down a notch. In a paper posted online earlier this month, 18-year-old Ewin Tang proved that ordinary computers can solve an important computing problem with performance potentially comparable to that of a quantum computer.<br><br>In its most practical form, the “recommendation problem” relates to how services like Amazon and Netflix determine which products you might like to try. Computer scientists had considered it to be one of the best examples of a problem that’s exponentially faster to solve on quantum computers — making it an important validation of the power of these futuristic machines. Now Tang has stripped that validation away.<br><br>“This was one of the most definitive examples of a quantum speedup, and it’s no longer there,” said Tang, who graduated from the University of Texas, Austin, in spring and will begin a Ph.D. at the University of Washington in the fall.<br><br>In 2014, at age 14 and after skipping the fourth through sixth grades, Tang enrolled at UT Austin and majored in mathematics and computer science. In the spring of 2017 Tang took a class on quantum information taught by Scott Aaronson, a prominent researcher in quantum computing. Aaronson recognized Tang as an unusually talented student and offered himself as adviser on an independent research project. Aaronson gave Tang a handful of problems to choose from, including the recommendation problem. Tang chose it somewhat reluctantly.<br><br>“I was hesitant because it seemed like a hard problem when I looked at it, but it was the easiest of the problems he gave me,” Tang said.<br><br>The recommendation problem is designed to give a recommendation for products that users will like. Consider the case of Netflix. It knows what films you’ve watched. It knows what all of its other millions of users have watched. Given this information, what are you likely to want to watch next?<br><br>You can think of this data as being arranged in a giant grid, or matrix, with movies listed across the top, users listed down the side, and values at points in the grid quantifying whether, or to what extent, each user likes each film. A good algorithm would generate recommendations by quickly and accurately recognizing similarities between movies and users and filling in the blanks in the matrix.<br><br>In 2016 the computer scientists Iordanis Kerenidis and Anupam Prakash published a quantum algorithm that solved the recommendation problem exponentially faster than any known classical algorithm. They achieved this quantum speedup in part by simplifying the problem: Instead of filling out the entire matrix and identifying the single best product to recommend, they developed a way of sorting users into a small number of categories — do they like blockbusters or indie films? — and sampling the existing data in order to generate a recommendation that was simply good enough.<br><br>At the time of Kerenidis and Prakash’s work, there were only a few examples of problems that quantum computers seemed to be able to solve exponentially faster than classical computers. Most of those examples were specialized — they were narrow problems designed to play to the strengths of quantum computers (these include the “forrelation” problem Quanta covered earlier this year). Kerenidis and Prakash’s result was exciting because it provided a real-world problem people cared about where quantum computers outperformed classical ones.<br><br>“To my sense it was one of the first examples in machine learning and big data where we showed quantum computers can do something that we still don’t know how to do classically,” said Kerenidis, a computer scientist at the Research Institute on the Foundations of Computer Science in Paris.<br><br>Kerenidis and Prakash proved that a quantum computer could solve the recommendation problem exponentially faster than any known algorithm, but they didn’t prove that a fast classical algorithm couldn’t exist. So when Aaronson began working with Tang in 2017, that was the question he posed — prove there is no fast classical recommendation algorithm, and thereby confirm Kerenidis and Prakash’s quantum speedup is real.<br><br>“That seemed to me like an important ‘t’ to cross to complete this story,” said Aaronson, who believed at the time that no fast classical algorithm existed.<br><br>Tang set to work in the fall of 2017, intending for the recommendation problem to serve as a senior thesis. For several months Tang struggled to prove that a fast classical algorithm was impossible. As time went on, Tang started to think that maybe such an algorithm was possible after all.<br><br>“I started believing there is a fast classical algorithm, but I couldn’t really prove it to myself because Scott seemed to think there wasn’t one, and he was the authority,” Tang said.<br><br>Finally, with the senior thesis deadline bearing down, Tang wrote to Aaronson and admitted a growing suspicion: “Tang wrote to me saying, actually, ‘I think there is a fast classical algorithm,’” Aaronson said.<br><br>Throughout the spring Tang wrote up the results and worked with Aaronson to clarify some steps in the proof. The fast classical algorithm Tang found was directly inspired by the fast quantum algorithm Kerenidis and Prakash had found two years earlier. Tang showed that the kind of quantum sampling techniques they used in their algorithm could be replicated in a classical setting. Like Kerenidis and Prakash’s algorithm, Tang’s algorithm ran in polylogarithmic time — meaning the computational time scaled with the logarithm of characteristics like the number of users and products in the data set — and was exponentially faster than any previously known classical algorithm.<br><br>Once Tang had completed the algorithm, Aaronson wanted to be sure it was correct before releasing it publicly. “I was still nervous that once Tang put the paper online, if it’s wrong, the first big paper of [Tang’s] career would go splat,” Aaronson said.<br><br>Related:<br><br>Finally, a Problem That Only Quantum Computers Will Ever Be Able to Solve<br><br>The Era of Quantum Computing Is Here. Outlook: Cloudy<br><br>Computing’s Search for Quantum Questions<br><br>Aaronson had been planning to attend a quantum computing workshop at the University of California, Berkeley, in June. Many of the biggest names in the field were going to be there, including Kerenidis and Prakash. Aaronson invited Tang to come out to Berkeley to informally present his algorithm in the days after the official conference ended.<br><br>On the mornings of June 18 and 19 Tang gave two lectures while fielding questions from the audience. By the end of four hours, a consensus emerged: Tang’s classical algorithm seemed correct. What many people in the room didn’t realize, however, was just how young the speaker was. “I did not know Ewin was 18, and I certainly did not get that from the talk. To me [Ewin] was someone who was giving a very mature talk,” Kerenidis said. The algorithm now faces a formal peer review before publication.<br><br>For quantum computing, Tang’s result is a setback. Or not. Tang has eliminated one of the clearest, best examples of a quantum advantage. At the same time, Tang’s paper is further evidence of the fruitful interplay between the study of quantum and classical algorithms.<br><br>“Tang is killing [Kerenidis and Prakash’s] quantum speedup, but then in another sense Tang is giving a big improvement and building on what they did. Tang never would have come up with this classical algorithm but for their quantum algorithm,” Aaronson said.<br><br>[/content]<br><br>[/toggle]的翻译：<br><br>[hr]<br><br>来自德克萨斯州的一名青少年将量子计算提升了一个档在本月早些时候在网上发表的一篇论文中，18岁的Ewin Tang证明普通计算机可以解决一个重要的计算问题，其性能可能与量子计算机相当。<br><br>在最实际的形式中，“推荐问题”涉及亚马逊和Netflix等服务如何确定您可能想要尝试的产品。计算机科学家认为它是量子计算机上解决速度快得多的问题的最佳例子之一 - 使其成为这些未来机器功能的重要验证。现在唐已经剥夺了验证。<br><br>“这是量子加速的最明确的例子之一，而且已经不存在了，”唐说，他在春季毕业于德克萨斯大学奥斯汀分校，并将开始攻读博士学位。秋天在华盛顿大学。<br><br>2014年，在14岁时，在跳过四年级到六年级之后，唐先生就读于UT奥斯汀，主修数学和计算机科学。 2017年春天，唐在量子计算方面的着名研究员斯科特·亚伦森（Scott Aaronson）教授量子信息课程。 Aaronson认为唐是一位非常有才华的学生，并且自称是一个独立研究项目的顾问。 Aaronson给了Tang一些可供选择的问题，包括推荐问题。唐有点不情愿地选择了它。<br><br>“我犹豫不决，因为当我看着它时，这似乎是一个难题，但这是他给我的最简单的问题，”唐说。<br><br>推荐问题旨在为用户喜欢的产品提供建议。考虑一下Netflix的情况。它知道你看过哪部电影。它知道其他数百万用户所观看的内容。根据这些信息，您接下来可能想要观看什么？<br><br>您可以将这些数据视为以巨大网格或矩阵排列，顶部列出的电影，侧面列出的用户，以及网格中各点的值，用于量化每个用户是否喜欢每部电影的程度。一个好的算法可以通过快速准确地识别电影和用户之间的相似性并填充矩阵中的空白来生成推荐。<br><br>2016年，计算机科学家Iordanis Kerenidis和Anupam Prakash发布了一种量子算法，该算法以比任何已知经典算法更快的速度解决推荐问题。他们通过简化问题来实现这一量子加速：不是填写整个矩阵并确定推荐的单一最佳产品，而是开发了一种将用户分类为少数类别的方式 - 他们喜欢大片还是独立电影？ - 并对现有数据进行抽样，以便生成足够好的建议。<br><br>在Kerenidis和Prakash的工作时，量子计算机似乎能够以比经典计算机指数更快的速度解决问题的例子。大多数这些例子都是专门的 - 它们是旨在发挥量子计算机优势的狭隘问题（包括今年早些时候广达所涵盖的“相关”问题）。 Kerenidis和Prakash的结果令人兴奋，因为它提供了人们关心量子计算机优于经典计算机的真实问题。<br><br>“据我所知，它是机器学习和大数据中的第一个例子，我们展示量子计算机可以做一些我们仍然不知道如何做经典的事情，”研究所的计算机科学家Kerenidis说。巴黎计算机科学基础。<br><br>Kerenidis和Prakash证明了量子计算机能够比任何已知算法以指数方式更快地解决推荐问题，但它们并不能证明快速经典算法不存在。因此，当Aaronson在2017年开始与Tang合作时，这就是他提出的问题 - 证明没有快速的经典推荐算法，从而确认Kerenidis和Prakash的量子加速是真实的。<br><br>“在我看来，这似乎是一个重要的't'来完成这个故事，”Aaronson说，他当时认为没有快速的经典算法存在。<br><br>3191/5000<br><br>Tang于2017年秋季开始工作，打算将推荐问题作为高级论文。几个月来，唐挣扎着证明快速的经典算法是不可能的。随着时间的推移，唐开始认为也许这样的算法是可能的。<br><br>“我开始相信有一种快速的经典算法，但我无法向自己证明这一点，因为斯科特似乎认为没有一种，而且他是权威，”唐说。<br><br>最后，随着高级论文的最后期限结束，唐写信给Aaronson并承认了一个越来越多的怀疑：“唐写信给我说，实际上，'我认为有一种快速的经典算法'，”Aaronson说。<br><br>在整个春天，唐写了结果并与Aaronson合作澄清证明中的一些步骤。 Tang发现的快速经典算法直接受到Kerenidis和Prakash两年前发现的快速量子算法的启发。唐表明，他们在算法中使用的那种量子采样技术可以在经典环境中复制。与Kerenidis和Prakash的算法一样，Tang的算法在多对数时间内运行 - 意味着计算时间与特征的对数（如数据集中的用户和产品的数量）进行缩放 - 并且比任何先前已知的经典算法指数化得快。<br><br>一旦Tang完成了算法，Aaronson希望在公开发布之前确定它是正确的。 “我仍然感到紧张，一旦唐在网上发表论文，如果这是错的，那么[唐'的职业生涯的第一篇大论文就会贬低，”亚伦森说。<br><br>Aaronson计划于6月份参加加州大学伯克利分校的量子计算研讨会。该领域的许多大腕都将出现在那里，包括Kerenidis和Prakash。在官方会议结束后的几天里，Aaronson邀请Tang来伯克利非正式地介绍他的算法。<br><br>在6月18日和19日的早晨，唐先生做了两次讲座，同时向观众提出了问题。到四小时结束时，出现了一个共识：唐的经典算法似乎是正确的。然而，房间里的许多人都没有意识到演讲者的年龄。 “我不知道Ewin是18岁，我当然没有从谈话中得到这个。对我来说，[Ewin]是一个正在进行非常成熟的谈话的人，“Kerenidis说。该算法现在在发布之前面临正式的同行评审。<br><br>对于量子计算，唐的结果是一个挫折。或不。唐已经消除了量子优势中最清晰，最好的例子之一。与此同时，唐的论文进一步证明了量子算法和经典算法研究之间富有成效的相互作用。<br><br>“唐正在杀死[Kerenidis和Prakash的]量子加速，但在另一种意义上，唐正在给予一个很大的改进，并在他们所做的基础上进行。唐从未想出这种经典算法，但对于他们的量子算法，“Aaronson说。