Why haven't quantum computers factored 21 yet?

So how many gates are we talking to factor some "cryptographically useful" number? Is there some pathway that makes quantum computers useful this century?

> So how many gates are we talking to factor some "cryptographically useful" number?

Table 5 of [1] estimates 7 billion Toffoli gates to factor 2048 bit RSA integers.

> Is there some pathway that makes quantum computers useful this century?

The pathway to doing billions of gates is quantum error correction. [1] estimates distance 25 surface codes would be sufficient for those 7 billion gates (given the physical assumptions it lists). This amplifies the qubit count from 1400 logical qubits to a million physical noisy qubits.

Samuel Jacques had a pretty good talk at PQCrypto this year, and he speculates about timelines in it [2].

(I'm the author of this blog post and of [1].)

[1]: https://arxiv.org/pdf/2505.15917

[2]: https://www.youtube.com/watch?v=nJxENYdsB6c

How do you go from 7 billion Toffoli gates (which consist of 42 billion "two-qubit entangling gates", per the blog post) to merely 1400 logical qubits?

A gate isn't a qubit, it's an operation applied to qubits. You can do more than one operation per qubit.

it probably should be called a qop (like a flop) rather than a gate which sounds like a measure of space.