So how many gates are we talking to factor some "cryptographically useful" number? Is there some pathway that makes quantum computers useful this century?
replies(9):
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].)