Major quantum computing advance made obsolete by teenager (2018)
A 2018 Quanta article, resurfaced on Hacker News, covering Ewin Tang's classical algorithm for the recommendation-systems problem. Kerenidis and Prakash's quantum recommendation algorithm had been a leading candidate for exponential speedup; as an undergraduate, Tang produced a classical algorithm with comparable polylogarithmic scaling under sampling-access assumptions, removing that speedup and launching the "dequantization" line of work.
Why it matters: A reminder that claimed exponential quantum speedups for linear-algebraic and ML tasks often depend on input-access assumptions that classical sampling algorithms can match, so speedup claims in QML deserve scrutiny.
Algorithms & complexityQuantum machine learningoverview