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.

This person assumed I didn’t know what I was talking about because I accidentally wrote “in NP” instead of “NP-hard,” and seemed bothered that I was questioning them at all, so I got blocked. In any case, I still don’t get what I’m getting so wrong here. If someone can tell me, I’d appreciate it.

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