12 ms·
Why haven't quantum computers factored 21 yet?
- alchemist1e9 1y agoAnd these are the same quantum computers that will eventually break ecliptic curve cryptography? Now I’m very confused.
- privatelypublic 1y agoHasn't classical already severely crippled ECC because of some mathematical Assumptions that somebody came back in 2022 and Proved were wrong?
- markusde 1y agoCould you link to any more information about this?
- kevindamm 1y agoWhich assumptions? ECDLP is still considered computationally hard, and ECC considered secure. There are invalid curve attacks and small subgroup attacks but that's a problem with key selection, not a fundamental problem with ECC. Do you have a citation?
- bitexploder 1y agoNot in general, no. It is still secure and used. There are of course attacks but those were not completely breaking
- cwmma 1y agoI believe you are thinking of "Supersingular isogeny Diffie–Hellman key exchange" or SIKE which is a post quantum encryption algorithm that was spectacularly broken a couple years ago. The math involves elliptical curves but it's different from the elliptical curve cryptography used in your browser.
- bArray 1y agoI think the idea is that it doesn’t matter if it takes billions of gates to achieve, the point is that it can do it very fast. If we thought a table sized FPGA could do it, a state actor would most definitely build one.
- lazide 1y agotheoretically The practical problem is that ‘noise’ between gates seems to increase exponentially, so practically it may actually be impossible to construct anything with more than a handful of gates for the foreseeable (possibly indefinite?) future. It’s essentially the crypto version of Fusion.
- EthanHeilman 1y agoQuantum error correction addresses this problem and we now have tech demos showing that we can build scalable QCs with surface codes [0]. [0] https://scottaaronson.blog/?p=8525 https://scottaaronson.blog/?p=8525
- lazide 1y agoCool, so we should totally be able to factor 21 (or larger numbers)…. When?
- EthanHeilman 1y agoYou brought up gate noise, there has been quite a bit of progress on that problem. > so we should totally be able to factor 21 (or larger numbers)…. When? Just because we solve one problem doesn't imply all the problems in QC are also instantly solved. I guess it does if you assume noise is the only problem and once is it solved the engineering is trivial. That is not the case. Even assuming all foundational problems have been solved, figuring out how actually engineer and also mass produce large numbers of gates, will take a while. As the article pointed out, going from 15 to 21 requires a 100x increase in gates. As the article that you posted under says: "Because of the large cost of quantum factoring numbers (that aren’t 15), factoring isn’t yet a good benchmark for tracking the progress of quantum computers. If you want to stay abreast of progress in quantum computing, you should be paying attention to the arrival quantum error correction (such as surface codes getting more reliable as their size is increased) and to architectures solving core scaling challenges (such as lost neutral atoms being continuously replaced)."
- santiagobasulto 1y agoThe potential is there, we haven't made it yet. It's the same with AI, AGI and all that. Imagine if you'd read a response from GPT-2 back in 2019, you'd also be like "and these are the same models that will eventually give us AGI".
- heyjamesknight 1y agoNot a great analogy, since there’s zero chance the kinds of model involved in GPT-2 will give us AGI.
- ACCount37 1y agoZero? Aren't you a little bit overconfident on that? Transformer LLMs already gave us the most general AI as of yet, by far - and they keep getting developed further, with a number of recent breakthroughs and milestones.
- bigfickpm 1y ago[dead]
- heyjamesknight 1y agoNo. The fundamental encoding unit of an LLM is semantic. Mapping reality into semantic space is a form of lossy compression. There are entire categories of experience that can't be properly modeled in semantic space. Even in "multimodal" models, text is still the fundamental unit of data storage and transformation between the modes. That's not the case for how your brain works—you don't see a pigeon, label it as "pigeon," and then refer to your knowledge about "pigeons". You just experience the pigeon. We have 100K years of homo sapiens thriving without language. "General Intelligence" occurs at a level above semantics.
- fmbb 1y agoImagine if you'd read a response from GPT-5 in 2025, you'd also be like "and these are the same models that will eventually give us AGI".
- z3phyr 1y ago"Is this what you can conjure Saruman?" I have a strong belief that new mathematical tools and methods can be developed that can make it "easy" to break a lot of modern cryptography primitives without ever using a quantum computer.
- griffzhowl 1y agoIf we can build a machine with enough coherent qubits, then it'll be able to break ECC. As it turns out, that's a big if, but the bigness of the if is about hardware implementation. The theory behind it is just basic quantum mechanics
- oh_my_goodness 1y agoArticle: it takes 2405 entangling gates to factor the number 21.
- wongarsu 1y agoIn many applications you are concerned about data you encrypt today still being secure 20 years from now. Especially if your threat model includes a malicious actor holding on to data in hopes of decrypting it later. From the article it sounds like we will still be safe for 20+ years. On the other hand 15 was just extraordinarily easy, progress after 21 will be much quicker. And we never know which breakthroughs might come in the next decades that speed up progress.
- oh_my_goodness 1y ago"progress after 21 will be much quicker" Can you provide a quick verification for that?
- wongarsu 1y agoThe article lists three reasons why 21 is so much harder than 15. Mostly that with 15 most of the required conditional multiplications are multiplications by 1 and the remaining multiplication can be done with cheap shifts because it's a multiplication by a power of 2 modulo 15 (which is one less than a power of two). But 22 and 24 are in the same boat as 21 here. All three of them require computing only factors that are not one, all three are not one less than a factor of 2. You need slightly more multiplications (and thus more gates) as the numbers get larger, but that only grows linearly. Maybe the conditional multiplications required get slightly more expensive to implement, but I wouldn't expect a 100x cost blowup from that. Error correction is still an issue, potentially making a linear complexity increase quadratic, but qubit counts in quantum computers also increase at an exponential rate
- oh_my_goodness 1y ago23 and 29 are prime.
- wongarsu 1y agoThat's what I get for not enough coffee. Same holds for 22 and 24 though
- Mistletoe 1y agoThis is the reality a million clickbait fearmongering articles won’t tell you. And pr machines for quantum computing companies won’t either.
- taway789aaa6 1y ago> Third, notice that the only remaining multiplication is a multiplication by 4. Because 15 is one less than a power of 2, multiplying by 2 modulo 15 can be implemented using a circular shift. A multiplication by 4 is just two multiplications by 2, so it can also be implemented by a circular shift. This is a very rare property for a modular multiplication to have, and here it reduces what should be an expensive operation into a pair of conditional swaps. > Aside: multiplication by 16 mod 21 is the inverse of multiplying by 4 mod 21, and the circuits are reversible, so multiplying by 16 uses the same number of Toffolis as multiplying by 4. I couldn't really find anything explaining the significance of this. The only info I found said that "4 mod 21 = 4" (but I don't know if it was AI slop or not). Is "multiplying by 4 mod 21" something distinct to quantum computing?
- oh_my_goodness 1y agoI mean 4 is equivalent to 4 mod 21. That part's not AI slop.
- JohnKemeny 1y agoI think, in fact, for every prime number p at least 5, 4 mod p is (congruent to) 4.
- oh_my_goodness 1y agoEven without the restriction to primes, that feels like a pretty good guess!
- freehorse 1y agoOr for less than 5.
- oh_my_goodness 1y agolol good point.
- owlbite 1y agoSo how many gates are we talking to factor some "cryptographically useful" number? Is there some pathway that makes quantum computers useful this century?
- dsclough 1y agoSaw this earlier: https://x.com/adamscochran/status/1962148452072124879?s=46 https://x.com/adamscochran/status/1962148452072124879?s=46 As a layman the pathway seems to exist behind multiple massive materials science breakthroughs
- andrewflnr 1y agoHow is it that we need to build logical qubits out of physical qubits for error correction purposes, but then still need to blow out our logic qubit numbers for error correction purposes, again? It seems like there's something missing from this explanation, at least.
- adgjlsfhk1 1y agothe blow-up is in physical qbits
- TacticalCoder 1y ago[dead]
- tripplyons 1y agoNot sure about the gate count, but if you look at the number of logical qubits required, we are still very far away from factoring numbers that traditional computing has already factored like the 829-bit RSA-250 number.
- Legend2440 1y agoRealistically, you want millions to billions of qubits to compete with classical computers that already have trillions of transistors.
- AceJohnny2 1y agoWhat does this mean about the size (and thus feasibility) of a circuit required to factor a cryptographically interesting number, say, to be generous, RSA1024?
- add-sub-mul-div 1y ago"(Quick aside: the amount of optimization that has gone into this factoring-21 circuit is probably unrepresentative of what would be possible when factoring big numbers. I think a more plausible amount of optimization would produce a circuit with 500x the cost of the factoring-15 circuit… but a 100x overhead is sufficient to make my point. Regardless, special thanks to Noah Shutty for running expensive computer searches to find the conditional-multiplication-by-4-mod-21 subroutine used by this circuit.)"
- Davidzheng 1y agoOff topic, but are cryptographers convinced that on the new gigawatt data centers RSA1024 is infeasible to factor? I gather that the fastest known algorithms are still too slow to factor it in reasonable time. But is consensus that there will not be improvements to these algorithms in near future?
- deleted 1y ago[deleted]
- raverbashing 1y agoMy belief in achieving actual quantum computing is going down as noise in qbits goes up Digital computers were much easier than that. Make it smaller, make a larger number of it, and you're set. Quantum computers complexity goes up with ~ n^2 (or possibly ~ e^n) where n is the number of qbits At the same time, things like d-wave might be the most 'quantum' we might get in the practical sense
- analog31 1y agoIt turns out that error correction was easy on digital computers, and was essentially a solved problem early in their development. In fact, "noise immunity" is arguably the defining feature of a digital system. And error correction can happen at each gate, since there's no reason to propagate an indeterminate number.
- Der_Einzige 1y agoExcept quantum error correction algorithms that are good don’t exist and probably theoretically never can exist: https://spectrum.ieee.org/the-case-against-quantum-computing https://spectrum.ieee.org/the-case-against-quantum-computing
- _bypa 1y agoThe current best one- and two-gate errors are well below 0.01% and going down with every generation of chips. See: https://ianreppel.org/quantum.html https://ianreppel.org/quantum.html There are no theoretical reasons QEC can't exist. In fact it already does. Is it already good enough for universal fault tolerance? No. But then again no one said it would. We are slowly getting closer every year. In his book, Dyakonov offers zero solid reasons other than "it's hard" and thus likely not possible. That's just an opinion.
- analog31 1y agoI took a QC course, and have done some reading, but am hardly an expert. But my impression has been: "This is analog computation." To reinforce the similarity, the error level of analog computers can be improved by running many of them in parallel.
- tiahura 1y agoWhat? I thought quantum computing was going to be factoring billion digit prime numbers in 5 years?
- sincerely 1y agoSounds like a you problem
- api 1y agoIt’s worth noting that the reason we are deploying PQ crypto is not that we are 100% convinced QC is coming soon. It may or may not depending on how development goes. The goal of cryptography is to make something as close to theoretically unbreakable as possible. That means even theoretical vulnerabilities are taken seriously. For ECC and RSA and related algorithms we have a theoretical and physically plausible pathway toward a practical machine that could break them. That means many cryptographers consider them theoretically broken even if such a machine does not exist and may not exist for a long time. The math works even if we can’t build it yet. So it’s considered prudent to go ahead and upgrade now while no QC exists. That way if some major advance does arrive we are ready. Nobody’s talking seriously about replacing SHA2, AES, ChaCha, etc because there is no physically plausible theoretically valid path to a machine that can break these in, say, less than many millions of years. AFAIK there is no proof that such a path does not exist but nobody has found one, hence they are considered unbroken. Note that cryptography is not the only or even the most useful application of QC. Things like physical stimulation of quantum systems, protein folding, machine learning, etc. could be more useful. Like digital computers there’s probably a ton of uses we don’t know about because we need to tinker with the machine to figure them out.
- leeoniya 1y ago> Things like physical stimulation of quantum systems, protein folding, machine learning, etc. could be more useful is there still more to do in protein folding after AlphaFold? https://www.isomorphiclabs.com/articles/alphafold-3-predicts-the-structure-and-interactions-of-all-of-lifes-molecules https://www.isomorphiclabs.com/articles/alphafold-3-predicts...
- api 1y agoThere’s a difference between good AI predictions and theoretically perfect QC computations. The AI estimates while the QC will give you the answer, full stop. The latter could be relied upon more strongly. It could also generate infinite training data to make much better models. QC might be directly applicable to AI training too. It may be possible to compute the optimal model over a data set in linear time. It could allow training that is faster and consumes a tiny fraction of the energy current brute force methods need.
- d_silin 1y agoObligatory reference: https://scottlocklin.wordpress.com/2019/01/15/quantum-computing-as-a-field-is-obvious-bullshit/ https://scottlocklin.wordpress.com/2019/01/15/quantum-comput...
- n4r9 1y agoObligatory how? It's sort of funny but comes across as uninformed, over the top, and lacking substance.
- NooneAtAll3 1y ago> I think a more plausible amount of optimization would produce a circuit with 500x the cost of the factoring-15 circuit I don't get this part If author already produced "115x", how can optimizations make it worse?
- tromp 1y agoThe 115x was obtained by doing a (less plausable) large amount of optimization...
- turtletontine 1y agoI think the idea is the minimal implementation will be unstable and unreliable. I don’t know the details, but there’s much work and thought on quantum error correcting qubits - where you hook up N qubits in a clever way to function as one very stable qubit. Terms such as “decoherence time” make appearances. You can imagine this quickly expands into an awful lot of qubits.
- tsimionescu 1y agoThe point was that the amount of optimization work that went into making the circuit for factoring 21 only ~100x larger than the one for factoring 15 is not feasible for larger numbers. So, the general rule should be that you need ~500x more gates for a similar increase in the number to be factored, not just ~100x.
- Strilanc 1y agoThe more plausible amount of optimization is less optimization. Or, more accurately, the benefits of optimization at large sizes is expected to be less beneficial than it was for the N=21 circuit.
- BitsAndObjects 1y agoI enjoyed the typo in "error corection" (sic).
- avhon1 1y agoThe linked paper "Replication of Quantum Factorisation Records with an 8-bit Home Computer, an Abacus, and a Dog" is a good read! https://eprint.iacr.org/2025/1237.pdf https://eprint.iacr.org/2025/1237.pdf
- tim333 1y agoThat was entertaining.
- m101 1y agoQuantum mechanics is "true" insofar as it's useful for some purpose. Until then it's a theory and the jury is still out. Randomness is something which I feel is a pretty weird phenomenon. I am definitely one of those 'God doesn't play with dice' types. Randomness is also something that we call things when actually it's random from a subjective perspective. If we knew more about a system the randomness just falls away. E.g. if we knew the exact physical properties of a dice roll we could probably predict it better than random. What if it's the case that quantum mechanics is similar. I.e. that what we think of as randomness isn't really randomness but only appears that way to the best of what we can observe. If this is the case, and if our algorithms rely on some sort of genuine randomness inherent in the universe, then doesn't that suggest there's a problem? Perhaps part of the errors we see in quantum mechanics arise from just something fundamental to the universe being different to our model. I don't think this is that far fetched given the large holes that our current understanding of physics have as to predicting the universe. It just seems that in the realm of quantum mechanics this isn't the case, apparently because experiments have verified things. However, I think there really is something in the proof being in the pudding (provide a practical use case).
- karmakurtisaani 1y agoThis has been considered, see https://en.m.wikipedia.org/wiki/Hidden-variable_theory https://en.m.wikipedia.org/wiki/Hidden-variable_theory
- m101 1y agoI've heard of it but I'm not very familiar, or have a deep understanding of it. I buy into things like Wolfram physics for explaining how the universe actually works, with equations/calculus being limited to approximations to an error in measurement. The hidden variable theory seems to mostly covers physics unlike what Wolfram covers, so it's useful for a purpose but it still seems to be going down a similar rabbit hole to where normal physics ends up.
- withinboredom 1y agoMost people don’t want to go down this hole. In the end, it means we might not have free will if there isn’t any randomness… But if you are up for an existential crisis, just google “hidden variable theories”
- hulitu 1y ago> Why haven't quantum computers factored 21 yet? They tried. But because they know exactly the question, they cannot give a precise answer. /s
- amelius 1y agoThat's ok as long as the VCs don't know the answer either /s
- deleted 1y ago[deleted]
- djha-skin 1y agoDoes this essentially mean that the Big-O "circuitry requirements" of factoring integers using Schorr's is super polynomial?
- cvoss 1y agoThe 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.
- hvenev 1y agoI wonder when quantum computers will be able to target post-quantum RSA [1]. Normal RSA operations (key generation, encryption, decryption) have an asymptotic advantage over Shor's algorithm, so it is not unreasonable to just use large enough keys. The advantage is similar to Merkle's puzzles [2], with the added bonus that the attacker also needs to run their attack on a quantum computer. A while ago I generated a gigabit RSA public key. It is available at [3]. From what I remember, the format is: 4-byte little-endian key size in bytes, then little-endian key, then little-endian inverse of key mod 256**bytes. The public exponent is 3. [1] https://eprint.iacr.org/2017/351.pdf https://eprint.iacr.org/2017/351.pdf [2] https://dl.acm.org/doi/pdf/10.1145/359460.359473 https://dl.acm.org/doi/pdf/10.1145/359460.359473 [3] https://hristo.venev.name/pqrsa.pub https://hristo.venev.name/pqrsa.pub
- BoppreH 1y agoPost-Quantum RSA is clearly a joke from djb, to have a solid reply when people ask "can't we just use bigger keys"?. It has a 1-terabyte RSA key taking 100 hours to perform a single encryption. And by design it should be beyond the reach of quantum computers.
- vrighter 1y agoBecause they haven't actually factored any other smaller number yet. If your program has a compilation process that requires you to already know the answer to the problem you're trying to solve, then what they did was not factorization, but "print 3" with extra steps.
- patrakov 1y agoThe article, if examined by a non-specialist like me, seems to contain an answer to this concern at the end: > There are papers that claim to have factored 21 with a quantum computer. For example, here’s one from 2021 [1]. But, as far as I know, all such experiments are guilty of using optimizations that imply the code generating the circuit had access to information equivalent to knowing the factors. [1] https://arxiv.org/abs/2103.13855 https://arxiv.org/abs/2103.13855
- DebtDeflation 1y agoThe article claims that 15 was done without precompilation (in the 2015 experiment but not the 2001 experiment), but only because 15 is a very unique number (after decomposition, only the last multiplication has to be performed because all the previous multiplications involve multiplying by 1). That said, we are REALLY far off from having a useful quantum computer. Jensen was probably being conservative when he said 20-30 years away, hence the immediate pressure he received form the investor community to reverse his statement followed by the flood of ridiculous press releases from the usual companies claiming to be 2-3 years away.
- aaron695 1y ago[dead]
- fsckboy 1y agoderiving arithmetic from lambda calculus is not "arithmetic with extra steps"... not sure what I mean by that, but seems like that implies there is arithmetic without extra steps, then you just print the answer
- brazzy 1y agoI recently talked to a guy who works on quantum computing research. He said that factoring and cryptography applications are red herrings. It's not what most people in the field are working on. The practical application lies in simulating processes where quantum effects are actually directly relevant, such as quantum chemistry: https://en.wikipedia.org/wiki/Quantum_chemistry https://en.wikipedia.org/wiki/Quantum_chemistry
- Nevermark 1y agoI wonder if the circuit could be modularized into a quantum ALU. Where many of the otherwise identical components in the original layout, couldn't just be arranged as operations time, over a reduced number of distinct components. Most digital algorithms would explode in terms of hardware needed, for increasing N, if we didn't distribute that computation in time, as well as across elements.
- cubefox 1y agoIs this the same idea as using universal Turing machines (CPUs that can execute software) rather than conventional fixed-function Turing machines (ASICs/FPGAs)?
- adgjlsfhk1 1y agounfortunately this is kind of fundamentally impossible. the whole power of quantum computation is that big quantum computers can do computation on a massive state space "for free". that benefit only exists if you have enough qbits to hold the state space.
- Nevermark 1y agoHolding the state space and iteratively transforming it (in a reversible way, so the state space is preserved), seem like a solution to that. This would still require more hardware than digital circuits (which can be made reversible for energy efficiency, but that is rarely done). While still reducing the number of operation components, and reusing them.
- JoachimS 1y agoDoes this mean in a general sense there are numbers that are harder to factor, or is it due to constraints? That some keys will be much harder to crack? If so, how can we know beforehand?
- adgjlsfhk1 1y agoit's more that there are numbers that are easier to factor (e.g. 2^n-1). almost all numbers once you get past the tiny numbers are about the same.