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].)
The result is that, if you keep adding qubits that can be operated on in parallel, Shor's algorithm basically just keeps getting faster and faster and faster. The energy cost doesn't go down, and the number of qubits required becomes frankly absurd, but the time can go really really low.