I’m skeptical about—and not qualified to review—this new result in factorization with a quantum computer, but if it’s true it’s a theoretical improvement in the speed of factoring large numbers with a quantum computer.
Spencer • March 16, 2026 6:10 AM
I was also going to post the aaronson link. The summary is that their algorithm relies on an exponential classical computation. So it works on small numbers but can’t scale (the largest composite tested in the paper is 1363).
bro256 • March 16, 2026 10:53 AM
People often celebrate new “improvements” in integer factorization, but it’s important to keep perspective.
Even with decades of research and better algorithms, progress without cheating is extremely slow. As a simple reminder about factoring 21:
https://algassert.com/post/2500
So while papers may claim optimizations or theoretical advances, the practical reality is that factoring numbers with quantum computers remains incredibly difficult.
Clive Robinson • March 16, 2026 1:54 PM
@ ALL,
The question at the back of some minds can be answered by,
“Woof… Woof, woof.”
As I noted a few days back as this story surfaced caution should be applied to it…
As with all quantum algorithms, you need to see three things,
1, The size of the “circuit”
2, The “generality” of the solution
3, There is not a faster “classical” non quantum algorithm available.
As I understand it this is about making the classical non quantum part of the algorithm faster, but only for smallish numbers.
Dave • March 17, 2026 4:33 AM
Whenever you hear any new quantum factorisation record announced, your automatic response shouldn’t be “this is really scary” but “where did they cheat?”.
People have already linked to Scott Aaaronson’s blog, there’s also https://postquantum.com/security-pqc/cybersecurity-apocalypse-in-2026-jvg/. First section is titled “The Technical Disconnect: Moving the Goalposts”.
Clive Robinson • March 17, 2026 8:14 AM
@ Dave,
With regards,
“your automatic response shouldn’t be “this is really scary” but “where did they cheat?”.”
But it can be so much more fun…
This video links back to a paper that has been mentioned here before,
https://m.youtube.com/watch?v=wgJojeXcuc4
Hence my “Woof… Woof, woof” comment above.
But it also mentions a few other things that people might have wondered about, like why “divide and conquer can make algorithms faster than claimed theoretical limits. Thus that and other classical algorithms are sub-optimal, and why they can become faster than Quantum equivalents that work with “random inputs”.
And other things such as why you often here about things on this blog eight or more years before they are “real world” concerns.
Subscribe to comments on this entry
Sidebar photo of Bruce Schneier by Joe MacInnis.
Luca Mariot • March 16, 2026 5:55 AM
Definitely not an improvement; see Aaronson’s blog post: https://scottaaronson.blog/?p=9615