[eru]

Do you have any sources that give good evidence that quantum computers are useful for 'weather predictions, machine learning, search, finance, logistics, classical simulations (e.g. fluid flow) and basically anywhere you have linear algebra or NP problems'? I'm basing my skepticism mostly on the likes of Scoot Aaronson.

I can believe that quantum computers might be useful for chemistry simulations (Quantum computers aren't really useful for encryption. But you could theoretically use them. They just don't really give you any advantage over running a quantum resistant algorithm on a classic computer.)

I'm especially doubtful that quantum computer would be useful for arbitrary NP problems or even arbitrary linear algebra problems.

[adastra22]

Both answers here are a good start:

https://cs.stackexchange.com/questions/76525/could-a-quantum...

There are specialized algorithms for any part of it, especially search. But demonstrating that quantum computers are good for linear algebra should be enough to show that they are generally useful, I hope.

The encryption I was referring to was quantum link encryption (technically not a quantum computer, but we are splitting hairs here; it uses the same set of underlying mechanisms). Quantum link encryption permits you to have a communications channel that if someone tries to man in the middle, all it does is break the link. Both you and the attacker only see gibberish. It’s like a one time pad that doesn’t require first exchanging pads.

[eru]

Thanks, but you can follow the comments on the answers to get eg https://scottaaronson.blog/?p=2196

See https://scottaaronson.blog/?p=8329 for something more recent.

[adastra22]

Scott to be a bit of a Debbie Downer on quantum timelines, and you need to be able to separate that from actual criticisms of the underlying technology. If you look past the way he phrased it, his criticisms of quantum machine learning basically boil down to: there are still some things to be worked out. Not that we have no expectation on how to work those things out, just that there are still unsolved challenges to be tackled.

That’s not really a takedown of the idea.

The more critical challenge is that there is a massive, massive, constant factor difference between classical and quantum computing using foreseeable technology. Even in the best case (like factoring) where a quantum computer gives you a logarithmic algorithm for a classically exponential problem, it does happen to throw in slowdown factor of a trillion. Oops.

But still, even with large constant factors, algorithmic improvements eventually went out asymptotically. It’s just a matter of building a quantum computer big enough and reliable enough to handle problems of that size.

We are already hitting the limits of what we can train on GPUs with reasonable cost. I expect that there will be many advances in the years to come from improved training algorithms. But at some point that will run dry, and further advances will come from quantum computing. Scott is right to point out that this is far, far beyond any existing companies planning horizon. But that doesn’t mean quantum technologies won’t work, eventually.