5 ms·

See https://bas.westerbaan.name/notes/2026/04/02/factoring.html https://bas.westerbaan.name/notes/2026/04/02/factoring.html and https://scottaaronson.blog/?p=96

See https://bas.westerbaan.name/notes/2026/04/02/factoring.html https://bas.westerbaan.name/notes/2026/04/02/factoring.html and https://scottaaronson.blog/?p=9665#comment-2029013 https://scottaaronson.blog/?p=9665#comment-2029013 which are linked to in the first section of the article. > Sure, papers about an abacus and a dog are funny and can make you look smart and contrarian on forums. But that’s not the job, and those arguments betray a lack of expertise. As Scott Aaronson said: > Once you understand quantum fault-tolerance, asking “so when are you going to factor 35 with Shor’s algorithm?” becomes sort of like asking the Manhattan Project physicists in 1943, “so when are you going to produce at least a small nuclear explosion?” To summarize, the hard part of scalable quantum computation is error correction. Without it, you can't factorize essentially anything. Once you get any practical error correction, the distance between 32-bit RSA and 2048-bit RSA is small. Similarly to how the hard part is to cause a self-sustaining fissile chain reaction, and once you do making the bomb bigger is not the hard part. This is what the experts know, and why they tell us of the timelines they do. We'd do better not to dismiss them by being smug about our layperson's understanding of their progress curve.

phicoh 6mo ago
The thing is, producing the right isotopes of uranium is mostly a linear process. It goes faster as you scale up of course, but each day a reactor produces a given amount. If you double the number of reactors you produce twice as much, etc. There is no such equivalent for qubits or error correction. You can't say, we produce this much extra error correction per day so we will hit the target then and then. There is also something weird in the graph in https://bas.westerbaan.name/notes/2026/04/02/factoring.html https://bas.westerbaan.name/notes/2026/04/02/factoring.html. That graph suggests that even with the best error correction in the graph, it is impossible to factor RSA-4 with less then 10^4 qubits. Which seems very odd. At the same time, Scott Aaronson wrote: "you actually can now factor 6- or 7-digit numbers with a QC". Which in the graph suggests that error rate must be very low already or quantum computers with an insane number of qubits exist. Something doesn't add up here.
- adgjlsfhk1 6mo ago
  You can already factor a 6 digit number with a QC, but not with an algorithm that scales polynomially. The graph linked is for optimized variants of Shor's algorithm.
- FiloSottile 6mo ago
  We are stretching the metaphor thin, but surely the progress towards an atomic bomb was not measured only in uranium production, in the same way that the progress towards a QC is not measured only in construction time of the machine. At the theory level, there were only theories, then a few breakthroughs, then some linear production time, then a big boom. > Something doesn't add up here. Please consider it might be your (and my) lack of expertise in the specific sub-field. (I do realize I am saying this on Hacker News.)
  - vlovich123 6mo ago
    Not only, but a huge challenge was manufacturing enough fuel and was the real limiting part. They were working out hard science and engineering but more fuel definitely == bigger bomb in a very real way and it is quite linear because E=mc^2. And it was in many ways the bottleneck for the bombs - it literally guided how big they made the first bomb and the US manufactured enough for 3 - 1 test, 2 to drop
- Strilanc 6mo ago
  > That graph suggests that even with the best error correction in the graph, it is impossible to factor RSA-4 with less then 10^4 qubits. Which seems very odd. It's because the plot is assuming the use of error correction even for the smallest cases. Error correction has minimum quantity and quality bars that you must clear in order for it to work at all, and most of the cost of breaking RSA4 is just clearing those bars. (You happen to be able to do RSA4 without error correction, as was done in 2001 [0], but it's kind of irrelevant because you need error correction to scale so results without it are on the wrong trendline. That's even more true for the annealing stuff Scott mentioned, which has absolutely no chance of scaling.) You say you don't see the uranium piling up. Okay. Consider the historically reported lifetimes of classical bits stored using repetition codes on the UCSB->Google machines [1]. In 2014 the stored bit lived less than a second. In 2015 it lived less than a second. 2016? Less than a second. 2017? 2018? 2019? 2020? 2021? 2022? Yeah, less than a second. And this may not surprise you but yes, in 2023, it also lived less than a second. Then, in 2024... kaboom! It's living for hours [4]. You don't see the decreasing gate error rates [2]? The increasing capabilities [3]? The ever larger error correcting code demonstrations [4]? The front-loaded costs and exponential returns inherent to fault tolerance? TFA is absolutely correct: the time to start transitioning to PQC is now. [0]: https://www.nature.com/articles/414883a https://www.nature.com/articles/414883a [1]: https://algassert.com/assets/2025-12-24-qec-foom/plot-half-life-linear.png https://algassert.com/assets/2025-12-24-qec-foom/plot-half-l... (from https://algassert.com/post/2503 https://algassert.com/post/2503 ) [2]: https://arxiv.org/abs/2510.17286 https://arxiv.org/abs/2510.17286 [3]: https://www.nature.com/articles/s41586-025-09596-6 https://www.nature.com/articles/s41586-025-09596-6 [4]: https://www.nature.com/articles/s41586-024-08449-y https://www.nature.com/articles/s41586-024-08449-y
octoberfranklin 6mo ago
> produce at least a small nuclear explosion The Manhattan Project scientists actually did this before anybody broke ground at Los Alamos. It was called the Chicago Pile. And if the control rods were removed and the SCRAM disabled, it absolutely would have created a "small nuclear explosion" in the middle of a major university campus. Given the level of hype and how long it's been going on, I think it's totally reasonable for the wider world to ask the quantum crypto-breaking people to build a Chicago Pile first. https://en.wikipedia.org/wiki/Chicago_Pile-1 https://en.wikipedia.org/wiki/Chicago_Pile-1
- tptacek 6mo ago
  What? No. No matter what anybody did with the Chicago Pile, it would never have produced a small version of a nuclear detonation.
- FiloSottile 6mo ago
  TIL about the Chicago Pile! (I don't know enough about the physics to tell if it could have indeed exploded.) > On 2 December 1942 https://en.wikipedia.org/wiki/Chicago_Pile-1 https://en.wikipedia.org/wiki/Chicago_Pile-1 > on July 16, 1945 https://en.wikipedia.org/wiki/Trinity_(nuclear_test) https://en.wikipedia.org/wiki/Trinity_(nuclear_test) Two years and a half. This is still a good metaphor for "once you can make a small one, the large one is not far at all."
- rcxdude 6mo ago
  A meltdown is not a nuclear explosion. It's not even what happens if you fail to make a nuke go off properly.
- defrost 6mo ago
  In truth the Chicago Pile crowd were all about power generation and didn't think it was feasible to make a nuclear bomb .. ( Not impossible, more strictly "beyond reach" economically and processing wise, operating on over estimates of the effort and approach ) They ignored letters from Albet Einstein on the topic, they ignored or otherwise disregarded several letters from the Canadian / British MAUD Committee / Tube Alloys group and it took a personal visit from an Australian for them to sit up and take note that such a thing was actually within reach .. although it'd take some man power and a few challenges along the way. * https://en.wikipedia.org/wiki/MAUD_Committee https://en.wikipedia.org/wiki/MAUD_Committee is one place to start on all that.
vlovich123 6mo ago
I’ve worked with Bas. I respect him, but he is definitely a QC maximalist in a way. At the very least he believes that caution suggests the public err on the side of believing we will build them. The actual challenge is we still don’t know if we can build QC circuits that factorize faster than classical both because the amount of qubits has gone from ridiculously impossible to probably still impossible AND because we still don’t know how to build circuits that have enough qbits to break classical algorithms larger or faster than classical computers, which if you’re paying attention to the breathless reporting would give you a very skewed perception of where we’re at. It’s also easy to deride your critics as just being contrarian on forums, but the same complaint happens to distract from the actual lack of real forward progress towards building a QC. We’ve made progress on all kinds of different things except for actually building a QC that can scale to actually solve non trivial problems . It’s the same critique as with fusion energy with the sole difference being that we actually understand how to build a fusion reactor, just not one that’s commercially viable yet, and fusion energy would be far more beneficial than a QC at least today. There’s also the added challenge that crypto computers only have one real application currently which is as a weapon to break crypto. Other use cases are generally hand waved as “possible” but unclear they actually are (ie you can’t just take any NP problem and make it faster even if you had a compute and even traveling salesman is not known to be faster and even if it is it’s likely still not economical on a QC). Speaking of experts, Bas is a cryptography expert with a specialty in QC algorithms, not an expert in building QC computers. Scott Aronson is also well respected but he also isn’t building QC machines, he’s a computer scientist who understands the computational theory, but that doesn’t make him better as a prognosticator if the entire field is off on a fool’s errand. It just means he’s better able to parse and explain the actual news coming from the field in context.
- bwesterb 6mo ago
  Don't recognise you from your username, but thanks for the respect. (Update: ah, Vitali! Nice to hear from you.) If you look back at my writing from 2025 and earlier, I'm on the conservative end of Q-day estimates: 2035 or later. My primary concern then is that migrations take a lot of time: even 2035 is tight. I'm certainly not an expert on building quantum computers, but what I hear from those that are worries me. Certainly there are open challenges for each approach, but that list is much shorter now than it was a few years ago. We're one breakthrough away from a CRQC.
littlestymaar 6mo ago
> Similarly to how the hard part is to cause a self-sustaining fissile chain reaction, and once you do making the bomb bigger is not the hard part. I don't like this analogy very much, because in practice making a nuclear reaction is much, much easier than making a nuclear bomb. You don't need any kind of enrichment or anything, just a big enough pile of natural uranium and graphite [1]. Making a bomb on the other hand, required an insane amount of engineering: from doing isotope separation to enrich U235 to an absurd level (and / or, extract plutonium from the wastes of a nuclear reactor) to designing a way to concentrate a beyond critical mass of fissile element. The Manhattan project isn't famous without reason, it was an unprecedented concerted effort that wouldn't have happened remotely as quickly in peacetime. [1]: https://en.wikipedia.org/wiki/Chicago_Pile-1 https://en.wikipedia.org/wiki/Chicago_Pile-1

phicoh 6mo ago

The thing is, producing the right isotopes of uranium is mostly a linear process. It goes faster as you scale up of course, but each day a reactor produces a given amount. If you double the number of reactors you produce twice as much, etc. There is no such equivalent for qubits or error correction. You can't say, we produce this much extra error correction per day so we will hit the target then and then. There is also something weird in the graph in https://bas.westerbaan.name/notes/2026/04/02/factoring.html https://bas.westerbaan.name/notes/2026/04/02/factoring.html. That graph suggests that even with the best error correction in the graph, it is impossible to factor RSA-4 with less then 10^4 qubits. Which seems very odd. At the same time, Scott Aaronson wrote: "you actually can now factor 6- or 7-digit numbers with a QC". Which in the graph suggests that error rate must be very low already or quantum computers with an insane number of qubits exist. Something doesn't add up here.

adgjlsfhk1 6mo ago
You can already factor a 6 digit number with a QC, but not with an algorithm that scales polynomially. The graph linked is for optimized variants of Shor's algorithm.
FiloSottile 6mo ago
We are stretching the metaphor thin, but surely the progress towards an atomic bomb was not measured only in uranium production, in the same way that the progress towards a QC is not measured only in construction time of the machine. At the theory level, there were only theories, then a few breakthroughs, then some linear production time, then a big boom. > Something doesn't add up here. Please consider it might be your (and my) lack of expertise in the specific sub-field. (I do realize I am saying this on Hacker News.)
- vlovich123 6mo ago
  Not only, but a huge challenge was manufacturing enough fuel and was the real limiting part. They were working out hard science and engineering but more fuel definitely == bigger bomb in a very real way and it is quite linear because E=mc^2. And it was in many ways the bottleneck for the bombs - it literally guided how big they made the first bomb and the US manufactured enough for 3 - 1 test, 2 to drop
Strilanc 6mo ago
> That graph suggests that even with the best error correction in the graph, it is impossible to factor RSA-4 with less then 10^4 qubits. Which seems very odd. It's because the plot is assuming the use of error correction even for the smallest cases. Error correction has minimum quantity and quality bars that you must clear in order for it to work at all, and most of the cost of breaking RSA4 is just clearing those bars. (You happen to be able to do RSA4 without error correction, as was done in 2001 [0], but it's kind of irrelevant because you need error correction to scale so results without it are on the wrong trendline. That's even more true for the annealing stuff Scott mentioned, which has absolutely no chance of scaling.) You say you don't see the uranium piling up. Okay. Consider the historically reported lifetimes of classical bits stored using repetition codes on the UCSB->Google machines [1]. In 2014 the stored bit lived less than a second. In 2015 it lived less than a second. 2016? Less than a second. 2017? 2018? 2019? 2020? 2021? 2022? Yeah, less than a second. And this may not surprise you but yes, in 2023, it also lived less than a second. Then, in 2024... kaboom! It's living for hours [4]. You don't see the decreasing gate error rates [2]? The increasing capabilities [3]? The ever larger error correcting code demonstrations [4]? The front-loaded costs and exponential returns inherent to fault tolerance? TFA is absolutely correct: the time to start transitioning to PQC is now. [0]: https://www.nature.com/articles/414883a https://www.nature.com/articles/414883a [1]: https://algassert.com/assets/2025-12-24-qec-foom/plot-half-life-linear.png https://algassert.com/assets/2025-12-24-qec-foom/plot-half-l... (from https://algassert.com/post/2503 https://algassert.com/post/2503 ) [2]: https://arxiv.org/abs/2510.17286 https://arxiv.org/abs/2510.17286 [3]: https://www.nature.com/articles/s41586-025-09596-6 https://www.nature.com/articles/s41586-025-09596-6 [4]: https://www.nature.com/articles/s41586-024-08449-y https://www.nature.com/articles/s41586-024-08449-y

octoberfranklin 6mo ago

> produce at least a small nuclear explosion The Manhattan Project scientists actually did this before anybody broke ground at Los Alamos. It was called the Chicago Pile. And if the control rods were removed and the SCRAM disabled, it absolutely would have created a "small nuclear explosion" in the middle of a major university campus. Given the level of hype and how long it's been going on, I think it's totally reasonable for the wider world to ask the quantum crypto-breaking people to build a Chicago Pile first. https://en.wikipedia.org/wiki/Chicago_Pile-1 https://en.wikipedia.org/wiki/Chicago_Pile-1

tptacek 6mo ago
What? No. No matter what anybody did with the Chicago Pile, it would never have produced a small version of a nuclear detonation.
FiloSottile 6mo ago
TIL about the Chicago Pile! (I don't know enough about the physics to tell if it could have indeed exploded.) > On 2 December 1942 https://en.wikipedia.org/wiki/Chicago_Pile-1 https://en.wikipedia.org/wiki/Chicago_Pile-1 > on July 16, 1945 https://en.wikipedia.org/wiki/Trinity_(nuclear_test) https://en.wikipedia.org/wiki/Trinity_(nuclear_test) Two years and a half. This is still a good metaphor for "once you can make a small one, the large one is not far at all."
rcxdude 6mo ago
A meltdown is not a nuclear explosion. It's not even what happens if you fail to make a nuke go off properly.
defrost 6mo ago
In truth the Chicago Pile crowd were all about power generation and didn't think it was feasible to make a nuclear bomb .. ( Not impossible, more strictly "beyond reach" economically and processing wise, operating on over estimates of the effort and approach ) They ignored letters from Albet Einstein on the topic, they ignored or otherwise disregarded several letters from the Canadian / British MAUD Committee / Tube Alloys group and it took a personal visit from an Australian for them to sit up and take note that such a thing was actually within reach .. although it'd take some man power and a few challenges along the way. * https://en.wikipedia.org/wiki/MAUD_Committee https://en.wikipedia.org/wiki/MAUD_Committee is one place to start on all that.

vlovich123 6mo ago

I’ve worked with Bas. I respect him, but he is definitely a QC maximalist in a way. At the very least he believes that caution suggests the public err on the side of believing we will build them. The actual challenge is we still don’t know if we can build QC circuits that factorize faster than classical both because the amount of qubits has gone from ridiculously impossible to probably still impossible AND because we still don’t know how to build circuits that have enough qbits to break classical algorithms larger or faster than classical computers, which if you’re paying attention to the breathless reporting would give you a very skewed perception of where we’re at. It’s also easy to deride your critics as just being contrarian on forums, but the same complaint happens to distract from the actual lack of real forward progress towards building a QC. We’ve made progress on all kinds of different things except for actually building a QC that can scale to actually solve non trivial problems . It’s the same critique as with fusion energy with the sole difference being that we actually understand how to build a fusion reactor, just not one that’s commercially viable yet, and fusion energy would be far more beneficial than a QC at least today. There’s also the added challenge that crypto computers only have one real application currently which is as a weapon to break crypto. Other use cases are generally hand waved as “possible” but unclear they actually are (ie you can’t just take any NP problem and make it faster even if you had a compute and even traveling salesman is not known to be faster and even if it is it’s likely still not economical on a QC). Speaking of experts, Bas is a cryptography expert with a specialty in QC algorithms, not an expert in building QC computers. Scott Aronson is also well respected but he also isn’t building QC machines, he’s a computer scientist who understands the computational theory, but that doesn’t make him better as a prognosticator if the entire field is off on a fool’s errand. It just means he’s better able to parse and explain the actual news coming from the field in context.

bwesterb 6mo ago
Don't recognise you from your username, but thanks for the respect. (Update: ah, Vitali! Nice to hear from you.) If you look back at my writing from 2025 and earlier, I'm on the conservative end of Q-day estimates: 2035 or later. My primary concern then is that migrations take a lot of time: even 2035 is tight. I'm certainly not an expert on building quantum computers, but what I hear from those that are worries me. Certainly there are open challenges for each approach, but that list is much shorter now than it was a few years ago. We're one breakthrough away from a CRQC.

littlestymaar 6mo ago

> Similarly to how the hard part is to cause a self-sustaining fissile chain reaction, and once you do making the bomb bigger is not the hard part. I don't like this analogy very much, because in practice making a nuclear reaction is much, much easier than making a nuclear bomb. You don't need any kind of enrichment or anything, just a big enough pile of natural uranium and graphite [1]. Making a bomb on the other hand, required an insane amount of engineering: from doing isotope separation to enrich U235 to an absurd level (and / or, extract plutonium from the wastes of a nuclear reactor) to designing a way to concentrate a beyond critical mass of fissile element. The Manhattan project isn't famous without reason, it was an unprecedented concerted effort that wouldn't have happened remotely as quickly in peacetime. [1]: https://en.wikipedia.org/wiki/Chicago_Pile-1 https://en.wikipedia.org/wiki/Chicago_Pile-1