Quantum Advantage for NP Approximation(scottaaronson.blog)
scottaaronson.blog
Quantum Advantage for NP Approximation
https://scottaaronson.blog/?p=8375
37 comments
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/
[1] https://maxsat-evaluations.github.io/
I fell in love with optimisation problems but haven’t played with them in a while…
What are some books to read more about non-linear optimisation that’s also non-machine learning (I’ve dabbled a lot with metaheuristics and genetic algorithms) but haven’t implemented a SAT solver (only played with what Prolog gives you)
What are some books to read more about non-linear optimisation that’s also non-machine learning (I’ve dabbled a lot with metaheuristics and genetic algorithms) but haven’t implemented a SAT solver (only played with what Prolog gives you)
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?
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.
Geoff Hinton was denied an academic position at the University of Sussex's CS department where he had done postdoc work (That department is now 'famous' for consciousness studies and integrated information theory https://osf.io/preprints/psyarxiv/zsr78. I bet they are kicking themselves now ...)
> "Academia will one day wake up, and realize that"
Charlie Munger famously said, "Show me the incentive and I'll show you the outcome" ...
> "Academia will one day wake up, and realize that"
Charlie Munger famously said, "Show me the incentive and I'll show you the outcome" ...
> Geoff Hinton was denied an academic position at the University of Sussex's CS department
These kind of anecdotes are fairly common I believe. Understanding anyone's academic potential is enormously difficult, and the competition is fierce. Hindsight is 20/20 and whatnot.
These kind of anecdotes are fairly common I believe. Understanding anyone's academic potential is enormously difficult, and the competition is fierce. Hindsight is 20/20 and whatnot.
> Random k-SAT is useless
Other than cryptography, is there any real-world value in solving random problem instances of NP-complete problems (at least when average case approaches worst case, based on the parameterization of the problem)? Presumably these are instances that do not have any underlying mathematical structure as a truly random problem instance is Kolmogorov-maximal, and thus even if you solve the problem via brute-force, the result still isn't useful for any predictive purpose.
Other than cryptography, is there any real-world value in solving random problem instances of NP-complete problems (at least when average case approaches worst case, based on the parameterization of the problem)? Presumably these are instances that do not have any underlying mathematical structure as a truly random problem instance is Kolmogorov-maximal, and thus even if you solve the problem via brute-force, the result still isn't useful for any predictive purpose.
Other than cryptography? Like, you see a use-case for it there? Please do educate me! IMO there's nothing there. It's a barren landscape. The desert is more alive.
Haha, I was more so meaning that cryptography depends on the actual existence of hard problem instances, which appears to be the case but hasn’t been conclusively proved.
I'm curious, which solver did you work on? And yeah, I've been working on formally verifying bitblasting in Lean (https://github.com/leanprover/lean4/pulls?q=+is%3Apr+author%...), and it's genius --- the algorithms, the reductions, the heuristics, it's all so deep.
Wow, nice work [1] ! I used to work on CryptoMiniSat a lot. Nowadays I'm doing model counting and maybe synthesis, if all goes well [2]
[1] https://github.com/leanprover/lean4/pulls/bollu [2] https://x.com/SoosMate/status/1827308967208317241
[1] https://github.com/leanprover/lean4/pulls/bollu [2] https://x.com/SoosMate/status/1827308967208317241
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/
[0] https://arxiv.org/abs/2408.08292 [1] https://quantumalgorithmzoo.org/
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.
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-usin... and observe other exotic phases of matter 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.
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.
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-usin... and observe other exotic phases of matter 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.
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.
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.
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.
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.
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.
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.
Is there a place for quantum computers if classical algorithms become more capable at simulating quantum mechanics in ways we find useful?
Computational physicists have been thinking about algorithms for simulating quantum systems essentially since computers were invented. We have decent algorithms for approximating ground states, or for systems in equilibrium (contingent on it being spin-balanced, or at half-filling, or at 0 density, ... depending on the model), or in other limited circumstances.
But lift any of those special restrictions, and simulation methods hit a sign problem [sign]. In particular, real-time evolution of quantum systems, which is what a quantum computer does by its very nature, poses in some sense the most difficult sign problem for approaches leveraging classical computing.
That's not a proof that classical algorithms can't become more capable, but it's almost certainly a question that must be answered system-by-system. The generic sign problem is NP-hard, so special-case reasoning is required.
[sign]: https://en.wikipedia.org/wiki/Numerical_sign_problem
But lift any of those special restrictions, and simulation methods hit a sign problem [sign]. In particular, real-time evolution of quantum systems, which is what a quantum computer does by its very nature, poses in some sense the most difficult sign problem for approaches leveraging classical computing.
That's not a proof that classical algorithms can't become more capable, but it's almost certainly a question that must be answered system-by-system. The generic sign problem is NP-hard, so special-case reasoning is required.
[sign]: https://en.wikipedia.org/wiki/Numerical_sign_problem
That's for the strong force. The challenge with quantum chemistry is the 2^N state space for N particles.
The reason those lattice field theory computations are done that way is that they provide stochastic but polynomial-time algorithms for exactly the same kind of exponentially-large state space that appears in quantum chemistry.
[deleted]
You are kind of asking if quantum computers would still be useful if quantum computers are not useful. By definition the answer is no.
Breaking crypto, unless that falls too. Not all crypto, I'm skeptical on Grover's. Mostly elliptic curve and integer factorization stuff.
> 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://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
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://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
> 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.
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.
Right. We are now arguing over the nuances of what would make quantum computers useful, which I address in a comment where I say "Everything matters" later in this thread.
Most people who work in this field doubt that every quantum simulation problem we care about will be classical tractable in practice, that is, non worst-case. If we believed that, we might as well give up and continue to use the robust, mature classical computers we have and will continue to have better instances of for the foreseeable future.
Most people who work in this field doubt that every quantum simulation problem we care about will be classical tractable in practice, that is, non worst-case. If we believed that, we might as well give up and continue to use the robust, mature classical computers we have and will continue to have better instances of for the foreseeable future.
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.
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.
> 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.
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.
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.
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.)
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.)
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.
> 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.
but is there quantum advantage for the mentioned dating app?
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?
But I don't know why you'd need an app for that. Sounds more like a lab process?
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...
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