[throw149102]

One point of interest was the paper on quantum computing applied to quantum chemistry[1]. In that paper, they did not find generic exponential speedup for a list of chemistry problems with current quantum algorithms. There are 3 problems with this: a speedup does not need to be exponential in order to be incredibly valuable; a speedup does not need to be extremely generic, just enough to cover real-world use cases; and quantum algorithms are still in their infancy, and it's unclear how much more we might discover in the next 10-20 years.

Furthermore, the paper itself links to a github repository[2] with a list of papers that either imply or use an exponential advantage in quantum chemistry. Now would be a good time to mention that I am not an expert in chemistry, nor have I read the entirety of this list of papers so I am not in a position to go through each and every one to decide how generic their results are or what the limitations are. Perhaps all these papers have fundamental limitations that prevent it from being useful in normal chemistry, only in weird souped-up problems specifically devised for a quantum advantage.

Either way, this paper is by no means conclusive on the subject. There's a ton of more research to be done in multiple fields to know for sure.

[1] https://arxiv.org/pdf/2208.02199.pdf [2] https://github.com/seunghoonlee89/Refs_EQA_GSQC

[lumost]

The reason exponential speedups are required is due to the extreme cost of quantum computing R&D and extremely limited quantum computers that come out of it.

I can provision 1k CPU based servers or ~20 4x GPU based servers in a cloud computing environment for an hour for <$400. These are mature technologies with massive economies of scale behind them. A quantum computer needs to not only outperform scale out GPU/CPU performance on a particular problem set, it needs to crush it.

[denton-scratch]

> The reason exponential speedups are required is due to the extreme cost of quantum computing R&D and extremely limited quantum computers that come out of it.

Hmmm. I'm no mathematician; but I thought the value of an "exponential speedup" is if you are trying to solve a problem with "exponential complexity".

I don't know if "exponential compexity" is a thing; I'm pretty sure "exponential speedup" isn't. Is it correct to say that a quantum factoring machine has an "exponential speedup"? Isn't it more accurate to say that the exponential difficulty is a property of the classical algorithms, not of the problem itself?

[lumost]

In an informal setting, specifying an exponential speed up is equivalent to specifying a "linear time solution to a problem for which the best known classical algorithm has exponential complexity".

My point was that we have immense amounts of classical compute available. QC systems will not be economically viable unless they deliver gains which are >10x classical computers.

[denton-scratch]

OK, thanks.

I'm one of those pedants that cringes when anyone uses "exponential" to mean "very fast". In a technical forum like this, I expect people to use a word like that fairly precisely; I'm cool with the version "a linear-time solution to a problem with exponential-time complexity for classical algorithms".

I'm also OK with your claim about the economic viability of QC; I'm not OK with the implication that there is anything exponential about a 10x performance gain.