1 00:00:00,000 --> 00:00:03,047 Okay. So in the, in our last video, we saw how 2 00:00:03,047 --> 00:00:10,003 to, how, how Grover's algorithm works. And we showed that it requires order 3 00:00:10,003 --> 00:00:15,008 square root and iterations. But then, what we, what we also assumed is 4 00:00:15,008 --> 00:00:20,007 that we have two primitives. And one was phase inversion. 5 00:00:20,007 --> 00:00:27,028 So in phase inversion what, what, what we do is we are, we are given some 6 00:00:27,028 --> 00:00:34,006 superposition over you know, over our entries from zero to N - one. 7 00:00:34,006 --> 00:00:41,007 One of which is special, you know, this, so we are given this function from this 8 00:00:41,007 --> 00:00:47,004 domain of size of a boolean function, so it maps it to 0.1. 9 00:00:47,004 --> 00:00:53,047 And we are assuming that, that this function evaluates to one for exactly one 10 00:00:53,047 --> 00:00:58,025 such x. This is the needle in the haystack, we are 11 00:00:58,025 --> 00:01:03,034 calling it x star. And what we want to do is, we want to 12 00:01:03,034 --> 00:01:11,044 implement phase inversion, by which I mean where you look at the amplitude of x star 13 00:01:11,044 --> 00:01:14,050 and you multiply it by -one. Okay? 14 00:01:14,050 --> 00:01:19,001 So, so that's what we want to actually implement. 15 00:01:19,001 --> 00:01:23,001 So how do we implement this, this primitive? 16 00:01:24,002 --> 00:01:28,065 Okay? So first remember what, what we're 17 00:01:28,065 --> 00:01:37,064 actually given is, is, is a quantum circuit, which on input x and zero, 18 00:01:37,064 --> 00:01:44,037 outputs x and f(x). Actually you could, you know, may, maybe, 19 00:01:44,037 --> 00:01:52,072 maybe it's even better to think of, think of this as, on input x and b. 20 00:01:52,072 --> 00:02:01,011 So if your answer bet is b then, then you get b exclusive or f(x). 21 00:02:01,011 --> 00:02:08,017 So, so your answer bet gets toggled, if and only f(x) = one. 22 00:02:08,017 --> 00:02:18,065 So now, what we'd like to do is, is we'd like instead, instead of getting the 23 00:02:18,065 --> 00:02:26,067 output bit, we, what we want this circuit to do in effect for us, is we'd like it to 24 00:02:26,067 --> 00:02:33,005 map x. So, so this is, this is what, you know, 25 00:02:33,005 --> 00:02:39,001 this is what, what an ideal circuit does for us. 26 00:02:39,001 --> 00:02:46,005 What we want it to do is map x to -one^f(x)x. 27 00:02:46,005 --> 00:02:50,005 Right? So, remember f is a boolean function. 28 00:02:50,008 --> 00:02:58,000 And they're saying that f(x) is zero for almost every input, the only input on 29 00:02:58,000 --> 00:03:05,001 which f(x) is one is the needle x star. Okay, so now, if we could implement this 30 00:03:05,001 --> 00:03:12,060 kind of a, of a quantum circuit, then of course what it does is, if, if you give it 31 00:03:12,060 --> 00:03:18,063 as input summation over all x of alpha x, x, what do we get as output? 32 00:03:18,063 --> 00:03:25,003 Well, we get as output summation over all x of -one^f(x) alpha x, x. 33 00:03:25,003 --> 00:03:30,016 Right? But, but now we are saying, f(x) is, is 34 00:03:30,016 --> 00:03:37,037 one, if only for the needle x star. And so what this would do is it would 35 00:03:37,037 --> 00:03:44,054 invert the phase only of the needle, which is exactly what they wanted. 36 00:03:44,054 --> 00:03:50,073 So, how do we carry this out? Well, remember what our, what our 37 00:03:50,073 --> 00:03:53,097 observation is. Our observation was, okay. 38 00:03:53,097 --> 00:04:00,093 So this is, this is our main observation, that, if you take this function use of f, 39 00:04:00,093 --> 00:04:08,001 this circuit use of f, tou input x. And instead of inputting this, this bit b, 40 00:04:08,001 --> 00:04:12,005 you input this, this, this bit b in the state minus. 41 00:04:12,005 --> 00:04:21,001 The claim is, what this outputs is x minus, but with the phase of -one^f(x) 42 00:04:21,001 --> 00:04:27,016 Okay so where does this phase of -one^f(x) come from? 43 00:04:27,016 --> 00:04:35,004 So remember, what use of f does is, it toggles the output bit, the, the answer 44 00:04:35,004 --> 00:04:40,089 bit, if and only f(x) = one. So, if f(x) = zero, it leaves the output 45 00:04:40,089 --> 00:04:45,064 bit alone. If f of, f(x) = one, it toggles it, it 46 00:04:45,064 --> 00:04:50,044 switches it. So now, what does it do to the minus 47 00:04:50,044 --> 00:04:54,049 state? So, remember, minus is one / square root 48 00:04:54,049 --> 00:05:02,022 to zero + one / square root to one. So, we have two cases, so, case one. 49 00:05:02,022 --> 00:05:07,055 F(x) = zero. If f(x) = zero, it leaves the answer a bit 50 00:05:07,055 --> 00:05:13,060 unchanged, so, so minus gets mapped to minus. 51 00:05:13,060 --> 00:05:22,035 Case two, f(x) = one. In this case the answer bit gets doubled. 52 00:05:22,035 --> 00:05:28,029 Sorry. Minus was one / square root to zero - one 53 00:05:28,029 --> 00:05:34,022 / square root to one. Okay, now let's look at case two, f(x) is 54 00:05:34,022 --> 00:05:40,043 one it, it toggles the answer bit. So, if the answer bit was zero, it gets 55 00:05:40,043 --> 00:05:44,006 back to one, if it's one, it gets back to zero. 56 00:05:44,006 --> 00:05:52,021 So, what is it, what is minus go to? So, so now, minus gets mapped to one / 57 00:05:52,049 --> 00:06:02,052 square root to zero gets mapped to one and one gets mapped to zero, so this is equal 58 00:06:02,052 --> 00:06:11,038 to, well, this is the same as a minus state but with the phase of -one. 59 00:06:11,038 --> 00:06:15,089 Okay? So, so the phase you get is +, in the case 60 00:06:15,089 --> 00:06:21,007 f(x)=0 and minus in the case, f(x) = one which is exactly -one^f(x). 61 00:06:21,007 --> 00:06:24,007 So that's what we were looking for. Okay. 62 00:06:24,007 --> 00:06:29,000 So, so the circuit to do phase inversion is exactly this. 63 00:06:29,000 --> 00:06:35,001 So you just, you just use the circuit for comp, quantum circuit for computing f, 64 00:06:35,001 --> 00:06:41,001 except in the answer bit, instead of having it start at zero, you have it start 65 00:06:41,001 --> 00:06:43,004 in the minus state. So, very simple. 66 00:06:43,004 --> 00:06:49,008 Now how about reflection about the mean? So what was this reflection about the mean 67 00:06:49,008 --> 00:06:53,002 operator? So remember what we wanted, we, we, we 68 00:06:53,002 --> 00:06:58,050 were, we started with some superposition over, over, over a domain from zero to N 69 00:06:58,050 --> 00:07:03,063 -one. And now, let's compute, let, we, we are 70 00:07:03,063 --> 00:07:09,007 letting MU be the, be the average of the alpha sub X's. 71 00:07:09,007 --> 00:07:14,002 Right? So, so, we start with some superposition. 72 00:07:14,002 --> 00:07:20,009 X of alpha sub x, x. And we let MU be summation of alpha x 73 00:07:20,009 --> 00:07:26,008 divided by, divided by, I guess they are capital N elements. 74 00:07:26,008 --> 00:07:32,002 And now, what we want the new superposition to be after it is the 75 00:07:32,002 --> 00:07:38,026 reflection about the mean is, well, each amplitude, if it's above the mean, it goes 76 00:07:38,026 --> 00:07:44,096 as much below the mean as it was above. If it's below, then it gets reflected and 77 00:07:44,096 --> 00:07:46,069 goes above. Alright? 78 00:07:46,069 --> 00:07:56,001 So we want the new superposition to be sum / x of two MU - alpha sub x, x. 79 00:07:56,005 --> 00:08:03,086 Okay. So how does, what, what kind of circuit 80 00:08:03,086 --> 00:08:08,070 implements this? So actually the circuit to implement this 81 00:08:08,070 --> 00:08:13,068 is very simple. So all you do is you take your N and put 82 00:08:13,068 --> 00:08:18,044 bits, you first do another mark transform on them. 83 00:08:18,044 --> 00:08:26,093 Then, you put them through a circuit. Okay, so, so this is x, this is minus. 84 00:08:26,093 --> 00:08:36,026 Okay, so same trick as with the phase inversion, but now what this circuit does 85 00:08:36,026 --> 00:08:46,008 is, it, it's supposed to output. Okay so, so this is computing the function 86 00:08:46,008 --> 00:08:58,083 f, so it's computing the function g, where g(x) = zero if x is all 0's and it's one 87 00:08:58,083 --> 00:09:00,053 otherwise. Okay? 88 00:09:00,053 --> 00:09:07,088 So, so only if, if the, if all N input bits are zero does, does this function 89 00:09:07,088 --> 00:09:12,078 output one, and otherwise it outputs all outputs. 90 00:09:12,078 --> 00:09:17,020 Sorry, it, it outputs zero, otherwise it outputs one. 91 00:09:17,020 --> 00:09:26,005 Meaning that once you put minus in the output bit, what it's doing is it's 92 00:09:26,005 --> 00:09:33,070 putting a phase of -one on all those X's. On all X's except, except when x is all 93 00:09:33,070 --> 00:09:37,033 0's. And then we, again, do a Hadamard 94 00:09:37,033 --> 00:09:41,062 transform over the, over the first N cubits. 95 00:09:41,062 --> 00:09:46,075 Okay, so why does this work? Okay, so here's, here's why it works. 96 00:09:46,075 --> 00:09:51,064 So let's try to understand it. So, doing a reflection about the mean is 97 00:09:51,064 --> 00:09:56,030 the same as doing a reflection about. Okay, here, here's, here's intuitive, 98 00:09:56,030 --> 00:10:01,024 intuitively what, what you want to do is a reflection about this uniform 99 00:10:01,024 --> 00:10:08,041 superposition over all x. Okay, so, so how would you do this? 100 00:10:08,041 --> 00:10:16,042 Well, what we do is we first move this uniform superposition to the all 0's 101 00:10:16,042 --> 00:10:21,031 vector. So we want to first do some transformation 102 00:10:21,031 --> 00:10:28,007 that maps, maps U. We want to map it to the all zero string. 103 00:10:28,007 --> 00:10:32,004 So which transformation maps you to the all zero string? 104 00:10:33,005 --> 00:10:40,007 Of course its a Hadamard Transform. So, we first map U to the all zero string. 105 00:10:40,007 --> 00:10:45,009 And now we want to, we want to make sure that we do an inversion about zero. 106 00:10:45,009 --> 00:10:51,001 So how do you do an inversion about zero? Well, you use this transformation. 107 00:10:51,004 --> 00:11:00,038 So use the transformation where you leave the all zero string alone but you invert 108 00:11:00,038 --> 00:11:05,011 the phase of everything else. Alright? 109 00:11:05,011 --> 00:11:10,002 You, you reflect everything else. Okay. 110 00:11:10,036 --> 00:11:19,016 So to the Hadamard transform to transform this, and then you do a Hadamard transform 111 00:11:19,016 --> 00:11:24,003 back. Okay, well this is the intuition but now 112 00:11:24,003 --> 00:11:33,005 lets see that this does the right thing. So you could write this as Hadamard 113 00:11:33,005 --> 00:11:42,043 transform times. Well, you could try this as two, zero 114 00:11:42,044 --> 00:11:55,034 minus Identity matrix times the Hadamard transform. 115 00:11:55,034 --> 00:12:04,030 Okay, so, so what is this? This is the Hadamard transform times two 116 00:12:04,030 --> 00:12:17,068 zero, zero, zero. The Hadamard transform minus H identity h. 117 00:12:17,068 --> 00:12:29,002 But remember this, The Hadamard transform times itself is just identity, so you just 118 00:12:29,002 --> 00:12:31,091 get identity. And so. 119 00:12:31,091 --> 00:12:38,022 So, what about this first term, how do you figure this out? 120 00:12:38,022 --> 00:12:44,052 So remember what, what, what, you know, if you, if you, if you try and multiply this 121 00:12:44,052 --> 00:12:51,065 out, remember the first, the first row and column of the Hadamard matrix is just, 122 00:12:51,065 --> 00:12:56,058 every entry is one / square root of N. Right? 123 00:12:56,058 --> 00:13:07,044 And so if you, if you multiply this out, what you get is, is, you, you, you will, 124 00:13:07,044 --> 00:13:13,083 you will multiply one / square root ten one / square root ten two for every entry 125 00:13:13,083 --> 00:13:26,021 so you'll get a, get a matrix, which is two / N. The every entry is, okay so every 126 00:13:26,021 --> 00:13:39,099 entry is two / N minus identity. Okay so, so if you were to write out this, 127 00:13:39,099 --> 00:13:52,052 this, this transformation, it's two / N - one, two / N - one And then, every other 128 00:13:52,052 --> 00:14:03,030 entries two / N. Okay. Okay. 129 00:14:03,030 --> 00:14:10,004 So now, let's, let's try to understand why this is a reflection about the mean. 130 00:14:11,001 --> 00:14:15,071 So remember what, what, what, what we, what we are saying, we are saying that the 131 00:14:15,071 --> 00:14:20,076 Hadamard transform, sorry, the, the reflection about the mean is, you do a 132 00:14:20,076 --> 00:14:26,038 Hadamard transform, you do this, this, this kind of phase inversion, where you 133 00:14:26,038 --> 00:14:31,077 invert the phase of everything which is not the all zero string and then you do a 134 00:14:31,077 --> 00:14:38,000 Hadamard transform again. Okay, and we, we are claiming that this 135 00:14:38,000 --> 00:14:54,000 operator. If you work it out, is to the diagonal. 136 00:14:55,000 --> 00:14:59,003 Every entry on the diagonal is two / N - one. 137 00:14:59,003 --> 00:15:10,008 And every other entry, every off diagonal entry is two / N. Okay. 138 00:15:10,008 --> 00:15:22,000 So, so now, let's understand what this does if our input superposition is 139 00:15:22,000 --> 00:15:32,056 summation / x, alpha x, x. Okay, so, so we have alpha zero, alpha N - 140 00:15:32,056 --> 00:15:36,000 one. Okay. 141 00:15:36,000 --> 00:15:42,097 So what do we get? But what's the, what's the, what's the 142 00:15:42,097 --> 00:15:49,056 first entry going to be? Well, you'll get, first you'll get a two / 143 00:15:49,056 --> 00:16:00,001 N alpha not plus, so what's two / N alpha not + two / N alpha one + alpha N - one 144 00:16:00,001 --> 00:16:09,070 Where this is just two times the average of these alphas, so it's two mean. 145 00:16:09,070 --> 00:16:13,086 Right, so what's, what's the first entry going to be? 146 00:16:13,086 --> 00:16:21,009 Well you'll get two MU - alpha not. What's the second entry? 147 00:16:21,009 --> 00:16:29,003 We'll again get two MU, but now the -one is in the second entry so you'll get two 148 00:16:29,004 --> 00:16:39,008 MU - alpha one, two MU - alpha N - one. So, so this gets mapped to summation over 149 00:16:39,008 --> 00:16:46,057 all x of 2MU - alpha sub x, x. This is exactly the inversion about the 150 00:16:46,057 --> 00:16:50,058 mean operation that we were looking for. Okay. 151 00:16:50,058 --> 00:16:57,097 So now we are, we are all set to go. We understand how to do a reflection about 152 00:16:57,097 --> 00:17:03,000 the mean, and how to do a phase in version. 153 00:17:03,000 --> 00:17:10,070 Okay, so, so remember what, what, what are, you know, what, what we wanted to do 154 00:17:10,070 --> 00:17:18,098 in our, in our implementation of the of Grover's algorithm was, was we first start 155 00:17:18,098 --> 00:17:26,032 off with an equal super position. So, remember this, these, these were the 156 00:17:26,032 --> 00:17:31,057 steps. So, so we first wish to start off with an 157 00:17:31,057 --> 00:17:41,031 equals super position. Over all the, over all numbers from zero 158 00:17:41,031 --> 00:17:50,003 to N. Or in other words above all the ended 159 00:17:50,003 --> 00:17:56,027 strings so we do a Hadamard transform. So, that's our initialization. 160 00:17:56,027 --> 00:18:07,000 Okay, so this is initialize. Then we want to do a phase reflection. 161 00:18:07,000 --> 00:18:13,007 So if this was x star, we want to take this and reflect it. 162 00:18:14,000 --> 00:18:18,008 Okay. So how do you do a, do a phase reflection? 163 00:18:18,008 --> 00:18:23,012 Remember? So this was, this is, what does the, 164 00:18:23,012 --> 00:18:26,033 sorry. The phase inversion. 165 00:18:26,033 --> 00:18:30,061 Right? We feed in a minus in the, in the answer 166 00:18:30,061 --> 00:18:33,060 bit and we compute U sub f. Right? 167 00:18:33,060 --> 00:18:40,058 Our quantum circuit for computing f. Then we want to do a inversion about the 168 00:18:40,058 --> 00:18:52,061 mean. And remember, our circuit for that was you 169 00:18:52,061 --> 00:18:59,073 do a Hadamard transform, then you do this, you have the circuit for checking whether, 170 00:18:59,073 --> 00:19:05,085 whether the input is the all zero string, and if, if not, then it outputs one. 171 00:19:05,085 --> 00:19:11,084 But again, since our answer bit is a minus, that puts the answer in the phase. 172 00:19:11,084 --> 00:19:18,057 And then we do a Hadamard transform again to switch back into the standard basis. 173 00:19:18,057 --> 00:19:22,064 Okay. So, so when we do the inversion about the 174 00:19:22,064 --> 00:19:39,029 mean that increases, you know so, so when we do the inversion about the mean the 175 00:19:39,029 --> 00:19:44,090 amplitude of x star shoots up, and then we want to repeat these, these two steps over 176 00:19:44,090 --> 00:19:49,004 and over again. So you want to do a phase inversion and 177 00:19:49,004 --> 00:19:54,010 inversion about mean. Okay, and so that's what that's what the 178 00:19:54,010 --> 00:19:59,083 circuit looks like, so we initialize, we do phase inversion, inversion about the 179 00:19:59,083 --> 00:20:06,055 mean, then we do a phase inversion again, we do an inversion about the mean again, 180 00:20:06,055 --> 00:20:11,004 and so on and so on. So the circuit sort of gets extended out 181 00:20:11,004 --> 00:20:16,008 and there are, there are, there are order square root of N such phases. 182 00:20:16,008 --> 00:20:22,050 Right? So, initialization followed by this, this 183 00:20:22,050 --> 00:20:28,063 circuit, this part of the circuit. Phase inversion plus inversion about the 184 00:20:28,063 --> 00:20:32,033 mean gets repeated order square root N times. 185 00:20:32,033 --> 00:20:37,031 And then, you measure. You measure this, this first, these first 186 00:20:37,031 --> 00:20:41,032 N cubits. And with probability at least a half, you 187 00:20:41,032 --> 00:20:44,054 get to see the needle. Okay. 188 00:20:44,054 --> 00:20:49,070 But with probability of about a half, you may not get the needle. 189 00:20:49,070 --> 00:20:55,059 So what you do, you go, you, you, you now take the outcome of your measurement and 190 00:20:55,059 --> 00:21:01,003 you look inside that entry, if its marked you are done, if not you repeat this whole 191 00:21:01,003 --> 00:21:03,062 process again. Okay. 192 00:21:03,062 --> 00:21:12,004 One other observation about Grover's algorithm which is that, you have to, you 193 00:21:12,004 --> 00:21:19,008 have to get this number right. If you let the, let Grover's algorithm run 194 00:21:19,008 --> 00:21:25,083 for too long, then it might uncompute the answer, so, you know, it, it keeps going 195 00:21:25,083 --> 00:21:31,051 along, this keeps increasing in height, the, the, amplitude of the needle keeps 196 00:21:31,051 --> 00:21:36,082 increasing in height. But eventually, and this is a good 197 00:21:36,082 --> 00:21:43,021 exercise for you to work out, you should check that the, that the amplitude of the 198 00:21:43,021 --> 00:21:47,097 needle after it attains its maximum value, it'll start reducing. 199 00:21:47,097 --> 00:21:54,052 And the amplitudes of these other entries will keep going up until the needle then 200 00:21:54,052 --> 00:22:00,000 becomes extremely unlikely. So, so, one of the important things in 201 00:22:00,000 --> 00:22:05,006 Grover's algorithm is that you've got to, you've got to set this parameter. 202 00:22:05,006 --> 00:22:11,007 So, for example, if there were more than one marked items, then Grover's algorithm 203 00:22:11,007 --> 00:22:16,001 will run faster. But you'll, you'll actually have to reduce 204 00:22:16,001 --> 00:22:20,000 this number of iterations appropriately. Okay. 205 00:22:20,000 --> 00:22:23,007 Grover's algorithm also is fairly general, you know. 206 00:22:23,007 --> 00:22:29,050 Even though it only gives a quadratic speeder so it doesn't give an exponential 207 00:22:29,050 --> 00:22:35,056 speeder But, the trade off is, that it, it solves an extremely general problem. 208 00:22:35,056 --> 00:22:40,057 And this, you know, the ideas behind Grover's algorithm have since been used in 209 00:22:40,057 --> 00:22:46,032 a number of different settings to solve a, you know, a, a range of different kinds of 210 00:22:46,032 --> 00:22:49,055 problems. And so if you look in the, in the notes, 211 00:22:49,055 --> 00:22:55,004 you will find, find pointers to some of the applications of Grover's algorithm.