Technology

(typed this out yesterday before @ZickZack s excellent answer, but couldn't post it at the time due to maintenance...)

No, you've got it wrong. This is a fairly common missunderstanding which is perpetuated by a lot of coverage about the topic being sloppy.

You could argue that there is a grain of truth to the idea of processing multiple possibilities at once, but it's a bit more complicated than that and the way it's usually presented leads to people building a bad intuition of how it works. If you do get in to the nitty-gritty of Shors algorithm it feels to me at least a bit like a weird hack that shouldn't work at all or at least not be faster than the normal way to compute prime factors. It isn't a general speedup, just in certain cases where you can exploit quantum mechanics in clever ways.

Of the top of my head the SMBC comic about it is actually pretty good. This article makes basically the same points, but a bit more elaborated (note that it was written a while ago so the part about the current state of quantum computing is outdated). I noticed that Veritasum put out a YouTube video which I haven't watched, but he is in my experience good at explaining physics and math so I think that there's a good chance that it'll hold up. I remember liking this Minute Physics video about Shor's algorithm too, if you wanna get a better understanding of it.

I should clarify that I'm not a quantum phycisist, I've just done a couple of internet deep dives on the topic but I can't say that I fully understand quantum computing at all. I do think my understanding of it is better than the one in this article and others like it.