Placeholder Image

字幕表 動画を再生する

  • 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!

  • There's nothing intrinsically quantum mechanical about this - you can, in fact, run a version

  • 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