The first author of the preprint [0] discussed by Scott Aaronson (Stephen Jordan) is also the maintainer of the quantum algorithms zoo [1], which tracks all of the quantum algorithms that have any kind of advantage over classical ones. It's still pretty bleak, not a lot of big wins for quantum algorithms, even assuming we had working hardware. As far as I know, Shor's algorithm is still the best one, after all these years.

[0] https://arxiv.org/abs/2408.08292 [1] https://quantumalgorithmzoo.org/

A lot of fun stuff in this post.

> then my blogging about it led to a group of ten computer scientists killing the claim by finding a classical algorithm that got an even better approximation.

And its callback,

> Regardless, though, as of this week, the hope of using quantum computers to get better approximation ratios for NP-hard optimization problems is back in business! Will that remain so? Or will my blogging about such an attempt yet again lead to its dequantization? Either way I’m happy.

The idea of working on nphard problems that have “algebraic structure” is clever.

I wonder if the team behind this preprint chose the problem with that intent in mind or if it’s just an observation by Aaronson.