How might quantum computers destroy computer security?
By utilizing Shor's algorithm.
[MUSIC PLAYING] Last week, we made a ton of progress toward our goal of hacking into an encrypted message.
Remember, popular forms of cryptography work by multiplying together two large prime numbers and using those primes as keys to recover the message.
So to crack the code, we'll need to find the prime factors of a really big number.
But that would take a classical computer a long time.
Way longer than the encrypted information is probably useful for.
But Shor's algorithm allows us to quickly factor large numbers using a quantum computer.
To learn about the outline and big picture of Shor's algorithm, check out last week's episode.
After that, come back here, because we're about to dive into the quantum portion of that algorithm.
For that, it will also be helpful if you have some background knowledge about how a quantum computer works.
Luckily, we've got an episode for that, too.
There's a popular notion that a quantum computer is just a bunch of classical computers working side-by-side in parallel.
That's kind of true and kind of false.
Let's see how.
We'll start by looking at one classical computer.
What's the most straightforward way it could find the factors of a number N?
Well, it could check.
Is 2 a factor, is 3 factor, is 4 a factor, and so on.
But if N is big, this might take a lot of steps.
Now, if a quantum computer is just a bunch of classical computers working in parallel, then we could have one computer check if 2 is a factor, another check if 3 is a factor, and so on.
Then it would only require two steps.
We've split the many steps of a classical computer among the many parallel computations of a quantum computer.
Here's the problem.
When we say that a quantum computer is a bunch of classical computers working in parallel, what we really mean is that a quantum computer is in a superposition of basic states, which are the kind of states a classical computer could be in.
Remember, a superposition is a combination of basic states and there's some probability associated with observing each of them.
To find that probability, you square the amplitude of the number in front of the basic state.
Here, we have N basic states and a 1 over N probability of being in each state.
So the quantum computer is not actually in all of these states.
It's more like the quantum computer has split itself into N different pieces.
But when you measure a quantum computer, that is, ask for the result of a computation, it doesn't tell you about all N pieces it's in.
Instead, it will pick a state, each with probability 1 over N, and tell you what that state says.
You can't look at the whole thing.
Just one random state.
That's a problem for us.
Only two the N states give really useful information.
That the number of checked was a divisor of N. So the vast majority of the time we run the computation, N minus 2 over N of the time, the result will just tell you that something is not a factor of N. That means our algorithm is no more efficient than checking random numbers to see if they are divisors using a classical computer.
To harness the power of quantum computation, we need each of these basic states, the components of the superposition, to be working together.
Right now, they're functioning as separate computers individually searching, which is a problem because the quantum computer can't tell us about all these independent states.
But if there's some kind of underlying structure to the states, we can use that to amplify the states with the correct answers.
In this case, the ones that give the factors of a number.
Then when we measure the quantum state, we'll have a high probability of ending up with the correct answer.
In fact, that's summarized in the tagline of a fantastic blog written by theoretical computer scientist Scott Aaronson.
Quantum computers would not solve hard search problems instantaneously by simply trying all the possible solutions at once.
So instead of checking each number smaller than N to see if it's a factor, how does Shor's algorithm find the factors?
It needs to utilize the properties of its entire superposition, and not just a few of its basic states.
To do that, Shor's algorithm actually uses some number theory, to transform the problem of finding the factors of a given number into a problem of finding a different number, the period of a periodic function.
In last week's episode, we outlined the number theory in Shor's algorithm for finding the two secret prime factors, p and q, of a given number N. That is, N is equal to p times q.
Here's the four basic steps.
Step 1, pick a number, a less than n, at random.
Check to make sure it's not a factor of N. Step 2, find r, the period of a mod N. Step 3, check that r is even, and A to the r over 2 plus 1 is not congruent to 0 mod N. Step 4, let p be the gcd of a to the r over 2 minus 1 and N, and q be the gcd of a to the r over 2 plus 1 and N. Then you found p and q, the two prime factors of N. But step 2 is the obnoxiously long step.
Remember, N is the number we're trying to find the factors of, and a is a selected number smaller than N. We're trying to find the smallest number r, which we call the period, such that a to the r is congruent to 1 mod N. It's pretty easy to find the period of a small example just by checking the powers of a mod N until we get 1.
So if N is equal to 7 and a is equal to 2, we compute 2 to the 1 mod 7 is 2, 2 the 2 mod 7 is 4, and 2 to the 3 mod 7 is 1.
So the period is 3.
But if N is really big, then r, the period, can be basically as big as N. There is no known efficient classical way to find the period.
Remember how we tried to find the factors of N by letting the quantum computer act as N parallel classical computers, and using each to check a different factor?
We could try the same thing to find the period.
We begin with N different states representing the numbers 1 through N. Then for each state, we compute a to the x mod N, where x is the number of the state.
So now the states are a to the 1 mod N, a to the 2 mod N, a to the 3 mod N, and so on.
Then we just look for the smallest one that says 1, and we're done.
That's when we run into the same problem as before.
We can't just scan all the states at once.
When we look at the result of a quantum computation, it just shows one random state, which isn't very helpful.
But there is something different about this current problem.
Something that will help us.
The period is a global property of this quantum superposition.
It's not just a special fact about one or two of the basic states.
It's a fact about this entire wave of numbers created by superposition, how often it repeats.
That's the period.
We can use this to our advantage.
We apply something known as the quantum Fourier transform to the superposition a to the 1 mod N, a to the 2 mod N, a to the 3 mod N, and so on.
The quantum Fourier transform utilizes the ideas of quantum physics to do exactly what we want.
It uses resonances to amplify the basic state associated with the correct period, and the incorrect answers destructively interfere, which suppress their amplitudes.
After applying the quantum Fourier transform, there's a very high probability that we'll pick the correct period.
So how does it work?
To understand the quantum Fourier transform, we'll need to start with a quick visual version of a branch of math known as complex analysis.
What we'll really be doing is adding complex roots of unity.
But if you aren't familiar with that concept, don't worry.
Start with a bunch of circles.
On the first, we'll put two equally spaced dots.
On the next, we'll put three equally spaced lines.
On the next, four equally spaced dots.
And so on.
Notice, though, we always put one of the dots on the middle right side, the 0 degree angle.
Start a dial on that special point.
By the way, these dots are called complex roots of unity.
Now, let's focus on the circle with three dots.
We'll move the dial counter-clockwise through the points.
And underneath the dial, we'll form a path consisting of arrows where the direction of the arrow is given by the direction in which the dial points.
For example, with three dots, the first arrow points east.
Then move the dial one dot counterclockwise and connect to the first arrow another that points northwest, like the dial.
Move the dial again and connect another arrow pointing southwest, the same direction as the dial.
Notice that after three arrows, we're back where we started.
This is what it looks like on a circle with six dots.
Again, after six arrows, we're back to the starting place.
OK, how is this helpful?
Remember that we have a superposition whose basic states look like a to the 1 mod N, a to the 2 mod N, a to the 3 mod N, and so on.
Let's pick a tiny example, like a equals 2 and N equals 7.
Then the components of the superposition are 2 to the 1 mod 7, 2 to the 2 mod 7, 2 to the 3 mod 7, and so on, which is the repeating pattern 2 4 1, 2 4 1, 2 4 1.
Because this example is so small, we can just see that the period is three by looking at it.
But how can we use our dials to figure out period?
We'll move along the sequence a to the 1 mod N, a to the 2 mod N, a to the 3 mod N. For each term in the sequence, move every dial once counter-clockwise.
Any time we encounter a 1, stop and record where the dial is pointing with an arrow.
Let's focus on the sequence 2 4 1, 2 4 1, 2 4 1.
The dial with three points is always pointing directly east when we record its values.
So our path of arrows just runs off to the right.
But what happens to the dial with four points?
The first time we encounter a 1, its facing south.
The next time, it's facing west.
The next time, it's facing north.
And the fourth time we encounter 1, its facing east again.
So our path of arrows has looped back to where it started.
In fact, this will happen with all of the numbers besides 3.
They'll all just make loops near the starting point.
The distance of the arrow from the starting point is like the amplitude, or probability of a state.
Since we are most likely to observe these states at the end of the computation, we're set.
We've magnified the correct answer.
And that's roughly how the quantum Fourier transform works.
Here's another way to think about it.
Pretend you're on a swing with period three seconds.
It swings back and forth every three seconds.
The arrows from before are like the kicks on a swing that you time as you try to get higher and higher on the swing.
If the kicks are timed off resonance with the swing's natural frequency, so anything other than every three seconds, then you end up slowing down the swing.
But if every kick is timed to match the frequency of the swing, every three seconds, you create resonance, amplifying the swing's motion.
If we start with a bunch of states, metaphorically swings, with different periods, than only the swing with the correct period will be moving after a while.
It'll be the state with the biggest amplitude or highest probability of being observed.
Of course, there is no actual dials or arrow paths or swings in a quantum computer.
That's just a visual representation of adding complex numbers, which are the amplitudes of waves.
Waves and their crazy ability to either reinforce each other with constructive interference, or negate each other with destructive interference, are at the heart of quantum physics.
The dial with three dots is showing constructive interference by making the arrow path grow, which represents the likelihood the quantum computer will measure that state.
The other dials are destructively interfering, making it less likely we'll detect them.
And just because I like to leave things on a down note, quantum computers don't really exist yet.
At least, not in any capacity large enough to use Shor's algorithm to factor numbers bigger than the ones you can figure out quickly on a piece of paper.
But it's likely just a matter of time before real quantum computers are factoring away.
See you next time on Infinite Series.
Hello.
I just wanted to respond to some of the comments about our first episode on Shor's algorithm.
So Neon Bull says, "When N equals p times q, then if the square root of N is not a whole number, it implies that one of the primes is less than the square root of N and one is bigger than the square root of N." That's true.
So what that means is that if you're checking to find all of the prime factors of the number N, you only need to look below the square root of N. But it doesn't that big a difference, because if N is really big, then the square root of N is really big.
So it's still a lot of numbers to check.
All right, Bhargav R said, "what if we have more than two prime factors?"
That's a great question.
Shor's algorithm still works, and still works for numbers with more than two prime factors.
You have to modify the fourth step a little bit.
But it's not that big a deal.
I chose to focus on the case where N just had two prime factors because it's a little simpler, and because that's what's applicable for RSA cryptography.
All right, finally, BobC's summary of how he experienced this episode made me laugh.
He's said, "Watch straight through.
Start over.
Pause, think, pause, think.
"Watch again.
Pause.
Google, Wikipedia, pause, Google, MathWorld.
Sleep.
Watch again.
Write some Python.
Peak ahead to Shor's algorithm."
I liked this, partly just because it made me laugh.
And partly because that's how most people experience math.
It takes a lot to process all the details, and you have to keep coming back to things and try a new angle, read about it from a different source, sleep on it, maybe go for a walk.
There's just a lot of absorbing that happens in learning math.
And I think it's pretty fun.
All right, have a good week.