Why are quantum computers faster at breaking RSA-2048 encryption than classical supercomputers are? One night whilst browsing the web I came across a video on Youtube called "The Hype Over Quantum Computers, Explained" by CNBC. Naturally, I became curious as to why quantum computers are so powerful in solving certain types of problems, such as modelling chemical compounds, and factorising large numbers using Shor's algorithm.
I've done some research into concepts such as the Qubit and how the concept of superposition allows each qubit to be represented as a linear combination between $0$ and $1$. I've also came across topics such as wave interference, and other quantum topic. However, for the most part the fundamental reasons why a Quantum Computer is able to potentially break RSA-2048 encryption is still unknown to me.
That being said, could someone please explain to me (in 200 words or less), why a quanutum computer is able to (theoretically) break RSA-2048 encryption using Shor's algorithm, whereas a classical computer is not.
 A: What allows an algorithm to be more efficient than a brute force solution is when the problem has some special structure that can be exploited.
One task that quantum computers are naturally very good at is identifying periodic structure. Here I will steal an analogy from Scott Aaronson to explain how quantum computing works. You can think of each output qubit in your computer as a dial on a clock face (more mathematically this dial represents the phase of the qubit). To obtain the probability of a given output, we arrange the dials end to end (maintaining their orientation) and compute the square of the length of a line drawn from the tail of the first arrow to the tip of the last arrow. If all the dials are aligned in the same direction, then we will get a large probability; if the dials are arranged every which way, then we will get a small probability.
At a rough, intuitive level, you can perhaps get a feel for how such a setup is naturally suited for finding periodic structure. If we have a superposition of inputs, then we can arrange the computer so that inputs which have a periodic structure will tend to rotate qubits in the same direction, while inputs without a periodic structure will tend to rotate qubits in many random directions. Thus by quantum superposition, the computer can "try many inputs at once," but only the output associated with a periodic input has a large probability of occurring.
The factoring problem can be broken down by a series of clever number theory tricks, to the problem of finding a period in a particular function. More precisely, if we want to factor $N$, then we pick a random number $a$ in the range $1<a<N$, and it turns out that if we can find the smallest period $r$ of the function $f(x)=a^x {\rm mod} N$, then there is a method to use $r$ to find the factors of $N$. The key application of quantum computing in Shor's algorithm is to use the quantum Fourier transform to obtain $r$ (and thereby factor $N$).
Classical computers cannot try multiple inputs at once with the same hardware in the same way that quantum computers can, and so cannot exploit this structure in the same way as quantum computers.

Here's an article by Scott Aaronson that is worth reading and better explained: https://www.quantamagazine.org/why-is-quantum-computing-so-hard-to-explain-20210608/
