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.

12/8/26, 11:52 pm0 reposts1 like

Corey J. Maley

@coreymaley.net

12 Aug

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.

Corey J. Maley

@coreymaley.net

12 Aug

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

Corey J. Maley

@coreymaley.net

12 Aug

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.

Johannes Brinz

@johannesbrinz.bsky.social

13 Aug

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