[okintheory]

You should be very skeptical of all those applications except Shor.

HHL: Here's a quote from Ewin Tang [1]: "We know that quantum computers can “efficiently solve” high-dimensional linear algebra problems; however, this assumes that we have some way to evolve a quantum system precisely according to input data, a much harder problem than the linear algebra itself."

[1] https://ewintang.com/blog/2019/01/28/an-overview-of-quantum-...

Grover's search: This is a speed-up from 2^n to 2^sqrt(n). Impressive, but there's not a lot of exp-time algorithms that people ever run. They go for heuristics instead.

Quantum fourier transforms: This is a tool, it's cool, but needs an application. I haven't seen a serious proposal for using it somewhere where a classical algorithm wouldn't do better.

[okintheory]

Also, just to add, 'quantumalgorithmszoo.org' is quite out of date: For example, they claim a polynomial speed-up for network flow, but that's based on the SOTA in 2007. These days, there's an almost-linear time classical algorithm [A], and no matching quantum algorithm (and also the idea that you would want to use a quantum computer to shave a factor n^(0.0001) is ridiculous). Now, all these statements are only about asymptotics, but don't get me started on practicalities: The idea that in the next 50 years you would use a quantum computer for any problem with only a polynomial speed-up is silly.

[A] https://www.quantamagazine.org/researchers-achieve-absurdly-...

[n4r9]

> this assumes that we have some way to evolve a quantum system precisely according to input data, a much harder problem than the linear algebra itself

That's a fair point. I guess I was interpreting OP's question as "what can we do once we have engineered quantum computers", and would categorise this "harder problem" as an engineering problem.

[bowsamic]

> would categorise this "harder problem" as an engineering problem.

I'm not sure what your relation to the field is, but I have found that a lot of things that look like engineering problems from the outside, end up being theoretical and fundamental problems from within. This is often the case when I discuss quantum noise of gravitational wave detectors. I often see people say things like "I wouldn't want to be the guy who has to make these gravitational wave detectors less noisy", almost implying it's just a case of one guy sitting there turning some knobs, but in reality it's thousands of physicists coming up with entirely new theoretical frameworks, often discovering fundamental issues of quantum measurement and control theory (quantum non demolition measurements, quantum squeezing, back action evasion, etc.), or coming up with the most sensitive seismometers ever, or developing new mirror coatings, etc.

Everyone thought that Apple's cancelled wireless charger was just an engineering problem, but it turned out that it seems to be physically impossible to achieve what they wanted.

That said, perhaps in this case you are right, but it's not often obvious what is simply a matter of time and what requires whole new paradigms.

[n4r9]

Again, a totally fair point. I just mean that when you posed the question "what exactly are quantum computers useful for?", I kind of assumed you meant an ideal quantum computer that had this kind of control over its state.

For reference I am out of my depth! My doctorate was in quantum information theory but I've been out of academia for many years now.

[bowsamic]

Yeah, I did mean that, and I stand by my opinion that even the ideal cases are not particularly compelling. I'm just also pointing out that the ideal case is not actually possible, even theoretically. There will also be decoherence, for example, and even the tomography of the state (i.e. actually measuring the state) is limited by fundamental quantum noise (e.g. ultimately the Heisenberg limit).

[n4r9]

I guess it depends on what you find compelling. I'm not interested in finance. A lot of it just seems like moving money around to make wealthy people wealthier. But it does make sense that a lot of heads will perk up if there's a potential for speeding up market simulation models.