Root Causes 474: Explaining Shor's Algorithm

Hosted by

Tim Callan

Chief Compliance Officer

Jason Soroko

Fellow

Original broadcast date

March 3, 2025

We talk a lot about Shor's Algorithm in our discussion of post quantum cryptography (PQC). In this episode Jason explains Shor's algorithm for non-quantum physicists.

Podcast Transcript

Lightly edited for flow and brevity.

Tim CallanWe're here in the Toronto session season two, having a great conversation about a lot of stuff. One of the things that we've been talking about for five years is Shor's algorithm. I don't know that we've ever explained Shor's algorithm.

Jason SorokoWe haven't and it's time.

Tim CallanExplain Shor’s algorithm.

Jason SorokoRemember, Shor’s algorithm, first question you have to ask is, what kind of a quantum computer can it work on? It absolutely requires a fully gated quantum computer, a universal quantum computer.

Tim CallanAs opposed to a quantum annealing computer.

Jason SorokoAs opposed to quantum annealing and other types of quantum computers that are out there. And the reason is this. In order to observe the entire number space, it needs to have a sufficient number of gated qubits per - -

Tim CallanIt needs to hold them all at once is how I understand. So, it needs to be large enough with enough stable qubits that it can hold them all at once.

Jason SorokoSo imagine RSA-2048. Rough thinking here. I'm oversimplifying, folks. Let's say you need two gated qubits per bit RSA-2048. That’s 4096. So, wow, that's an interesting insight already, isn't it? In terms of, hey, I've heard about quantum computers. I've heard that they're perhaps by the end of 2025, you might have 1000 stable qubits. So we're definitely not going to be cracking RSA-2048 in 2025.

Tim CallanUnless you need to half a qubit, which isn't a thing.

Jason SorokoI'm going to pause right there, because a lot of times people's eyes glaze over in the room whenever I've given talks like this, because people, they sheepishly don't want to put up their hands and go, Jay, what's a qubit? So let's cover that real quick here.

Tim CallanSure. Qubit stands for quantum bit.

Jason SorokoQuantum bit. It doesn't stand for something fancy. It's just a quantum bit. So what's a non-quantum bit? Well, zero and one.

Tim CallanTraditional architecture.

Jason SorokoWe have used symbolic reasoning. In other words, zeros and ones in many combinations, are symbols that can, God, every number, every letter, all modern computer systems are based on that zero and one symbology and zero and one as a bit. In other words, this is when, as you're doing calculations, it's based on ones and zeros. That's all the computer science kindergarten 101, that we're not going to get into. Suffice to say that all traditional computers are entirely based on on and off.

That's great. But there's another type of bit. This bit isn't a zero or one.

Tim CallanQuantum bit is a percentage. It's 35% zero and 65% one.

Jason SorokoIt’s only that once you've measured it. Because until you've measured it all of those combinations.

Tim CallanIt's Schrodinger’s bit.

Jason SorokoSo that's a qubit. In that it's not a 01. It's a anything between zero and one until you measure it, and that it's something once you measure it. The biggest problem with a qubit in engineering today is error handling, but that's what the willow chip has given us, is advanced error handling. But we're gonna get better and better and better. Better engineering for the next five years, at least. Or more, obviously, of, of better error handling. So there are physical qubits. There are logical qubits. My God, Tim, not all qubits are created equal. So that's something to just note intuitively.

So no, it's gonna take a lot more than 4096 bits to correct, because you're gonna have to have error correction systems and all kinds of funky things. So why the 4096? Why? Just think about this. What are you trying to solve for? We’re trying to solve for prime numbers that have been multiplied together within that system.

I won't get into the math of RSA. That's not what this is about. Shor's algorithm is really another name for a system that's using quantum Fourier transform.

I’m gonna tell you a funny story. I remember this. I was exactly 16 years old. I was working for a government office that was concerned with lands and forests and various forms of wildlife and one of the things we did was we were setting up lightning locator systems because we were interested in lightning. We were interested in forest fires, and that's basically what business we were in. I remember jumping out of a helicopter because we were in the middle of absolutely nowhere in northern Ontario and I'll never forget that I had in my hands two spectrum analyzers. We're talking circa late 1980s. Imagine this, Tim. Think about this. This is the analogy I want you to imagine before I tell you the rest of the story of jumping out of the helicopter. You are far old enough to remember, like me, dialing on an FM dial.

And so if you were to ask the question, how many radio stations can I listen to on this FM dial, you would have to brute force every single turn of a knob and listen to all those frequencies. Well, within that radio was a system that actually was able to listen to a specific frequency and give you your FM or give you your AM station. Great. Well, by the time I was jumping out of that helicopter, we had systems that could actually analyze through a fast Fourier transform all of the radio stations all at once. In other words, any frequency that was being modulated on, you would have a signal across what basically looked like an oscilloscope. If you can imagine that. So that was amazing, because at a glance, you could see the entire frequency spectrum that was defined by the machine, and you could actually solve for, all right, tell me every frequency that's being broadcast on right now. The reason why we had that in the bush - I'll tell you the rest of the story – I’m about to jump out of the helicopter. I’m a pretty strong kid. I'm not very tall, but I was a strong kid and I was told just before I jumped out of the helicopter, hey, watch out for the bear. What? Jump out of the helicopter and sure enough, there's a bear about 30 feet away from me, and he's just looking at me like, what? It was like an alien just dropped out of space. Probably never seen a human being before.

Tim CallanCertainly never a helicopter.

Jason SorokoSo that's the setting I'm in while I'm setting up two spectrum analyzers to make sure that the lightning locator system wasn't creating interference on various frequencies that we didn't want to create interference on. That's the reason why I set up these things. And sure enough, I was looking at the frequencies that our systems were broadcasting on and listening on, and all was good. And we went back home, and I didn't get eaten by a bear. Terrific.

Tim CallanExcellent. As witnessed by you being here now.

Jason SorokoI am here today to tell you that I experienced two things that day. Didn't get eaten by a bear, and (b) I got to look at a very expensive set of spectrum analyzers, which were defined in a number space from X to Y, and were able to tell me, here are all the places where there are frequencies that are open. Amazing. So what's quantum Fourier transform?

If you go back to papers, very early papers on, how in the world do we look at a number space and solve for every prime number in that space? Well, believe it or not, you can put a quantum computer against that problem and one of the ways a quantum computer can be programmed to solve for a lot of prime numbers quickly is to say how many stable qubits do I have, and that number of stable qubits can define my number space that I can evaluate for prime numbers.

So if you need to solve for RSA-2048, you need to have X amount of stable qubits. So very rapidly, what a quantum computer can do is through a quantum Fourier transforming – eh, what does that really mean? Fourier sets are really all about saying, all right, when there's a repeating pattern happening, if there's a certain number that is calculable in this repeating set of frequencies. In other words, remember, there's a temporal element to this in a fast Fourier transform, but in a quantum Fourier transform, what you're measuring is the energy level of the qubits, because you're taking measurements of all the qubits.

And if the qubits at specific points in number space, say, as a quantum, as a Fourier set, you can actually look at – and it’s amazing. I will put screenshots of the original IBM research that looked just like the spectrum analyzer, that I was sitting in front of that bear looking at.

Tim CallanWe are breaking new ground in this podcast, for sure. We're gonna have screenshots and edits.

Jason SorokoNow, this is important one, because it can't just be words. It's gotta be pictures. I might even show a bear. Just to create the vibe. Massive, massive number space, where it would be impossible, or a traditional computer – zeros and ones - to just roll the dial in brute force. Is this a prime? Is this a prime? Is this a prime?

Tim CallanThat's the whole point of the whole thing.

Jason SorokoYou got it. But a quantum computer, it's no different than going from, I have to turn the dial to now in front of a bear spectrum analyzers, I now see all - -

Tim CallanI can just look for the waves.

Jason SorokoIt's just there. The sinusoidal waves, which is what a Fourier transform is, the sinusoidal waves at each of the places that were measured to have values greater than zero all of a sudden, it's like, there's all the primes.

Tim CallanThis all at once detection owes itself to the probabilistic nature of quantum physics. Is that correct?

Jason SorokoQuantum fields, this is where I got into trouble last time I tried to do this explanation. I'm going to try to do this a little more quickly, a little more succinctly. Tim, did you know - and my God, you accuse me of going all over the place. I'm going to still go all over the place.

Chlorophyll. Strangely enough - I didn't know this till I started to look it up - It's one of these weird things where a little more energy is going into the plant than you would expect for the amount of chlorophyll in a plant. What the heck is going on? Now, nobody has fully explained it, but I tell you one guy who has tried to explain it, and this is not proven. This is merely an analogy. It turns out that chlorophyll in plants have nanotubules. Now this is not something I've witnessed. I'm just reading and repeating here. Don't shoot the messenger. That potentially could be creating a type of quantum field where photons could be everywhere at once.

In other words, photons that are just coming at random angles might not be hitting the little solar panel equivalents in the chlorophyll. Because, don't forget, just because it's green doesn't mean it's collecting energy.

Tim CallanAnd so by being quantum, it can collapse down to the position that allows the energy to be absorbed.

Jason SorokoEvery photon hits every receptor. Because it’s everywhere.

Tim CallanAin't that convenient?

Jason SorokoRoger Penrose, who I got to meet in university when I was a much younger person, is the guy who wrote about this in books such as The Emperor's New Mind. In fact, The Emperor's New Mind also was the idea that you've got similar nanotubules in the brain. In other words, there's spooky systems at small scale. This is where quantum things happen. Well, what happens if quantum fields can be created in the brain? Now, nobody's proven it. A lot of people don't like to even talk about that. In fact, a lot of people are very scared of the idea, because all of a sudden, ESP and other strange brain phenomena which are not proven or anything close to that - I don't want to pretend that this is the truth. I'm just saying that if quantum fields exist in the human brain, God only knows what that's for, why we adapted to it, and what kind of things that we can and can't do with our brains.

Richard Feynman. Like Richard Feynman with quantum, and I'm talking about like guys like Roger Penrose, who are no joke, they're the guys who are talking about this kind of stuff. Let's go back to our world now.

Our world basically, just to answer your question about the fact that these qubits are evaluating everything at once, in other words, the entire number space that they're defined to be looking at, essentially act like kind of - I like analogies. They kind of act just like a spectrum analyzer so that you can see the entire number space. In other words, the entire frequency spread all at once. Something that used to have to be brute forced by a traditional computer. And so now Shor's algorithm has all kinds of mechanisms for how you do the input to the quantum Fourier transform. The reason I over rotated on the quantum Fourier transform and tried to create several semi intuitive explanations for what it's actually doing, that's about as close as I'm going to get to explaining to you, really what is at the heart of Shor's algorithm.

Can I spend an extra minute with you to talk about quantum annealing? Quantum annealing is definitely different because it's not fully gated. It's not a universal computer. It normally is dependent upon you bringing it an optimization problem. That's what quantum annealers are the best at. But what happens if you can flip the table a little bit and actually program into a quantum annealer optimizing for factorization.

Tim CallanCan you?

Jason SorokoTurns out – yes! You and I just podcasted about a couple of Chinese researchers who actually used a d’wave computer and gave the first demonstrated attack, if you will, against very small bit RSA. Keys. And they did two - -

Tim CallanWe had a whole episode on this. I think it's called, Did Researchers Use Quantum Annealing To Break RSA?

Jason SorokoI'm going to tell you what. If you listen to that episode, I'm going to say, don't listen to it. Because I have all new information. Here's what I did. I actually turned that Chinese written report into a bot. So now I can query that paper. Because I don't read Chinese. It turns out that the initial journalist who did the interpretations got it wrong. So we have to redo that podcast. That's coming at you soon.

Tim CallanThere’s a teaser. I look forward to that. That’s exciting.

Jason SorokoWhat I'm gonna explain is, how did I do a retrieval augmented generative system to be able to use AI to very, very accurately search that paper. It’s a whole other thing. So let's get it to quantum annealing really quick.

Which is this. You're talking about a collapse. In other words, the natural degradation of - - it’s still qubits - - But here's the thing about a quantum annealer. Instead of starting with like a 40 qubit fully gated computer, that d’wave computer, those Chinese researchers were using - 5000 qubits.

Tim CallanBecause stability is a whole different game there, because you're letting it degrade.

Jason SorokoSo, think about this.

Tim CallanYou want it to degrade.

Jason SorokoI'm trying to make this as intuitive as possible and not make this a 12 hour podcast. So here it is.

If you were trying to solve for a maze, one of those paths in the maze was, absolutely, factorized the two prime numbers that were multiplied together for RSA, and that's and yet like this is not just a maze. This is like the most complicated maze you've ever seen in your life. I don't even know how large of a number space I'd have to explain to you, but this is like the biggest maze ever.

But, yes, there are many, many, many failed paths, but there's one path that gives you the answer. A quantum annealer will actually follow every path, and as it's rolling down the hill, - - this is the thing. As it's degrading, as the energy levels of the qubits are allowed to degrade down to zero, eventually what you end up finding out is one of the paths emerges as the oh, this is not zero, and now you found the path.

So remember how he said in quantum Fourier transform, it required you to have a lot of stable qubits in order to be able to give you that beautiful sinusoidal wave representation, the spectrum analyzer. With quantum annealing, the number of qubits you start with allows you to determine, again, the number space. Therefore, you still need to have a lot more qubits at the beginning than we have today in current state of the art quantum annealers. But achieving a higher number is less difficult. I hope that was enough for today.

Tim CallanWell, that's good. We may return to this. It sounds like definitely we want to return to talking about the quantum annealing attack, but for today, thank you, Jay.

Stay informed with expert insights

Subscribe to Root Causes for engaging discussions on PKI, digital security, and best practices for protecting your organization's critical assets. Don’t miss an episode!