undefined | Better HN

0 pointslumost3y ago0 comments

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.

0 comments

denton-scratch3y 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

0 comments

denton-scratch3y ago

OK, thanks.

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