←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.317s | source
Show context
djha-skin ◴[31 Aug 25 22:24 UTC] No.45087650[source]▶
Does this essentially mean that the Big-O "circuitry requirements" of factoring integers using Schorr's is super polynomial?
replies(1): >>45087867 #
1. cvoss ◴[31 Aug 25 23:02 UTC] No.45087867[source]▶
The article explains the gate cost mostly comes from O(n) multiply-under-mod ops on O(n)-bit numbers. Each op could be naively spelled out as O(n^2) gates. So the whole thing looks cubic to me at worst.