1 00:00:00,000 --> 00:00:03,009 Okay. So, in this video we're gonna study some 2 00:00:03,009 --> 00:00:11,003 properties of quantum Fourier transform that make them useful in, in algorithms. 3 00:00:11,003 --> 00:00:17,001 So let's, let's re, remember what quantum Fourier transform is. 4 00:00:17,001 --> 00:00:25,004 Its it's, it's an n by matrix, it's, it's an n by unitary matrix which is which is 5 00:00:25,007 --> 00:00:30,002 expressed in terms of the n through infinity omega. 6 00:00:30,002 --> 00:00:36,000 So, here omega is e to the two pi I over n. 7 00:00:36,000 --> 00:00:43,004 It's a primitive Nth root of unity. And, and basically the, the, the matrix 8 00:00:43,004 --> 00:00:47,006 has its, has its, JKTH, entry, omega to the JK. 9 00:00:47,006 --> 00:00:55,004 Let's see, so there are, there are two, very interesting properties of, of this 10 00:00:55,004 --> 00:01:04,006 quantum Fourier transform. So, so let's say that this was, this was a 11 00:01:04,006 --> 00:01:12,009 quantum Fourier transform matrix, one omega, omega to the N minus one, one omega 12 00:01:12,009 --> 00:01:17,007 to the N minus one. Okay. 13 00:01:17,007 --> 00:01:31,000 And, let's say we apply the two. To this state and we got as output. 14 00:01:35,004 --> 00:01:41,006 Right? So we are assuming, so, so what we are 15 00:01:41,006 --> 00:01:52,000 saying is that f sub n applied to the state, summation over j alpha j, j. 16 00:01:52,005 --> 00:01:57,007 Is equal to summation of a k, b to the sub k, okay. 17 00:01:57,007 --> 00:02:02,009 Alright? That's the, that's the result of applying 18 00:02:02,009 --> 00:02:10,002 this, this transform to this. Okay, so now let's, let's consider what 19 00:02:10,002 --> 00:02:17,005 happens if we, if we applies the same transformation, the fourier, quantum 20 00:02:17,005 --> 00:02:23,000 fourier transform so we, we apply this the same matrix. 21 00:02:23,006 --> 00:02:28,001 Okay? So we apply it to a shifted version of 22 00:02:28,001 --> 00:02:32,005 them. So, so what we're going to do is we're 23 00:02:32,005 --> 00:02:38,002 going to shift. Our, our input superposition. 24 00:02:38,002 --> 00:02:45,003 And so we sh-, we shifted cyclically, so let's say we shifted by one position but 25 00:02:45,003 --> 00:02:52,000 then, you know, as you'll see the same principle will apply no matter how much 26 00:02:52,000 --> 00:02:59,001 we, if we, if we shift by many positions. So, so let's shift everything down by one 27 00:02:59,001 --> 00:03:03,042 position. So you have Alpha naught moves down to the 28 00:03:03,042 --> 00:03:10,046 second position, alpha one, alpha n - two, and then alpha n - one get knocked, gets 29 00:03:10,046 --> 00:03:18,037 knocked out and move to the top position. And now we want to understand, what's the 30 00:03:18,037 --> 00:03:24,093 Quantum Fourier Transform? Well, the answer is particularly nice. 31 00:03:24,093 --> 00:03:31,049 So what it says is basically everything stays unchanged. 32 00:03:31,049 --> 00:03:40,047 Okay, so all these amplitudes, on this side, basically remain the same, except 33 00:03:40,047 --> 00:03:45,019 they get multiplied by faze. And, and what phase is it? 34 00:03:45,019 --> 00:03:50,038 It's some, it's some, some meaning, meaning a complex number of unit 35 00:03:50,038 --> 00:03:54,039 magnitude. And in fact, it's, it's actually going to 36 00:03:54,039 --> 00:03:58,083 be a power of omega. So what power of omega do we have? 37 00:03:58,083 --> 00:04:05,042 Well, it depends upon which row we have. So, so this first one gets multiplied by 38 00:04:05,042 --> 00:04:12,062 one The second one by omega, the third one by omega^2, and so on, up to omega to the 39 00:04:12,062 --> 00:04:16,024 N-1. Okay, now, here's the important thing. 40 00:04:16,024 --> 00:04:23,032 The important thing is that each of these, it's not what the actual value is. 41 00:04:23,032 --> 00:04:27,062 It's the fact that these are all unit magnitude. 42 00:04:27,062 --> 00:04:33,023 So now. If we were to do a measurement at this 43 00:04:33,023 --> 00:04:36,026 point. What we'd see. 44 00:04:36,026 --> 00:04:43,058 Is, is k with probability beta sub k magnitude^2. 45 00:04:43,058 --> 00:04:52,013 Exactly the same as if you did the measurement up here. 46 00:04:52,013 --> 00:04:59,057 You see k with probability beta sub k magnitude^2. 47 00:04:59,057 --> 00:05:03,038 So. The moral of all this is, that if you 48 00:05:03,038 --> 00:05:10,011 start with some superposition, and if you are going to do a Fourier transform, 49 00:05:10,011 --> 00:05:19,055 quantum Fourier transform and then measure, so if you are going to do. 50 00:05:19,055 --> 00:05:27,033 Quantum. For a sampling. 51 00:05:27,033 --> 00:05:34,002 Then. Doing a cyclic shift, of the, of the input 52 00:05:34,002 --> 00:05:39,059 super position doesn't change the output distribution. 53 00:05:39,059 --> 00:05:47,002 Okay, so, now to some of you, this you know this, this property of quantum 54 00:05:47,002 --> 00:05:53,076 Fourier transforms might look very familiar, and the reason it looks familiar 55 00:05:53,076 --> 00:05:59,075 is probably because it is. So this, this property that when you shift 56 00:05:59,075 --> 00:06:07,013 the, shift the input superposition, the output superposition just gets multiplied 57 00:06:07,013 --> 00:06:12,085 point-wise by phase. This is the same thing as this is the 58 00:06:12,085 --> 00:06:22,058 convolution. Multiplication. 59 00:06:22,058 --> 00:06:34,074 Property of the foray transform. Okay so, well see if you can, you know, if 60 00:06:34,074 --> 00:06:39,061 you, if you do know about the con-, convolution multiplication property, see 61 00:06:39,061 --> 00:06:42,040 if you can figure out why this is the case. 62 00:06:42,040 --> 00:06:46,069 So what are you convolving and what is point-wise multiplication? 63 00:06:46,069 --> 00:06:49,077 Right? So just to give you a hint, this is where 64 00:06:49,077 --> 00:06:55,026 you have point-wise multiplication. You are multiplying point-wise by this. 65 00:06:55,026 --> 00:07:01,001 You know, by these phases, right, so really okay, so this, this what you are 66 00:07:01,001 --> 00:07:06,070 doing, you are multiplying the fourier transform of something which is the b term 67 00:07:06,070 --> 00:07:12,020 of beta n minus one, point wise by one omega, omega squared omega to the n minus 68 00:07:12,020 --> 00:07:18,018 one, which is the fourier transform of something else. 69 00:07:18,018 --> 00:07:24,070 Okay and. So what you're getting on the left inside, 70 00:07:24,070 --> 00:07:30,097 you're getting, you're, you're starting with this particular vector, and then 71 00:07:30,097 --> 00:07:35,075 you're convolving it with something to get the shifted vector. 72 00:07:35,075 --> 00:07:41,024 So, that's why you're getting a convolution on the left, and point-wise 73 00:07:41,024 --> 00:07:47,016 multiplication on the, on the right. See if you can figure it, if you, if you 74 00:07:47,016 --> 00:07:52,051 happen to know about the convolution multiplication property. 75 00:07:52,051 --> 00:07:55,094 Okay. So now, let's, let's prove a second very 76 00:07:55,094 --> 00:07:59,088 important property of the Quantum Fourier Transform. 77 00:07:59,088 --> 00:08:07,021 The, this property says that if you start off with a periodic function, then the 78 00:08:07,021 --> 00:08:12,030 quantum theory transform is going to map it to a periodic function. 79 00:08:12,030 --> 00:08:18,050 So let me, let me say this in a, you know, a little more carefully in terms of how 80 00:08:18,050 --> 00:08:25,057 you've been thinking about it. So, let's say that our input superposition 81 00:08:25,057 --> 00:08:28,094 was. Summation of a sub j and j. 82 00:08:28,094 --> 00:08:34,002 So j, of course, goes from zero to a -one. Alright? 83 00:08:34,002 --> 00:08:42,002 So that's our input superposition. And now we are applying the Fourier 84 00:08:42,002 --> 00:08:48,075 transform to this. And we get a output superposition, 85 00:08:48,075 --> 00:08:55,037 summation k equal to zero to a -one of b to a sub k. 86 00:08:55,037 --> 00:08:59,036 Okay? Okay, so wh-, what's periodic here? 87 00:08:59,036 --> 00:09:06,089 So, so remember wh-, what we are doing here is we are, we are, we are plotting J 88 00:09:06,089 --> 00:09:11,052 along this axis and alpha sub J along that axis. 89 00:09:11,052 --> 00:09:18,038 So what we are saying is that these amplitudes are periodic, meaning that. 90 00:09:18,038 --> 00:09:22,051 Alpha sub j plus r equal to alpha sub j. Right? 91 00:09:22,051 --> 00:09:27,008 That's what it means for it to be periodic with period r. 92 00:09:27,008 --> 00:09:33,013 So, when you, when you add r to the index, you get the, get back to the same 93 00:09:33,013 --> 00:09:36,064 amplitude. So we are claiming. 94 00:09:36,064 --> 00:09:43,035 That this implies. That beta must also be periodic. 95 00:09:43,035 --> 00:09:50,031 Okay, so what's beta? Well, you know, so, so here we are, we 96 00:09:50,031 --> 00:10:00,009 are, we are plotting k along the x axis, and beta sub k along this y axis. 97 00:10:00,009 --> 00:10:05,047 Right? And what we are claiming is, now, beta 98 00:10:05,047 --> 00:10:14,066 must be periodic with period M over R. So, beta sub k + m over r must be = to 99 00:10:14,066 --> 00:10:23,035 beta sub k. Okay, so we've already seen an, an extreme 100 00:10:23,035 --> 00:10:26,027 case of this. You know. 101 00:10:26,027 --> 00:10:31,067 So, so, let's, let's write it out over here. 102 00:10:31,067 --> 00:10:38,085 So, suppose we apply f sub n to the uniform superposition. 103 00:10:38,085 --> 00:10:44,039 To one over square root n, sum of everything. 104 00:10:44,039 --> 00:10:47,074 J= to zero to n-1 of j. Right? 105 00:10:47,074 --> 00:10:52,042 So. So it's, you know this is a super position 106 00:10:52,042 --> 00:10:58,078 of everything from zero to N - one. And what's the Fourier transform of this? 107 00:10:58,078 --> 00:11:03,040 Well it's, it's, It's just, it's just zero. 108 00:11:03,040 --> 00:11:10,041 Right? And so, well, this, this superposition has 109 00:11:10,041 --> 00:11:15,008 period r = one. So here, we have r equal to one. 110 00:11:15,008 --> 00:11:23,004 And so m over r is equal to m. So this is a, this is a superposition with 111 00:11:23,004 --> 00:11:29,091 period exactly m, in the sense that, in the sense that this is a superposition 112 00:11:29,091 --> 00:11:33,020 which starts, near with which is a delta function at zero. 113 00:11:33,020 --> 00:11:38,055 And then there's nothing all the way up to M minus one, you know, which is everything 114 00:11:38,055 --> 00:11:41,056 we have. And then of course if we, if we made it 115 00:11:41,056 --> 00:11:46,023 [inaudible], you know we'd get another delta function at M and then nothing all 116 00:11:46,023 --> 00:11:50,038 the way up to 2M minus one and so. But, but of course we are, we are only 117 00:11:50,038 --> 00:11:55,050 limiting ourselves to zero through M minus one, so the period is exactly M, which is, 118 00:11:55,050 --> 00:11:59,071 which is, which is like saying we ended up with this delta function. 119 00:11:59,071 --> 00:12:00,047 Okay. Okay. 120 00:12:00,047 --> 00:12:06,070 So that's this, you know that's our second property of the quantum foray transform 121 00:12:06,070 --> 00:12:12,010 that. It treats periodic functions extremely 122 00:12:12,010 --> 00:12:16,039 nicely. Okay, so let's start by proving a very 123 00:12:16,039 --> 00:12:22,017 special case of this of this property of the Fourier transform. 124 00:12:22,017 --> 00:12:29,053 So would it in this special case we, you know, the superposition we start with has 125 00:12:29,053 --> 00:12:33,019 non-zero amplitudes only at multiples of R. 126 00:12:33,019 --> 00:12:36,070 And it has equal amplitudes at these points. 127 00:12:36,070 --> 00:12:43,028 So, so our initial superposition is, is zero plus R plus 2R. 128 00:12:43,028 --> 00:12:49,000 Plus one plus n minus r. We have to remember that we are, we are 129 00:12:49,000 --> 00:12:55,046 also working in the, in the special case where R divides N, and so if you look at 130 00:12:55,046 --> 00:13:02,002 the number of terms in this superposition it's there's exactly N over R of them. 131 00:13:02,002 --> 00:13:07,034 And so each of, to normalize each you'd have amplitude R over N. 132 00:13:07,034 --> 00:13:14,015 And then what, what they're claiming is that under the Fourier transform you get N 133 00:13:14,015 --> 00:13:19,039 equals superposition over zero, N over R, 2N over R, et cetera. 134 00:13:19,039 --> 00:13:26,019 And again, the number of terms here is R. So, to normalize, we put in one over 135 00:13:26,019 --> 00:13:29,051 square root R. So I think that this is, you know. 136 00:13:29,051 --> 00:13:32,093 So, if you want to understand this intuitively. 137 00:13:32,093 --> 00:13:38,036 Well, let's, let's start by looking at the very special case where you, where you 138 00:13:38,036 --> 00:13:39,083 start with. Just. 139 00:13:39,083 --> 00:13:46,049 A super position which is which is concentrated 110. 140 00:13:46,049 --> 00:13:51,049 So that would correspond to a period of N. Right? 141 00:13:51,049 --> 00:13:55,078 And now, when you take the Fourier transform. 142 00:13:55,078 --> 00:14:01,054 What this should tell us, you get a super position. 143 00:14:01,054 --> 00:14:13,083 So, Zero + N over N so, one + two + one or two, N - one or normalized by one over 144 00:14:13,083 --> 00:14:16,041 square root n. Okay? 145 00:14:16,041 --> 00:14:21,096 And, the converse also holds that if we start from the c equal superposition 146 00:14:21,096 --> 00:14:28,002 before you transform gives us back just the zero state So, let's see that this is 147 00:14:28,002 --> 00:14:31,061 actually true. So, remember what the Fourier transform 148 00:14:31,061 --> 00:14:35,008 matrix is? It's an N by N matrix, one over square 149 00:14:35,008 --> 00:14:42,000 root N, the first row is all 1s, the first column is all 1s, and here you have omega, 150 00:14:42,000 --> 00:14:46,008 omega to the N minus one, omega squared, omega to the N minus one. 151 00:14:46,008 --> 00:14:50,000 Okay, so that's the Fourier transform matrix. 152 00:14:50,000 --> 00:14:53,005 And now, what's this state, just the zero state? 153 00:14:53,005 --> 00:14:56,009 Well that's one here. Its, its amplitude is one. 154 00:14:56,009 --> 00:15:02,005 Everything else has amplitude zero. So this just picks out the first column. 155 00:15:02,005 --> 00:15:07,009 Which is exactly that state, yes. One more square exam. 156 00:15:07,009 --> 00:15:13,007 One, one, one. One, right so one in all the entries. 157 00:15:16,009 --> 00:15:21,008 And so, so that's, that's exactly equal to that state. 158 00:15:21,008 --> 00:15:26,000 And similarly, if we start with all one state. 159 00:15:26,006 --> 00:15:31,006 Then, as you can see, you'd get the inner product of the first row with that, and 160 00:15:31,006 --> 00:15:37,000 that that'll give you a one in the, in the top position and everything else will give 161 00:15:37,000 --> 00:15:39,006 us 0s. And so if you start with this state, 162 00:15:39,006 --> 00:15:43,006 you'll, you'll get that. So, now remember, you know, so intuitively 163 00:15:43,006 --> 00:15:48,002 what the Fourier transform does is if you start with this delta function. 164 00:15:48,002 --> 00:15:52,007 They are concentrated at zero. In the Fourier domain you spread out 165 00:15:52,007 --> 00:15:55,009 completely. So your, you, you have a superposition 166 00:15:55,009 --> 00:15:59,000 over everything. If you start off with N equals 167 00:15:59,000 --> 00:16:04,002 superposition over everything, you get completely focused result on the Fourier 168 00:16:04,002 --> 00:16:09,003 domain so you get, just get a, get a completely concentrated superposition on 169 00:16:09,003 --> 00:16:12,043 the zero state. Now what this, what this property is 170 00:16:12,043 --> 00:16:17,092 telling us is that if you start, you know, generalize this completely so if you start 171 00:16:17,092 --> 00:16:22,046 with period of r then in the Fourier domain, we get period n over r. 172 00:16:22,046 --> 00:16:27,032 So this, so the smaller the period on this side the larger the period in the 173 00:16:27,032 --> 00:16:32,001 foredomain and vice-versa. Okay so this is what we want to prove.