We need many error corrected qubits (meaning they have to be very stable) in order to break, say, 2,048 bits RSA. IIRC the most recent result is ~1,700 qubits. However, it's almost impossible to have so many stable qubit in any condition, so what we need are some somewhat stable qubits along with quantum error correction to "simulate" a really stable qubit. How many "real" qubit are required depends on how stable the real qubits are. So yes if the real qubits are not very stable you'll need millions of them. However, if we can improve the stability then it's possible to achieve that with maybe less than a million real qubits.
How far away is this is of course still unknown, but from what happened in last few years I think it's safe to say that the progression is real. We are no longer in the realm of "we will have a quantum computer in 50 years." We'll probably have something with 1,000 good real qubits in say 5 years. This is of course still not enough to break something like 2,048 bits RSA, but when it happens people really should migrate immediately because at that time a real breakthrough could happen suddenly. Migration is a huge work too, probably even bigger than the Y2K thing.
Note that it's not just software. It's easy to upgrade your OS and browsers, but public key cryptography is used in so many places. Smart cards are everywhere, and they are difficult to upgrade. There are also many "IoT" devices which will be difficult to upgrade (or even impossible to upgrade, as post-quantum cryptography will take more resources to run). These have to be replaced. And it's not just about cost but also about the time it takes. So basically I agree with NIST that we need to prepare now and it's probably better to start migrating in 5 years. Last time I checked NIST already narrow down the post-quantum cryptography candidates to three, so maybe we'll have a final standard soon (which means "a few years" in cryptography time).
Another thing is that with public key cryptography, the time it takes to break a key is mostly irrelevant, because a private key is supposed to be long lasting. So as long as the time takes to break it is reasonable (8 hours is short in this regard) it'll render the encryption useless.
How far away is this is of course still unknown, but from what happened in last few years I think it's safe to say that the progression is real. We are no longer in the realm of "we will have a quantum computer in 50 years." We'll probably have something with 1,000 good real qubits in say 5 years. This is of course still not enough to break something like 2,048 bits RSA, but when it happens people really should migrate immediately because at that time a real breakthrough could happen suddenly. Migration is a huge work too, probably even bigger than the Y2K thing.
Note that it's not just software. It's easy to upgrade your OS and browsers, but public key cryptography is used in so many places. Smart cards are everywhere, and they are difficult to upgrade. There are also many "IoT" devices which will be difficult to upgrade (or even impossible to upgrade, as post-quantum cryptography will take more resources to run). These have to be replaced. And it's not just about cost but also about the time it takes. So basically I agree with NIST that we need to prepare now and it's probably better to start migrating in 5 years. Last time I checked NIST already narrow down the post-quantum cryptography candidates to three, so maybe we'll have a final standard soon (which means "a few years" in cryptography time).
Another thing is that with public key cryptography, the time it takes to break a key is mostly irrelevant, because a private key is supposed to be long lasting. So as long as the time takes to break it is reasonable (8 hours is short in this regard) it'll render the encryption useless.
