Why haven't quantum computers factored 21 yet?

Posted by ingve 8/31/2025

Why haven't quantum computers factored 21 yet?(algassert.com)

340 points | 197 commentspage 2

NooneAtAll3 8/31/2025|

> 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?

tsimionescu 8/31/2025||

The 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 8/31/2025|||

The 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.

turtletontine 8/31/2025|||

I 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.

tromp 8/31/2025||

The 115x was obtained by doing a (less plausable) large amount of optimization...

m101 8/31/2025||

Quantum 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).

dekken_ 9/1/2025||

Quantum mechanics, is not "just one thing", so to say "it is true" is somewhat wrong I think.

You are probably talking about the Copenhagen interpretation, involving superposition.

Personally, I don't think this is the final theory.

Any theory using calculus, cannot be considered discrete, so is therefore not quantized, and not possibly "physical".

Gerard 't Hooft has more to say on this if you want to hear something from a nobel laureate on the subject.

m101 9/1/2025||

Yes, agree that suggesting "true" is unclear, and in fact in science doesn't really talk about true things but rather than ability to predict the way things behave. We are still in the dark about the fundamental nature of reality. Science is still useful of course, but only insofar as it has a useful purpose. It's more like an engineering subject.

I think what I've just said foots with your calculus comment, and also a Wolfram-like interpretation is closer to "truth" and your point on discretisation.

Why do you think discretisation/quantisation is necessary for the "physical"?

What can I search for to find his comments on this subject?

dekken_ 9/1/2025||

> Why do you think discretisation/quantisation is necessary for the "physical"?

We are trying to explain, the physical reality we find outselves in, so, if the universe is fundamentally quantized, it must be discrete, as continuous math would reify infinities.

> What can I search for to find his comments on this subject?

You could check Curt Jaimungal's youtube, Hooft was on it recently.

karmakurtisaani 8/31/2025|||

This has been considered, see https://en.m.wikipedia.org/wiki/Hidden-variable_theory

m101 9/1/2025||

I'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 8/31/2025|||

Most 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”

ryankrage77 8/31/2025|||

the 'no randomness = no free will' argument is pretty common, but how does randomness ensure free will? It's still something out of our control, just it can't be predicited. Why is it any better to be a random automaton than a predictable one?

withinboredom 9/1/2025||

It's the difference between getting to choose between your favorite and least favorite meal vs. a choice between two random meals. The former is easy to predict, the latter is impossible.

AlienRobot 8/31/2025|||

Turns out we only have "free as in free beer" will.

Sorry, I was destined to make this joke before I was even born.

dhampi 8/31/2025||

Yes, Schrodinger’s equation is entirely deterministic. There is no randomness inherent in quantum mechanics. The perceived randomness only arises when we have incomplete information. (It is another matter that quantum mechanics to some extent forbids us from having perfect information.)

I mean no disrespect, but I don’t think it’s a particularly useful activity to speculate on physics if you don’t know the basic equations.

JoachimS 9/1/2025||

Does 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 9/1/2025|

it'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.

djha-skin 8/31/2025||

Does this essentially mean that the Big-O "circuitry requirements" of factoring integers using Schorr's is super polynomial?

cvoss 8/31/2025|

The 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.

taway789aaa6 8/31/2025||

> 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?

shiandow 8/31/2025||

It is phrasing mathematicians sometimes use. In this sentence 'mod 4' does not indicate an operator but denotes what number system you are in.

For instance the following are equivalent:

2 = 6 mod 4

6 = 2 mod 4

This 'mod 4' can also appear in parentheses or in some other way, but it must appear at the end. Like I said it is not an operator rather it denotes that the entire preceding statement takes place in the appropriate quotient space.

So it is not (multiplying by (4 mod 21)) but ((multiplying by 4) mod 21)

layer8 8/31/2025|||

See https://en.wikipedia.org/wiki/Modular_arithmetic. It means that the multiplication is performed modulo 21.

taway789aaa6 8/31/2025||

Thank you!

AnotherGoodName 8/31/2025|||

Fractions are under any modulus are actually representable as whole numbers (provided they don’t share factors with the modulus).

For example under mod 21 a half can actually be represented by 11. Try it. Times any even number by 11 and you’ll see you halved it.

Take any number that’s a multiple of 4 and times it by 16 under mod 21. You now have that number divided by 4.

Etc.

Absolutely nothing to do with quantum computers.

oh_my_goodness 8/31/2025||

I mean 4 is equivalent to 4 mod 21. That part's not AI slop.

JohnKemeny 8/31/2025||

I think, in fact, for every prime number p at least 5, 4 mod p is (congruent to) 4.

oh_my_goodness 8/31/2025||

Even without the restriction to primes, that feels like a pretty good guess!

freehorse 8/31/2025||

Or for less than 5.

oh_my_goodness 8/31/2025||

lol good point.

d_silin 8/31/2025||

Obligatory reference: https://scottlocklin.wordpress.com/2019/01/15/quantum-comput...

n4r9 8/31/2025|

Obligatory how? It's sort of funny but comes across as uninformed, over the top, and lacking substance.

raverbashing 8/31/2025||

My 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 8/31/2025|

It 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 8/31/2025||

Except 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

i7l 8/31/2025|||

The 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

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 8/31/2025|||

I 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.

vrighter 9/1/2025||

That gets you about 1 bit of extra precision every time you quadruple the number of parallel machines. (or rerun the computation 4x)

analog31 9/1/2025||

Yep. O(sqrt(n)) is a tough slog.

tiahura 8/31/2025|

What? I thought quantum computing was going to be factoring billion digit prime numbers in 5 years?

sincerely 8/31/2025|

Sounds like a you problem