7 ms·

Quantum Advantage for NP Approximation

85 points by apsec112 2y ago

inasio 2y ago
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 https://arxiv.org/abs/2408.08292 [1] https://quantumalgorithmzoo.org/ https://quantumalgorithmzoo.org/
- vtomole 2y ago
  I work in this field. Although the prospects for using quantum computers to solve classical problems are pretty bleak, the primary motivator for the invention of quantum computers was not to solve classical problems, but to solve quantum ones: https://tinyurl.com/3ndp36y7 https://tinyurl.com/3ndp36y7. With regards to using quantum computers as they were originally intended, things are looking pretty good! To cherry pick two examples, quantum computers have been used to create a time crystal https://www.quantamagazine.org/first-time-crystal-built-using-googles-quantum-computer-20210730/ https://www.quantamagazine.org/first-time-crystal-built-usin... and observe other exotic phases of matter https://arxiv.org/abs/2305.03766 https://arxiv.org/abs/2305.03766. Think of early quantum computers as tools for scientific discovery, not for addressing industrial problems. Their abilities to solve commercial problems comes later, that is, decades from now.
  - uhgtherp 2y ago
    Is there a place for quantum computers if classical algorithms become more capable at simulating quantum mechanics in ways we find useful?
    - Vecr 2y ago
      Breaking crypto, unless that falls too. Not all crypto, I'm skeptical on Grover's. Mostly elliptic curve and integer factorization stuff.
      - vtomole 2y ago
        > Is there a place for quantum computers if classical algorithms become more capable at simulating quantum mechanics in ways we find useful? There is not. Our existence as a field pretty much hinges on classical computers not being able to simulate all quantum mechanical problems efficiently. We imagine that designing quantum matter: https://cognitivemedium.com/qc-a-science https://cognitivemedium.com/qc-a-science, https://arxiv.org/abs/1508.02595 https://arxiv.org/abs/1508.02595 will be very useful in the scientific and technological sense and we don't think classical computers will ever fully stand up to that task. > Breaking crypto, unless that falls too If classical computers can simulate quantum efficiently then using quantum computers to break crypto also falls. Simulating quantum physics and factoring are in the same complexity class: https://en.wikipedia.org/wiki/BQP https://en.wikipedia.org/wiki/BQP
        Vecr 2y ago
        I don't put too much stock into complexity classes. They're a real thing for sure, but implementation difficulties and constant factors are too.
        vtomole 2y ago
        I agree. "Everything" matters when it comes to these applications: complexity theory, heuristics, constant factors, quantum error correction overhead, qubit quality, improvements in classical algorithms, CPU and GPU improvements e.t.c. Doesn't make sense to put too much stock in just one of these components at the cost of others.
        greeneggs 2y ago
        > Our existence as a field pretty much hinges on classical computers not being able to simulate all quantum mechanical problems efficiently. I don't think this is quite accurate. It could be that many of the kinds of quantum simulations we care about can be done efficiently classically, even if the worst-case quantum simulations are classically intractable. Certainly, classical simulation algorithms are steadily improving.
  - eru 2y ago
    > Think of early quantum computers as tools for scientific discovery, not for addressing industrial problems. Their abilities to solve commercial problems comes later, that is, decades from now. Well, they might become very useful for simulations in material science, even if they 'only' thing they can do better than normal computers is simulate quantum physics.
    - vtomole 2y ago
      Yes. It's a spectrum. In the worst case, quantum computers only help us gain a deep understanding of quantum physics. In the best case, they beat classical computers on optimizations problems as well. Materials science falls somewhere along this spectrum.
      - eru 2y ago
        Yes. Though it's more than a one dimensional spectrum: There's also the orthogonal possibility that quantum computers don't work, or don't work well, and eventually we'll learn some new physics that tells us why. (Given that orthodox quantum mechanics says that quantum computers work, but so far they've been hard to do. It's most likely 'just' engineering issues, but there's still the possibility of something deeper.)
  - thrance 2y ago
    Every communication or marketing I have ever seen done by quantum computing actors has been about very "classical" problems: finance, clean energy, AI... It's all snake oil, obviously. Those are keywords thrown out for VC money. IMO, there would be no way for this many companies to raise this much money if the investors knew what kind of problems quantum computing is really addressing.
    - vtomole 2y ago
      The people who claim that current quantum computers are useful for classical problems contribute to "Quantum hype" which is frowned upon by most members of the community.
      - zero_k 2y ago
        I mean, I wish. I have met these so-called giants of the field when I was at conference (they had a yearly big-brains meeting the same time, same place). I bet they talk about classic stuff because otherwise they wouldn't get funding. Quantum mechanics and using quantum computers for quantum problems actually would have convinced me. But who cares about me. What they need this is this thing called MONEY and that doesn't come with intellectually interesting problems -- it comes with overinflated claims over things that the committee understands. So classical problems it is. Can't blame them playing the game, but at the same time, I wonder how they look into the mirror at night.
        karmakurtisaani 2y ago
        To be fair, this is what academics in basically every field do. If you prove a useless result about an exotic construction in your niche topology, you mention that recently topology has been successfully applied i.e. in data science. If you study some pathological convergencs properties if unheard of stochastic processes, you cite Black-Scholes equation and remind the reader of its importance in finance. Indeed, this is how the game is played.
uhgtherp 2y ago
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.
dsp_person 2y ago
but is there quantum advantage for the mentioned dating app?
- eru 2y ago
  I wonder what quantum effects you can use for dating. Perhaps there's some natural quantum decay process that you can use to figure out the age of some system? (Like C14 carbon dating or so?) But I don't know why you'd need an app for that. Sounds more like a lab process?
  - magicalhippo 2y ago
    Based on friends and what I read online, it seems quite often that someone finds themselves in a superposition of being in a relationship and not being in a relationship when using dating apps, often unwillingly...
zero_k 2y ago
Random k-SAT is useless. I won a number of awards at SAT competitions over the years -- not in random k-SAT, they don't even run that track anymore [1] And I'm pretty damned certain whatever that paper is saying, could be fixed with classical algorithms, if anyone cared about random k-SAT. But nobody does, for a good reason. I could go on ranting about quantum, but I'll stick to the one thing I actually know about, SAT solving. I think there are some really cool things out there, if you wanna dump research money into. For example SMT, model counting, symbolic execution, automated invariant finding, CHC, BMC, function synthesis, programming language research. Academia will one day wake up, and realize that they've been awarding tenure to people who have done nothing but a quantum buzzword generator, while the people working hard at important topics are left behind. Like the dude (Victor Ambros) who recently got the Nobel only to be previously declined tenure at Harvard. Big fail. [1] https://satcompetition.github.io/2024/results.html https://satcompetition.github.io/2024/results.html
- zero_k 2y ago
  By the way, if you truly care about NP-optimization, e.g. MaxSAT algorithms, there's a lot of good work being done, just check out [1]. It's fun, and useful. You could make >$1B just by slightly improving global logistics via such algorithms. Yes, scalability can be an issue, but it only takes some work to cut the problems into chunks, and do local optimization at each level, rather than total global optimization. Yes, it won't be a global optimum, but likely significantly better than what's out there right now. They already use these algorithms for e.g. train and bus schedule optimization. [1] https://maxsat-evaluations.github.io/ https://maxsat-evaluations.github.io/
  - hnaccount_rng 2y ago
    Hypothetically: If a friend with interest in this kind of logistics were to be looking for a job. Which company would one tell said friend to look at?
    - zero_k 2y ago
      Cadence is a good one. There are also bus/train schedule optimization startups/companies. AWS is also hiring in this field, a lot, but I wouldn't recommend it. Even though many people there are very good, and I respect some of the individual people there very much.

85 points by apsec112 2y ago

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 https://arxiv.org/abs/2408.08292 [1] https://quantumalgorithmzoo.org/ https://quantumalgorithmzoo.org/

vtomole 2y ago
I work in this field. Although the prospects for using quantum computers to solve classical problems are pretty bleak, the primary motivator for the invention of quantum computers was not to solve classical problems, but to solve quantum ones: https://tinyurl.com/3ndp36y7 https://tinyurl.com/3ndp36y7. With regards to using quantum computers as they were originally intended, things are looking pretty good! To cherry pick two examples, quantum computers have been used to create a time crystal https://www.quantamagazine.org/first-time-crystal-built-using-googles-quantum-computer-20210730/ https://www.quantamagazine.org/first-time-crystal-built-usin... and observe other exotic phases of matter https://arxiv.org/abs/2305.03766 https://arxiv.org/abs/2305.03766. Think of early quantum computers as tools for scientific discovery, not for addressing industrial problems. Their abilities to solve commercial problems comes later, that is, decades from now.
- uhgtherp 2y ago
  Is there a place for quantum computers if classical algorithms become more capable at simulating quantum mechanics in ways we find useful?
  - Vecr 2y ago
    Breaking crypto, unless that falls too. Not all crypto, I'm skeptical on Grover's. Mostly elliptic curve and integer factorization stuff.
    - vtomole 2y ago
      > Is there a place for quantum computers if classical algorithms become more capable at simulating quantum mechanics in ways we find useful? There is not. Our existence as a field pretty much hinges on classical computers not being able to simulate all quantum mechanical problems efficiently. We imagine that designing quantum matter: https://cognitivemedium.com/qc-a-science https://cognitivemedium.com/qc-a-science, https://arxiv.org/abs/1508.02595 https://arxiv.org/abs/1508.02595 will be very useful in the scientific and technological sense and we don't think classical computers will ever fully stand up to that task. > Breaking crypto, unless that falls too If classical computers can simulate quantum efficiently then using quantum computers to break crypto also falls. Simulating quantum physics and factoring are in the same complexity class: https://en.wikipedia.org/wiki/BQP https://en.wikipedia.org/wiki/BQP
      - Vecr 2y ago
        I don't put too much stock into complexity classes. They're a real thing for sure, but implementation difficulties and constant factors are too.
        vtomole 2y ago
        I agree. "Everything" matters when it comes to these applications: complexity theory, heuristics, constant factors, quantum error correction overhead, qubit quality, improvements in classical algorithms, CPU and GPU improvements e.t.c. Doesn't make sense to put too much stock in just one of these components at the cost of others.
      - greeneggs 2y ago
        > Our existence as a field pretty much hinges on classical computers not being able to simulate all quantum mechanical problems efficiently. I don't think this is quite accurate. It could be that many of the kinds of quantum simulations we care about can be done efficiently classically, even if the worst-case quantum simulations are classically intractable. Certainly, classical simulation algorithms are steadily improving.
- eru 2y ago
  > Think of early quantum computers as tools for scientific discovery, not for addressing industrial problems. Their abilities to solve commercial problems comes later, that is, decades from now. Well, they might become very useful for simulations in material science, even if they 'only' thing they can do better than normal computers is simulate quantum physics.
  - vtomole 2y ago
    Yes. It's a spectrum. In the worst case, quantum computers only help us gain a deep understanding of quantum physics. In the best case, they beat classical computers on optimizations problems as well. Materials science falls somewhere along this spectrum.
    - eru 2y ago
      Yes. Though it's more than a one dimensional spectrum: There's also the orthogonal possibility that quantum computers don't work, or don't work well, and eventually we'll learn some new physics that tells us why. (Given that orthodox quantum mechanics says that quantum computers work, but so far they've been hard to do. It's most likely 'just' engineering issues, but there's still the possibility of something deeper.)
- thrance 2y ago
  Every communication or marketing I have ever seen done by quantum computing actors has been about very "classical" problems: finance, clean energy, AI... It's all snake oil, obviously. Those are keywords thrown out for VC money. IMO, there would be no way for this many companies to raise this much money if the investors knew what kind of problems quantum computing is really addressing.
  - vtomole 2y ago
    The people who claim that current quantum computers are useful for classical problems contribute to "Quantum hype" which is frowned upon by most members of the community.
    - zero_k 2y ago
      I mean, I wish. I have met these so-called giants of the field when I was at conference (they had a yearly big-brains meeting the same time, same place). I bet they talk about classic stuff because otherwise they wouldn't get funding. Quantum mechanics and using quantum computers for quantum problems actually would have convinced me. But who cares about me. What they need this is this thing called MONEY and that doesn't come with intellectually interesting problems -- it comes with overinflated claims over things that the committee understands. So classical problems it is. Can't blame them playing the game, but at the same time, I wonder how they look into the mirror at night.
      - karmakurtisaani 2y ago
        To be fair, this is what academics in basically every field do. If you prove a useless result about an exotic construction in your niche topology, you mention that recently topology has been successfully applied i.e. in data science. If you study some pathological convergencs properties if unheard of stochastic processes, you cite Black-Scholes equation and remind the reader of its importance in finance. Indeed, this is how the game is played.

uhgtherp 2y ago

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.

dsp_person 2y ago

but is there quantum advantage for the mentioned dating app?

eru 2y ago
I wonder what quantum effects you can use for dating. Perhaps there's some natural quantum decay process that you can use to figure out the age of some system? (Like C14 carbon dating or so?) But I don't know why you'd need an app for that. Sounds more like a lab process?
- magicalhippo 2y ago
  Based on friends and what I read online, it seems quite often that someone finds themselves in a superposition of being in a relationship and not being in a relationship when using dating apps, often unwillingly...

zero_k 2y ago

Random k-SAT is useless. I won a number of awards at SAT competitions over the years -- not in random k-SAT, they don't even run that track anymore [1] And I'm pretty damned certain whatever that paper is saying, could be fixed with classical algorithms, if anyone cared about random k-SAT. But nobody does, for a good reason. I could go on ranting about quantum, but I'll stick to the one thing I actually know about, SAT solving. I think there are some really cool things out there, if you wanna dump research money into. For example SMT, model counting, symbolic execution, automated invariant finding, CHC, BMC, function synthesis, programming language research. Academia will one day wake up, and realize that they've been awarding tenure to people who have done nothing but a quantum buzzword generator, while the people working hard at important topics are left behind. Like the dude (Victor Ambros) who recently got the Nobel only to be previously declined tenure at Harvard. Big fail. [1] https://satcompetition.github.io/2024/results.html https://satcompetition.github.io/2024/results.html

zero_k 2y ago
By the way, if you truly care about NP-optimization, e.g. MaxSAT algorithms, there's a lot of good work being done, just check out [1]. It's fun, and useful. You could make >$1B just by slightly improving global logistics via such algorithms. Yes, scalability can be an issue, but it only takes some work to cut the problems into chunks, and do local optimization at each level, rather than total global optimization. Yes, it won't be a global optimum, but likely significantly better than what's out there right now. They already use these algorithms for e.g. train and bus schedule optimization. [1] https://maxsat-evaluations.github.io/ https://maxsat-evaluations.github.io/
- hnaccount_rng 2y ago
  Hypothetically: If a friend with interest in this kind of logistics were to be looking for a job. Which company would one tell said friend to look at?
  - zero_k 2y ago
    Cadence is a good one. There are also bus/train schedule optimization startups/companies. AWS is also hiring in this field, a lot, but I wouldn't recommend it. Even though many people there are very good, and I respect some of the individual people there very much.