The temporal aspect of breaking encryption with a quantum computer
You've probably heard someone claim before that a sufficiently large quantum computer will be able to break a sufficiently weak encryption standard within the next few decades. And this is perfectly true in theory, but in practice it requires a large number of assumptions.
When is a quantum computer a threat to encryption?
To begin, we need to define what we mean by "breaking encryption." Does it mean being able to decrypt just one message? I could start guessing 1024-bit primes at random until I get lucky and find one that decrypts an RSA-encrypted message, but that doesn't mean I've broken RSA-1024. There are still a myriad of other messages that I haven't been able to decrypt. Additionally, each one will take a random amount of time to decrypt because their prime factors are generated in a pseudorandom manner. So what we actually mean by "a quantum computer will break existing encryption" is "a quantum computer will, on average, decrypt messages within a short amount of time."
But now we need to define what qualifies as a short amount of time. Days? Hours? Minutes? This question does not have a single answer because it depends on how that encrypted information is being used. For example, suppose I send a WhatsApp message to my friend that says, "I am leaving the house now and won't be back for 4 hours." If Eve is a quantum-capable burglar intent on robbing my house, then she would need a computer large enough to decrypt that message (assuming she intercepts it) in less than 4 hours or else she will miss her window of opportunity. This is in stark contrast to information that may be sensitive for decades, such as the blueprints for the F-35. Let's call this quantity information lifetime. In this scenario, the information lifetime of the message I send my friend is 4 hours. This brings us to the main point: Eve's quantum computer is only a threat to encryption if the average time it takes her to decrypt a given message is less than the information lifetime for that message.
How large does a quantum computer need to be?
Now let's talk about the average time it takes to decrypt a message. Shown in Table 4.1, the National Academies of Sciences published a report in 2018 on the average time it takes to decrypt a number of commonly used algorithms.
The first thing that sticks out to me is how large the number of logical qubits needs to be in order to break an RSA-encrypted message within hours. For reference, the largest quantum computers today are near 80ish qubits. We are clearly still at least several decades away from reaching a point where even RSA-4096 is no longer secure for daily communications.
The second thing that sticks out to me are the footnotes. The numbers presented in this table come with quite a few assumptions nested as footnotes in the report (as shown below).
As you can see, it is not easy to calculate the average time it takes to decrypt a message, even if we know exactly how both the encryption and decryption algorithms work (for a layperson's primer on Shor's algorithm, check out this blog post from Scott Aaronson). The authors of the report had to make a lot of assumptions about how they think quantum computers in the decades to come, which is always subject to change as new architectures and error-correction codes are developed.
When should we start worrying?
My hope is that, after reading this post, you are convinced that there will not be a defined moment when quantum computing breaks classical encryption. It will be more like an ocean tide slowly coming in than like a tsunami. Nevertheless, we should transition to quantum-resistant encryption as soon as possible for a couple reasons. First, there is information stored right now that may remain sensitive for the next 50 years, so it will be still be vulnerable to a quantum computer unless it is re-encrypted. Second, the shift from one Internet encryption standard to another may take as along as 20-30 years. Internet standards move slowly because it requires a lot of inertia to change the status quo. Luckily, recognizing this challenge, NIST has been working on the problem of quantum-proofing the Internet for some time now. So there is no need to panic unless we make zero progress on this front for the next couple decades.