[HN Gopher] Quantum Advantage for NP Approximation
       ___________________________________________________________________
        
       Quantum Advantage for NP Approximation
        
       Author : apsec112
       Score  : 18 points
       Date   : 2024-10-05 23:27 UTC (3 days ago)
        
 (HTM) web link (scottaaronson.blog)
 (TXT) w3m dump (scottaaronson.blog)
        
       | inasio wrote:
       | 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/
        
       | uhgtherp wrote:
       | 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.
        
       ___________________________________________________________________
       (page generated 2024-10-09 23:00 UTC)