←back to thread

Why haven't quantum computers factored 21 yet?

(algassert.com)
335 points ingve | 1 comments | 31 Aug 25 12:14 UTC | HN request time: 0.201s | source
Show context
NooneAtAll3 ◴[31 Aug 25 16:48 UTC] No.45084643[source]▶
> I think a more plausible amount of optimization would produce a circuit with 500x the cost of the factoring-15 circuit

I don't get this part

If author already produced "115x", how can optimizations make it worse?

replies(4): >>45084837 #>>45084872 #>>45085102 #>>45086295 #
1. tsimionescu ◴[31 Aug 25 17:37 UTC] No.45085102[source]▶
The point was that the amount of optimization work that went into making the circuit for factoring 21 only ~100x larger than the one for factoring 15 is not feasible for larger numbers. So, the general rule should be that you need ~500x more gates for a similar increase in the number to be factored, not just ~100x.