文章摘要
一位18岁的德克萨斯少年Ewin Tang证明，普通计算机可以解决一个重要的计算问题，其性能可能与量子计算机相当。这一发现使得原本被认为是量子计算机优势的“推荐问题”不再成为量子计算的独特优势，削弱了量子计算机在这一领域的验证。
文章总结
标题：青少年发现经典算法替代量子推荐算法，量子计算重大进展被颠覆
主要内容：
来自德克萨斯州的18岁少年Ewin Tang在一篇在线发布的论文中证明，普通计算机能够解决一个重要的计算问题，其性能可能与量子计算机相当。这一发现对量子计算领域产生了重大影响。
“推荐问题”是像亚马逊和Netflix这样的服务用来确定用户可能喜欢哪些产品的核心问题。此前，计算机科学家认为这是量子计算机能够指数级加速解决的典型问题之一，因此被视为量子计算机能力的重要验证。然而，Tang的研究打破了这一观点。
Tang在2017年春季参加了量子计算领域的知名研究者Scott Aaronson教授的量子信息课程。Aaronson认为Tang是一位异常有天赋的学生，并邀请他参与一个独立研究项目。在Aaronson提供的几个问题中，Tang选择了推荐问题，尽管他最初对此有些犹豫。
推荐问题的核心是通过分析用户和产品之间的相似性，快速准确地生成推荐。2016年，计算机科学家Iordanis Kerenidis和Anupam Prakash发表了一种量子算法，能够以指数级速度解决推荐问题。他们的方法通过简化问题，将用户分类并采样现有数据来生成推荐。
然而，Kerenidis和Prakash并未证明不存在快速的经典算法。因此，当Aaronson与Tang合作时，他提出的问题是：证明不存在快速的经典推荐算法，从而确认Kerenidis和Prakash的量子加速是真实的。
Tang在2017年秋季开始研究，最初试图证明快速经典算法的不可能性。但随着时间推移，他开始怀疑可能存在这样的算法。最终，Tang发现了一种经典算法，其灵感直接来源于Kerenidis和Prakash的量子算法。Tang的算法在多项式对数时间内运行，比任何已知的经典算法都要快。
Tang的算法在加州大学伯克利分校的一次量子计算研讨会上得到了初步认可。尽管许多人并未意识到演讲者年仅18岁，但与会者一致认为Tang的算法似乎是正确的。
对于量子计算领域来说，Tang的研究结果是一个挫折，但也展示了量子算法与经典算法研究之间的有益互动。Aaronson指出，Tang的研究虽然颠覆了Kerenidis和Prakash的量子加速，但也在此基础上做出了重大改进。
总结： Ewin Tang的研究表明，经典计算机能够以与量子计算机相当的速度解决推荐问题，这一发现颠覆了量子计算在推荐问题上的优势。尽管这对量子计算领域是一个挫折，但也展示了量子与经典算法研究之间的相互促进。
评论总结
评论内容主要围绕Ewin Tang及其在量子计算领域的研究展开，观点多样，既有对其成就的肯定，也有对量子计算前景的质疑。
对Ewin Tang研究的肯定
- 评论1认为Tang的访谈提供了对量子计算现状的深刻见解：“I listened to the 'Joy of Y' podcast of an interview with Ewin Tang and thought it was an enlightening view of the current state of quantum computing.”
- 评论2提到Tang的论文《Quantum Machine Learning without any Quantum》现已公开，显示其研究的重要性：“Her thesis is now available 'Quantum Machine Learning without any Quantum'.”
对量子计算前景的质疑
- 评论3指出，即使算法更快，其实用性未必优于随机选择：“even if the algorithm is faster, its usefulness shouldn't be superior to a random pick based on some matching criteria.”
- 评论6以幽默的方式批评了量子计算记录的夸大：“Shows in a humorous way how the vast majority of quantum computing 'records' are utter nonsense.”
对Tang个人经历的讨论
- 评论4提到Tang跳级进入大学，认为这可能是巨大的成就，也可能带来社交上的损失：“Oh wow, that is either insanely cool, or a huge loss.”
- 评论5则调侃性地建议Tang解决Transformer和GenAI的扩展问题：“Propose a better architecture and call it AGI.”
对量子计算复杂度的讨论
- 评论7提出BQP和P可能等价的观点，认为量子计算机未必带来计算复杂度的提升：“this result made me believe that BQP and P might be equivalent computational classes.”
- 评论9则引用了其他相关讨论，进一步探讨了Tang的研究对量子计算领域的影响。
总结：评论中对Ewin Tang的研究普遍持肯定态度，但也对量子计算的实际应用和前景提出了质疑，同时对其个人经历和量子计算的复杂度展开了讨论。