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.

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

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