undefined | Better HN

0 pointsdenton-scratch3y ago0 comments

> 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?

0 comments

lumost3y ago

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-scratchOP3y ago

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.

j / k navigate · click thread line to collapse