> 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.
> 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.