So how many gates are we talking to factor some "cryptographically useful" number? Is there some pathway that makes quantum computers useful this century?
Ah - this helped me understand the numbers in quantum computing a little more clearly. I had been under the impression (based on my naive interpretation of the naming) that the number of qubits in a quantum processor might be something analogous to the number of bits of register state in a regular CPU; that qubits should be thought of more as analogous to transistors or maybe even gates makes it a little clearer why you need so many more qubits to perform more complex operations.
the difference is that you need millions of 1 qbits to factor rsa 4096, but you only need 10s of millions to factor rsa 32k. qbits and quantum time scale almost linearly with factor size, but super-polynomially for regular computers