Post

Someone blocked me for questioning the claim that “hardware doesn’t matter for tractability.” This person knows this area well, but also it seems like at least one case of a quantum algorithm is a counter example. Integer factorization on classical computers is intractable.

It’s not NP-hard, but in the sub-exponential complexity class. NP-hard problems are intractable, but so are those in the sub-exponential class. There is an algorithm (Shor’s algorithm) that factors integers in polynomial time (it’s in the BQP class , thus tractable), but it’s a quantum algorithm.

Given that quantum algorithms can only run on quantum computers, this seems like a case where the kind of hardware changes what is tractable.

My guess: „Hardware“ is ambiguous between “architecture” (quantum vs. digital) and material “implementation” (photonic qbits vs. spin qbits). Maybe, they understood you as saying “implementation matters for tractability”?