alt Hacker NewsOn one hand I hear that quantum computers will crack factorisation and discrete logarithms, on the other that the max number factorised is 15 and that 21 might not even be feasible.
What is going on?
Replies
From what i understand the 15 factor was just a stunt and didnt use the actual error corrected algorithm that needs to be used in general.
I think an analogy would be, imagine you are driving across north america in a car, but your engine is broken. The mechanic is near by so you put it in neutral and push it.
If someone said, well it took you half an hour to push it to the mechanic, it will take the rest of your life to get it across north america - that would be the wrong take away. If the mechanic actually fixes the engine, you'll go quite fast quite quickly. On the other hand maybe its just broke and can't be fixed. Either way how fast you can push it has no bearing on how fast the mechanic can fix it or how fast it will work after its fixed.
Maybe people will figure out quantum computers maybe they won't, but the timeline of "factoring" 15 is pretty unrelated.
In the context of cryptography, keep in mind its hard to change algorithms and cryptographers have to plan for the future. They are interested in questions like: is there a > 1% change that a quantum computer will break real crypto in the next 15 years. I think the vibe has shifted to that sounding plausible. Doesn't necessarily mean it will happen, its just become prudent to plan for that eventuality, and now is when you would have to start.
This article, "Factoring is not a good benchmark to track Q-day", was posted this month by one of Cloudflare's lead post-quantum researchers specifically addressing the factoring issue.
https://bas.westerbaan.name/notes/2026/04/02/factoring.html
It doesn't say much by itself, but it has four very good links on the subject. One of these has a picture of the smallest known factor-21 circuit, which is vastly larger than that of the factor-15 circuit, and comparable to much larger numbers. Another is Scott Aaronson's article making the analogy of asking factoring small numbers as asking for a "small nuclear explosion" - if you're in 1940 and not able to make a small nuclear explosion, that doesn't mean you're much farther away from a big nuclear explosion.
In the last month there has been a sharp vibe shift among cryptography engineers based on rumors that we may have demonstrations of CRQCs much sooner than anticipated, perhaps within 5 years. You're not going to get satisfactory answers beyond that; everybody understands the "factored 15" thing, the people for whom the vibe has shifted have priced that in.
It's LK99 all over again. A bunch of software engineers working themselves into a tizzy on X and adjacent circles despite not really knowing the physics. Combined with a lot of financial incentives for people working in the space to play things up...
The quantum circuit to factor 15 is a weird special case that can be factored with just a handful of logic gates [0]. Factoring 21 will require quantum error correction, which adds a huge amount of overhead.
The idea seems to be that there will some sort of cascading effect if we can somehow create physical qubits with sufficient noise performance. It's this "threshold" we keep hearing about. Once we exceed threshold there is a possibility that we can use error correction to expand everything without limit.
This assumes that there will not be other problems that arise. I suspect that "error correcting" thousands of qubits entangled with one another will be one of those problems.
The current state (no real threat to RSA) ≠ plausible but not certain future state (RSA and EC are broken).
Coherency
To get useful results, a quantum computer needs all of its qbits to stay entangled with each other, until the entire group collapses into the result. With current technology, it is very difficult for a reasonable sized group of qbits to stay coherently entangled, so it can only solve problems that are also relatively easy to solve on classical computers.
If someone today were to figure out how to keep large numbers of bits entangled, then quantum computing would instantly be able to break any encryption that isn't quantum safe. It's not something that we are slowly working toward; it's a breakthrough that we can't predict when, or even if, it will happen.
> The bet is not “are you 100% sure a CRQC [cryptographically-relevant quantum computer] will exist in 2030?”, the bet is “are you 100% sure a CRQC will NOT exist in 2030?”
— from https://words.filippo.io/crqc-timeline/ "A Cryptography Engineer’s Perspective on Quantum Computing Timelines", the OP's blog post from two weeks ago, and the first link in this one. [HN discussion: https://news.ycombinator.com/item?id=47662234]
Yes today's quantum computers cannot factor 21, but enough progress is happening fast enough that now there's a >1% chance they will go much further in (say) five years.
More broadly (outside of relevance to cryptography), quantum computers already can (almost certainly) beat classical computers on certain contrived (useless) problems: see https://arxiv.org/abs/2603.09901 "Has quantum advantage been achieved?" for a summary of the current state.