Quantum Advantage for NP Approximation

by apsec112 • 2 years ago

85 36 2 years ago

inasio• 2 years 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 [1] https://quantumalgorithmzoo.org/

vtomole6• 2 years 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.

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.

uhgtherp2• 2 years ago

Is there a place for quantum computers if classical algorithms become more capable at simulating quantum mechanics in ways we find useful?

eru3• 2 years 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.

thrance• 2 years 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.

uhgtherp2• 2 years 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• 2 years ago

but is there quantum advantage for the mentioned dating app?

eru3• 2 years 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• 2 years 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_k6• 2 years 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

zero_k6• 2 years 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/

hnaccount_rng• 2 years 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?

alfiedotwtf• 2 years ago

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)

9q9• 2 years ago

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

karmakurtisaani2• 2 years ago

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.

Xcelerate2• 2 years ago

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.

zero_k6• 2 years ago

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.

bollu• 2 years ago

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.

zero_k6• 2 years ago

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

Quantum Advantage for NP Approximation

Related Stories