If you are to believe the glossy marketing campaigns about ‘quantum computing’, then we are on the cusp of a computing revolution, yet back in the real world things look a lot less dire. At least if you’re worried about quantum computers (QCs) breaking every single conventional encryption algorithm in use today, because at this point they cannot even factor 21 yet without cheating.
In the article by [Craig Gidney] the basic problem is explained, which comes down to simple exponentials. Specifically the number of quantum gates required to perform factoring increases exponentially, allowing QCs to factor 15 in 2001 with a total of 21 two-qubit entangling gates. Extrapolating from the used circuit, factoring 21 would require 2,405 gates, or 115 times more.
Explained in the article is that this is due to how Shor’s algorithm works, along with the overhead of quantum error correction. Obviously this puts a bit of a damper on the concept of an imminent post-quantum cryptography world, with a recent paper by [Dennish Willsch] et al. laying out the issues that both analog QCs (e.g. D-Wave) and digital QCs will have to solve before they can effectively perform factorization. Issues such as a digital QC needing several millions of physical qubits to factor 2048-bit RSA integers.
Maybe it’s no a pure implementation of Shor’s algorithm, but it appears quantum computers have factored 21 before, in 2012: https://arxiv.org/abs/1111.4147
Although there seems to be criticism towards this: https://arxiv.org/abs/1301.7007
Found while trying to get an understanding of Shor’s algorithm from wikipedia:
https://en.wikipedia.org/wiki/Shor%27s_algorithm
Well, to be honest, they did factor 21. But, being a quantum computer, nobody knows where the result is stored.
https://eprint.iacr.org/2025/1237.pdf
Essentially, every even slightly impressive claim of quantum capability has been some form of semi-fraud.
Factored an RSA-2048 pair of primes? They only differ by a few bits, so it’s equivalent (“compiled” using a classical computer) to a simple less-than-21 factorization. Factored 1,099,551,473,989 back in 2019? That number is a 1 followed by a whackload of zeroes. etc. etc.
They propose that all future factoring efforts must be done on products whose primes are not known to researchers, to make this sleight-of-hand more difficult.
That linked paper is a work of art :) it combines the right amount of knowledge with the right amount poking fun at previous research.
To be clear for everyone else, it’s titled: “Replication of Quantum Factorisation Records with an 8-bit Home Computer, an Abacus, and a Dog”
And you should read it.
Oh, my word! That paper is so funny!
Taking a shot at the cheating methods used to “factorise” specific numbers:
Taking a shot at current politics:
Just being funny:
A final shot at current quantum factorisation methods:
That paper is a gold mine of sarcasm and wit.
Regarding the use of a dog in the experiments:
OP should have posted the title not just a dry link!
There’s a growing argument that meaningful quantum computing will never become possible, due to both the exponential explosion in gates as and the growing overhead of “quantum error correction” causing any attempt to collapse it’s own weight.
It would require so many gates that it would be impossible for them to ever become quantum in the first place. eg. you could never build a cryostat cold and perfect enough.
And distributed QCs don’t make sense I suppose?
It’s an interesting problem – trading exponential complexity in software for exponential complexity in hardware.
There’s no such thing as a distributed quantum computer. The defining property of quantum systems is that they remain entangled, even when the particles are separated. Physically separating the parts of the system doesn’t do anything to make it any less fragile.
It’s also worth noting, there’s no such thing as quantum “software” here. Quantum computers aren’t computers in the traditional sense. They’re physics experiments set up to mimic some mathematical problem, and that “error correction” means redundant circuits. Not code.
There’s no quantum software- yet. We’re currently at the discrete gate level of this technology (or at least single IC). Quantum architecture is capable of computing anything a traditional computer does, just we don’t have hardware with anywhere near enough cubits or gates yet to run software. There absolutely will be quantum computing at some point, and if it happens in our lifetime, it would come as one of the biggest changes to computing in history. However, right now the hardware is extremely primitive compared to traditional digital computers.
Also, bear in mind there’s a STRONG incentive to say that all the problems will solve themselves if “we just need to scale up.” That’s why we hear it everywhere: in AI, in SMRs, in quantum computing. It’s music to investors’ ears, and will bring lots of funding to your project.
If the only problem is “scaling up” then it’s a problem that can be solved purely with money and investors have lots of money. That’s their job. Their platonic ideal is a technology that’s had all the hard research problems worked out and just needs to be scaled up to start returning a profit.
Who knows! Maybe all those pesky problems will just disappear if we just scale up! Or, maybe they don’t. But it can be really tempting for researchers to place that bet, because failures rarely backfire on them.
I’m not sure if it is impossible. But it does feel like it needs a revolutionary step, instead of an evolutionary one.
EUV for chip fabrication looked impossible, and it required several revolutionary steps and a mega-ton of engineering to pull it off. And it feels like quantum computing is trying to do the engineering steps without having the required revolutionary steps to support it.
You are actually making a lot of sense. The problem is they don’t know what they want to create and the problem they are trying to solve with for humanity.
Also they need reevaluation of thoughts.
Putting noise to use.
https://www.sciencedaily.com/releases/2026/01/260129080418.htm
If the title of the article is a question, the answer is usually “no.”
WHY HAVEN’T QUANTUM COMPUTERS FACTORED 21 YET?
No.
Uhh…
Better catch up on some old Internet jokes…
Start here.
https://en.wikipedia.org/wiki/Betteridge%27s_law_of_headlines
https://en.wikipedia.org/wiki/Betteridge%27s_law_of_headlines
Simple logic and history tells me that the people that want to break encryption won’t be shouting their success from the rooftops and will attempt to pretend they can’t for as long as possible.
+i
+j
True. I think the most common way to break encryption is to know exploits in the libraries and hardware that provide it and/or weaknesses in the approach. That’s what recent history has shown us anyway.
There are post quantum cryptographic methods nowadays.
https://xkcd.com/538
Indeed, anyone even close to doing it will be locked in the basement of the NSA/GCHQ/MSS/etc. living like a king while the others fumble around making it look hard / like it’s not possible any time soon.
Highly likely they wouldn’t be living like kings, or even be alive at all. I understand the sentiment though.
i’m feeling mighty prescient. I think it was fall of 2000, someone came to my school to give a colloquium on quantum computing. And despite travelling across the nation giving speeches on it, they couldn’t describe it. Especially when it got to factoring, they literally waved their hands. The only thing they were confident of is that whatever it would do, it would do simultaneously across the whole problem domain. If that’s all the experts knew, then i knew there was no ‘there’ there. In fact, it’s just a special case of an analog computer working on a not-particularly-interesting set of analog formulas.
About a year before that, i saw a presentation from one of my professors about analog computing. He said that there’s a fairly boring set of formulas that you can get an instantaneous answer simply by putting point probes at specific locations on a sheet of polysilicon, and he was still looking for the killer app but he had a contract to explore it with some canadian telecom company. I thought that was so cool!
Amazing the difference when something is sold as what it is instead of sold as what it aint
The lure of money draws hackers to quantum computing like moths to a flame. The idea of breaking every PW in the universe is absolutely intoxicating to even the most casual of hackers. One day the hackers will get a hold of one of these machines, and watch out. All heck will break loose.
lol you must be script kidding!
This is a very silly take. No one is doing these physics experiments in their garage. Even if a malicious actor pulled some epic heist and got their hands on a quantum ‘computer’ from one of the orgs spending big bucks, they could not do ANY useful math with it. There is no useful tech here, just investor hype.
Read the excellent and entertaining paper [M] posted above – these expiriments are designed to look flashy, but don’t actually do anything useful.
It won’t be a hacker that throws the first stone. A nation state’s cyber agency will first use them to recover the private keys for some of the major commercial trusted certificate authorities, such as digicert, Apple, Microsoft, etc. From there they’ll start forging certificates for software signatures (likely requesting CT log signatures, too!) and deploying difficult to detect malicious updates.
While they probably won’t be able to buy a quantum computer outright, once IBM and Microsoft start offering multi-thousand qubit quantum computing as a service we can expect to see professional criminals leasing time on the machines and attempting to do the same thing.
Since we don’t know when this is going to happen, it’s prudent for the big players to deploy quantum resistant cryptography sooner rather than later.
You misspelled ‘hell’.
It’s funny you got retards like on gbatemp that think they can get a quantum computer so they can steal some more intellectual property and run illegal roms
Can’t even afford one
And where’s the working computer?
They also already created quantum resistant drm and cryptography encryption well ahead of em
I’m happy that this was posted… It reminded me that I haven’t repeated the spaced repetition learning quantum for a long time.
Al Williams write-up was great!
https://hackaday.com/2020/06/19/learn-quantum-computing-with-spaced-repetition/
That makes me pleased to here. I don’t want it! They should ask not how, but why.