科学与数学quantamagazine.org
一位少年找到了量子推荐算法的经典替代方案
Teenager Finds Classical Alternative to Quantum Recommendation Algorithm
2018 — 2025，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
18岁的Ewin Tang为推荐系统问题找到了一个经典算法，其性能与Kerenidis和Prakash提出的量子算法相当，从而表明该问题上所谓的量子加速可能并不需要量子计算机。这一结果在复杂度理论界引起轰动，也引发了对量子算法价值的重新思考。
为什么经久不衰：它展示了量子计算研究如何反过来推动经典算法的进步，是量子-经典算法竞争的经典案例，多年后仍具启发性。
HN 评论精选
量子算法即使被'去量子化'，也证明其作为研究工具的价值
Aaronson说：Tang'杀死'了Kerenidis和Prakash的量子加速，但从另一个角度看，她是在他们的工作基础上做出了重大改进——没有他们的量子算法，Tang不可能想出这个经典算法。我认为这值得强调：无论最终是否需要量子计算机，量子计算作为一种模型显然对做研究、推进知识现状很有用。
vanderZwan查看英文原文
> “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. I think this deserves more emphasis: regardless of whether or not we need a quantum computer in the end, as a model quantum computing is apparently useful to do research with and advance the status quo of our knowledge.
新闻标题有误导性，这其实是复杂度理论的成果，与推荐系统关系不大
我想指出'推荐系统'这个角度其实并不重要。这本质上是复杂度理论的结果，回答的是'是否真的需要量子计算机才能在多对数时间内采样部分指定的低秩矩阵的行'。虽然这个问题出现在基于矩阵分解的推荐器中，但已有许多无需量子计算机的成熟解决方案，推荐也远不止这一种方法。
proto-n查看英文原文
I just want to mention that the "recommendation systems" angle is quite unimportant here. This is a result in complexity theory, a resolution of the question "whether you actually need a quantum computer to sample the rows of a partially-specified low-rank matrix in polylogarithmic time" (as Scott Aaronson puts it [1]). While this problem does occur in matrix factorization based recommenders, there are a lot of solutions for it without quantum computers that perform well, and it's far from being the one method for recommendation. [1] https://www.scottaaronson.com/blog/?p=3880
自嘲式感叹天才少年的成就令人望尘莫及
有时我觉得自己挺聪明，因为我会配置 WebPack，然后读到这样的文章……
FactolSarin查看英文原文
Sometimes I think I'm smart because I can configure WebPack, and then I read an article like this.
提供主人公Ewin Tang的成长背景链接
关于Ewin Tang的一些背景资料：http://www.uta.edu/utamagazine/archive-issues/2010-13/2012/12/cultivating-genius/index.html
devy查看英文原文
A little bit backdrop of Ewin Tang: http://www.uta.edu/utamagazine/archive-issues/2010-13/2012/12/cultivating-genius/index.html
历次讨论
同类还值得读
如果月球只有 1 像素：一个极其精确的太阳系模型（2014）
If the moon were only 1 pixel: A tediously accurate solar system model (2014)
一个网页版太阳系模型，以“如果月亮只有 1 像素”的真实比例呈现：你必须一路横向滚动，才能体会行星之间空旷到何等程度。
科学与数学上首页 7 次 · 2014–2025joshworth.com编辑精选沉浸式线性代数（2016）
Immersive Linear Algebra (2016)
《Immersive Linear Algebra》是一本完全免费、开放在线的线性代数“超文本教科书”，其最大特色是大量可交互的图形：读者可以直接拖动、操作图中的向量、矩阵和变换…
科学与数学上首页 5 次 · 2015–2024immersivemath.com编辑精选如何将贝果切成两个相连的半环（2009）
How to Slice a Bagel into Two Linked Halves (2009)
数学家 George Hart 的经典教程，演示如何用一刀把贝果切成两个相互扣住的环，并附上切割步骤与数学原理。
科学与数学上首页 5 次 · 2009–2022georgehart.com“犹太问题”：一组用于歧视的数学题
Jewish problems
一篇 arXiv 论文，整理并讨论苏联时期犹太学生在申请大学数学系时被问到的特殊数学难题：这些题往往有简单解法却极难想到，被用作面试中拒绝犹太考生的手段。
科学与数学上首页 5 次 · 2011–2021arxiv.org你的身体并非为长久而造：人类死亡率数据的一课
Your body wasn’t built to last: a lesson from human mortality rates
文章从人类死亡率随年龄变化的统计规律出发，解释身体并非为长久使用而设计：年轻时死亡风险较低，之后随年龄近似指数上升，像复杂系统在不断累积损伤。
科学与数学上首页 5 次 · 2009–2018gravityandlevity.wordpress.com