1 00:00:00,000 --> 00:00:04,023 Okay. So now, let's, let's prove this, this 2 00:00:04,023 --> 00:00:11,040 period, this periodic property of the Fourier Transform in this, in this in a 3 00:00:11,040 --> 00:00:15,086 special case. And the special case that we'll, we'll 4 00:00:15,086 --> 00:00:21,091 look at involves, let's assume that, that the period r divides N. 5 00:00:21,091 --> 00:00:28,090 And let's assume that our initial superposition is, is non-zero only on 6 00:00:28,090 --> 00:00:35,025 multiples of r. So, so, let's say that our initial super 7 00:00:35,025 --> 00:00:40,000 position was of the form sum of j of times r. 8 00:00:40,000 --> 00:00:45,081 So, these are the only values which have non-zero amplitude. 9 00:00:45,081 --> 00:00:49,091 And in fact, how many of them are there going to be? 10 00:00:49,091 --> 00:00:53,097 Well, you know, since r goes into M, N over r times. 11 00:00:53,097 --> 00:00:57,084 So, we'll, we'll have j = zero to N / r - one, alright? 12 00:00:57,084 --> 00:01:04,036 So, there will be exactly N such, N / r such values, and each should have, you 13 00:01:04,036 --> 00:01:09,028 know, since we want them to have equal amplitudes, each will have amplitude 14 00:01:09,028 --> 00:01:13,063 square root r / N. So, this is our initial superposition. 15 00:01:13,063 --> 00:01:17,033 It's, it's non-zero only for these multiples of r. 16 00:01:17,033 --> 00:01:22,065 And it has, it has amplitude exactly this much at each one of them. 17 00:01:22,065 --> 00:01:29,068 So now, we want to understand what happens when we apply the Fourier Transform to 18 00:01:29,068 --> 00:01:33,003 this. And the claim is, we get a similar 19 00:01:33,003 --> 00:01:39,000 superposition with period N / r. So, so, in other words, we get K = zero to 20 00:01:39,000 --> 00:01:42,094 something. And, we'll, we'll get non-zero amplitudes 21 00:01:42,094 --> 00:01:47,062 only at multiples of N / r. So, it's K N / r. 22 00:01:47,062 --> 00:01:54,058 So, N / r, 2N / r and so on to r - one times N / r. 23 00:01:54,058 --> 00:01:59,056 So, so, there will be exactly r such non-zero values. 24 00:01:59,085 --> 00:02:05,022 And so, each should have amplitude, one / square root of r. 25 00:02:05,022 --> 00:02:11,025 And K goes from zero to what? Well, you know, there are r of them so 26 00:02:11,025 --> 00:02:13,023 you'll go to r - one. Okay. 27 00:02:13,023 --> 00:02:19,008 So, so, how do we prove this? Well, to prove this, we have to remember 28 00:02:19,008 --> 00:02:25,016 what, what our Fourier Transform is. So, remember what our Fourier transform, 29 00:02:25,016 --> 00:02:32,032 what F sub N looks like is, well, it's one / square root N, times this N by N matrix. 30 00:02:32,032 --> 00:02:38,040 What's the N by N matrix? Well, if you look at the x, yth entry, 31 00:02:38,040 --> 00:02:41,006 it's Omega to the xy. Okay. 32 00:02:41,006 --> 00:02:49,059 So, what, what is this telling us? Well, it's telling us, if you want to know 33 00:02:49,059 --> 00:02:55,065 how much this particular entry gets mapped to that one, well, what, how much does 34 00:02:55,065 --> 00:03:00,037 this, this entry get mapped, you know, what, what does it contribute? 35 00:03:00,037 --> 00:03:03,043 So, we, we, okay, what are we trying to do? 36 00:03:03,043 --> 00:03:10,067 We are trying to figure out what is, you know, if this was, if, if the amplitude of 37 00:03:10,067 --> 00:03:15,004 this entry was, was beta. What's beta, right? 38 00:03:15,004 --> 00:03:23,050 Well, okay, so, so, so the, the amplitude here will get, get some, some contribution 39 00:03:23,050 --> 00:03:32,017 from every non-zero term here. What, what contribution does it get? 40 00:03:32,017 --> 00:03:44,043 Well, it gets Omega to the power of j r, which is in this case, y times omega to 41 00:03:44,043 --> 00:03:54,038 the x, which is times K times N / r, okay? So, that's, that's, this omega to the, 42 00:03:54,038 --> 00:04:05,063 this, times the amplitude you started with, which is square root r / N and then 43 00:04:05,063 --> 00:04:15,011 times one / square root N. And now, we must sum this for all j going 44 00:04:15,011 --> 00:04:22,086 from zero to N / r - one. So, that should be the amplitude of, of, 45 00:04:22,086 --> 00:04:26,089 this, this, particular entry. Okay. 46 00:04:26,089 --> 00:04:37,087 So, so, what is this value? Well, you get this is equal to square root 47 00:04:37,087 --> 00:04:51,088 of r / N summation j = zero to N / r - one of omega to the power of these rs will 48 00:04:51,088 --> 00:05:01,089 cancel and it's j times K times N. But remember, Omega to the N is one. 49 00:05:01,089 --> 00:05:05,074 So, this is just one, right? So. 50 00:05:05,074 --> 00:05:15,068 You, so, you'd get square root r / N times one added N / r times, so times N / r, 51 00:05:15,068 --> 00:05:20,064 which is exactly one / square root r. Okay. 52 00:05:20,064 --> 00:05:30,003 So, so, what they've prove is that for each multiple of N / r, the amplitude is 53 00:05:30,003 --> 00:05:37,043 exactly one / square root r. Now, there are exactly r of these values, 54 00:05:37,043 --> 00:05:42,007 right? And so, so, the, the amplitude is exactly 55 00:05:42,007 --> 00:05:45,096 one / square root r for, for these r values. 56 00:05:45,096 --> 00:05:50,015 What's the amplitude at, at these other points? 57 00:05:50,015 --> 00:05:56,004 Well, remember, this is a unit vector. And we already have a unit vector. 58 00:05:56,004 --> 00:06:00,056 The, the, the, this, this output vector has to be a unit vector. 59 00:06:00,056 --> 00:06:06,091 We've already accounted for, for a unit norm in its amplitudes at zero N / r, 2N / 60 00:06:06,091 --> 00:06:11,035 r, and so on. And so, the amplitude at every other point 61 00:06:11,035 --> 00:06:13,008 has got to be zero. Okay. 62 00:06:13,008 --> 00:06:17,080 That's one way of arguing it. The other way you can argue it is if you, 63 00:06:17,080 --> 00:06:23,025 if you, instead of taking, looking at a point of this kind, a multiple of N / r. 64 00:06:23,025 --> 00:06:28,042 You just look at, look at the amplitude of, of some other point which is not a 65 00:06:28,042 --> 00:06:32,008 multiple of N / r. And then, what you'll see here is that 66 00:06:32,008 --> 00:06:36,065 this Omega to, to these, powers, these will just precess around and they'll 67 00:06:36,065 --> 00:06:43,000 cancel out in the, in the [unknown]. Okay, so in either case, what we've shown 68 00:06:43,000 --> 00:06:48,002 is, that if you start with this periodic superposition with period r, you end up 69 00:06:48,002 --> 00:06:52,006 with this periodic superposition with period N / r. 70 00:06:52,006 --> 00:06:55,032 Okay. So now, we are ready to look at our 71 00:06:55,032 --> 00:07:01,078 primitive, which is period finding. This is what we are going to use in Shor's 72 00:07:01,078 --> 00:07:06,079 algorithm for factoring. So, so, this is sort of the last thing we 73 00:07:06,079 --> 00:07:11,006 are going to do in this, in this particular video. 74 00:07:11,006 --> 00:07:17,098 So, lets try to understand how, how period finding works. 75 00:07:17,098 --> 00:07:34,043 So now, suppose we are given some function f such that this set zero through N - one 76 00:07:34,043 --> 00:07:40,051 is mapped to some set S, we don't care what S is. 77 00:07:40,051 --> 00:07:55,027 But we are told that f is periodic with period, period r. 78 00:07:55,027 --> 00:08:12,039 So, sum period r which divides N. Okay, meaning f(x) = f(x) + r that's in 79 00:08:12,039 --> 00:08:18,011 mod N. So, we're working modular N, okay? 80 00:08:18,011 --> 00:08:25,037 So, we're wrapping around. Moreover, so, so we are told that f is 81 00:08:25,037 --> 00:08:32,047 periodic but within each fundamental period, we are, we are told it's one to 82 00:08:32,047 --> 00:08:36,027 one. So, f(0) is different from f(1) is 83 00:08:36,027 --> 00:08:41,023 different from f(2), is different from f of r - one. 84 00:08:41,023 --> 00:08:46,096 But then, once you get, get past r - one, you keep repeating. 85 00:08:46,096 --> 00:08:56,042 So, if you were to plot out, if this was x, that was f(x) then maybe, this is what 86 00:08:56,042 --> 00:09:04,016 f looks like, it's, it's one to one up through, let's say, that's r - one, that's 87 00:09:04,016 --> 00:09:07,091 zero. And then, starting from r, you have 88 00:09:07,091 --> 00:09:14,025 exactly, the same, same shape. And then, starting from 2r, you have 89 00:09:14,025 --> 00:09:18,007 exactly the same shape and size. Okay. 90 00:09:18,007 --> 00:09:24,085 So, that's our function f. And the way this function is specified to 91 00:09:24,085 --> 00:09:32,086 you is by a black box or some program to compute f. 92 00:09:32,086 --> 00:09:42,027 So, you're given a black box or a circuit C sub f. 93 00:09:42,027 --> 00:09:56,066 And what you want to do is you want to determine the period r, okay? 94 00:09:56,066 --> 00:10:04,021 So now, now, in general, N is going to be very large and so is r. 95 00:10:04,021 --> 00:10:13,046 And so, what's, what's not a very effective strategy is to just take your 96 00:10:13,046 --> 00:10:22,044 circuit for computing f, and feed in random values for x, hoping to see a 97 00:10:22,044 --> 00:10:27,060 collision. So, this is not going to be a very quick 98 00:10:27,060 --> 00:10:34,065 way of, of, of computing r because you'd have to do work proportional to r, or 99 00:10:34,065 --> 00:10:38,000 square root of r, something like that.