## Subtitles section Play video

• The goal of encryption is to garble data is such a way so that no one who has the data

• can read it unless they're the intended recipient.

• And the encryption of pretty much all private information sent over the internet relies

• immensely on one numerical phenomenon - as far as we can tell, it's really really hard

• to take a really big number and find its factors using a normal, non-quantum computer.

• Unlike multiplication, which is very fast (just multiply the digits together and add

• them up ), finding the prime numbers that multiply together to give you an arbitrary,

• big, non-prime number appears to be slow - at least, the best approach we currently have

• that runs on a normal computer - even a very powerful one - is very slow.

• Like, to find the factors of this number , it took 2000 years of computer processor time!

• Now, it's not yet proven that we won't eventually find a fast way to break encryption

• just with normal computers, but it's certain that anybody with a large working quantum

• computer today would pose an immediate privacy and security threat to the whole internet.

• And that's due to something calledShor's Algorithm.”

• Well actually it's due to quantum superposition and interference; they're just taken advantage

• of by an algorithm developed by Peter Shor, which I'm now going to attempt to explain.

• The kind of encryption we're talking about garbles orlocksmessages using a large

• number in such a way that decrypting orunlockingthe data requires knowing the factors of that

• number . If somebody doesn't have the factors, either they can't decrypt the data, or they

• have to spend a really really long time or a huge amount of investment in computing resources

• finding the factors.

• Our current best methods essentially just guess a number that might be a factor, and

• check if it is . And if it isn't, you try again.

• And again.

• And again.

• It's slow.

• There are so many numbers to check that even the fast clever ways to make really good guesses

• are slow.

• For example, my computer took almost 9 minutes to find the prime factors of this number.

• So if you used this number to encrypt your data, it would only be safe from me for 9

• minutes.

• If, on the other hand, you used a number like the one that took 2000 years of computer processor

• time to factor , your data would definitely be safe from me and my laptop, but not from

• somebody with access to a server farm . This is similar to how putting a lock on your

• door and bars on your windows doesn't guarantee you won't have stuff stolen from your house,

• but does make it take more time and more work.

• Encrypting data isn't a guarantee of protection - it's a way of making it harder to access;

• hopefully enough harder that no one thinks it's worth trying.

• But quantum computation has the potential to make it super super easy to access encrypted

• data - like having a lightsaber you can use to cut through any lock or barrier, no matter

• how strong.

• Shor's algorithm is that lightsaber.

• Roughly speaking, to factor a given number Shor's algorithm starts with a random crappy

• guess that might share a factor with your target number, (but which probably doesn't),

• and then the algorithm transforms it into a much better guess that probably DOES share

• a factor!

• of Shor's algorithm on a regular computer to factor big numbers, but perhaps unsurprisingly

• theturning your bad guess into a better guesspart of the process takes a very

• very long time on a normal computer.

• On the other hand, this key step happens to be ridiculously fast on quantum computers.

• So, our task is to explain how Shor's algorithm turns a crappy guess into a better guess (which

• is purely mathematics), and why quantum computers make that fast (which is where the physics

• comes in).

• It all starts with a big number, N, that you'll need to find the factors of to break into

• some encrypted data.

• If you don't know what the factors are (which you don't), you can make a guess; just pick

• some number g that's less than N . We actually don't need the guess to be a pure factor

• of N - it could also be a number that shares some factors with N, like how 4 isn't a

• factor of 6, but shares a factor with it.

• Numbers that share factors are ok because there's a two-thousand-year-old method to

• check for and find common factors - it's called Euclid's algorithm and it's pretty

• darn efficient.

• All this is to say that to find a factor of N, we don't have to guess a factor of N - guessing

• numbers that share factors with N works, too, thanks to Euclid.

• And if Euclid's algorithm found any shared factors with N, then we'd be done!

• You could just divide N by that factor to get the other factor and break the encryption.

• But for the big numbers used in encryption, it's astronomically unlikely that any single

• guess will actually share a factor with N.

• Instead, we'll use a trick to help transform your crappy guess into a pair of guesses that

• are way more likely to share factors with N. The trick is based on a simple mathematical

• fact: for any pair of whole numbers that don't share a factor, if you multiply one of them

• by itself enough times, you'll eventually arrive at some whole number multiple of the

• other number, plus 1 . That is, if a and b are integers that don't share factors, then

• eventually a^p will be equal to m times b + 1, for some power p and some multiple m

• . We don't have the time to get into why this is true, but hopefully a few illustrations

• can at least give you a feeling for it.

• For example, 7 and 15.

• While seven squared isn't one more than a multiple of 15, and neither is seven cubed,

• seven to the fourth is.

• Or take 42 and 13 - 42 squared isn't one more than a multiple of 13 , but 42 cubed

• is.

• This same kind of thing works for any pair of numbers that don't share factors, though

• the power p might be ridiculously large.

• So, for the big number, N, and your crappy guess, g, we're guaranteed that some power

• of g is equal to some multiple of N, plus 1 . And here's the clever part - if we rearrange

• this equation by subtracting the 1 from both sides, we can rewrite g^p-1 as (g^p/2 + 1)(g^p/2

• - 1) . You can multiply that back together to convince yourself that it works.

• And now we have an equation that almost looks likesomethingtimessomething

• is equal to N, which is exactly what we're trying to find - factors of N!

• These two terms are precisely the new and improved guesses that Shor's algorithm prescribes:

• take the initial crappy guess, multiply it by itself p/2 times, and either add or subtract

• one!

• Of course, since we're dealing with a multiple of N rather than N itself, the terms on the

• left hand side might be multiples of factors of N, rather than the factors themselves.

• Like how 7^4/2+1 = 50, and 7^4/2-1 = 48, neither of which is a factor of 15.

• But we can find shared factors by using Euclid's algorithm again, and once we do, we'll have

• broken the encryption!

• So is this all Shor's algorithm is?

• Where's the quantum mechanics?

• Why can't we use this to break encryption right now?

• Well, indeed, there are three problems with these new and improved guesses.

• First, one of the new guesses might itself be a multiple of N, in which case the other

• would be a factor of m and neither would be useful to us in any way.

• And second, the power “p” might be an odd number , in which case p/2 isn't a whole

• number and so our guess taken to the power of p/2 probably isn't a whole number either,

• which is no good.

• However, for a random starting guess, it turns out that at least 3/8ths of the time neither

• of these problems happens and p does generate guesses that share factors with N and break

• the encryption!

• This is worth repeating - for ANY initial guess that we make, at least 37.5% of the

• time g^p/2 ±1 will lead to a factor of N, decrypting the garbled message.

• Which means we're 99% likely to break the encryption with fewer than 10 guesses.

• However, problem number three is the big one.

• Remember, to turn a crappy guess into a good guess we need to know how many times you have

• to multiply our guess by itself before we get a multiple of N, plus 1.

• And for a normal computer, the act of finding that power p takes a ton of work and time.

• It's not hard for small numbers like 42 and 13, but if our big number is a thousand

• digits long, and our crappy guess is 500 digits long, then trying to figure out how many times

• you have to multiply our guess by itself before you get some multiple of the big number, plus

• one, takes a ridiculous amount of trial and error on a normal computer - more effort than

• it would have taken to just factor N by brute force in the first place!

• So finally, this is where quantum mechanics comes in and speeds things up an INSANE amount.

• Unlike a normal computation which gives only one answer for a given input, a quantum computation

• can simultaneously calculate a bunch of possible answers for a single input by using a quantum

• superposition - but you only get one of the answers out at the end, randomly, with different

• probabilities for each one.

• The key behind fast quantum computations is to set up a quantum superposition that calculates

• all possible answers at once while being cleverly arranged so that all of the wrong answers

• destructively interfere with each other.

• That way when you actually measure the output of the calculation, the result of your measurement

• is most likely the right answer.

• In general it can be really hard to figure out how to put any particular problem into

• a quantum form where all the wrong answers destructively interfere, but that's what

• Shor's algorithm does for the problem of factoring large numbers - well, actually,

• it does it for the problem of finding the power “p”.

• Remember, at this point we've made a crappy guess g, and we're trying to find the power

• p so that g to the p is one more than a multiple of N. A p that does that also means that g^p/2

• ±1 is very likely to share factors with N.

• So to begin the quantum computation, we need to set up a quantum mechanical computer that

• takes a number x as input, and raises our guess to the power of x.

• For reasons we'll see later, we need to keep track of both the number x, and our guess

• to that power.

• The computer then needs to take that result and calculate how much bigger than a multiple

• of N it is.

• We'll call that the "remainder", and we'll write it as plussomething" for whatever

• something the remainder is (remember, we want a remainder of 1).

• So far, no different from a normal computer.

• But since it's a quantum computer, we can send in a superposition of numbers and the

• computation will be done simultaneously on all of them, first resulting in a superposition

• for each p of all possible powers our guess could be raised to , and then a superposition

• for each p of how much bigger each of those powers are than a multiple of N.

• We can't just measure this superposition to get the answer - if we did, we'd get

• a single random element of the superposition as output, likeour guess squared is 5

• more than a multiple of N” . Which is no better than just randomly guessing powers,

• which we can do with a normal computer.

• No, we need to do something clever to get all the non-p answers to destructively interfere

• and cancel out, leaving us with only one possible answer: p.

• Which it turns out we can do, based on another mathematical observation.

• This mathematical observation isn't particularly complicated, but it is a tad subtle and it

• may not be immediately clear why we care.

• However, it's the key idea that allows us to turn the problem of finding p into one