1 00:00:00,000 --> 00:00:03,004 Okay. So in this video, we are going to talk 2 00:00:03,004 --> 00:00:05,008 about Grover's algorithm. Okay? 3 00:00:05,008 --> 00:00:10,000 So remember, the problem that we are trying to solve. 4 00:00:10,000 --> 00:00:13,006 We are given a table with capital n entries. 5 00:00:13,006 --> 00:00:17,005 We think of, capital n as two to the little n. 6 00:00:17,005 --> 00:00:23,041 And then we are given a, you know, this, this, this table is given to us in the 7 00:00:23,041 --> 00:00:29,002 form of a function which maps. Zero, three and minus one to zero, one. 8 00:00:29,002 --> 00:00:34,000 It's a Boolean function. And what we want to do is find an x such 9 00:00:34,000 --> 00:00:39,000 that f of x equal to one. We're going to assume we have the hardest 10 00:00:39,000 --> 00:00:44,007 case when, you know, the case in which there's exactly one such x, where f of x 11 00:00:44,007 --> 00:00:48,006 equal to one, and. There the question is. 12 00:00:48,008 --> 00:00:53,000 How many times do we have to evaluate f(x)? 13 00:00:53,000 --> 00:00:59,002 Okay, and of course classically, we have to do this at least capital land over two 14 00:00:59,002 --> 00:01:02,006 times. And they are aiming to do it and solve 15 00:01:02,006 --> 00:01:08,004 this problem with, with only square root of capital land evaluations of f(x). 16 00:01:08,004 --> 00:01:13,006 Okay, so it turns out that, that the algorithm to do this, the quantum 17 00:01:13,006 --> 00:01:18,007 algorithm to do this. Has, has two different primitives that 18 00:01:18,007 --> 00:01:24,001 it's going to rely on. So the first primitive that, that it 19 00:01:24,001 --> 00:01:28,001 relies on is what's called phase inversion. 20 00:01:28,001 --> 00:01:37,010 So, let's say that so, so, let's say that f(x) = 1.< /i> So that's the unique X, 21 00:01:37,010 --> 00:01:39,075 such that f(x) = one. Right? 22 00:01:39,075 --> 00:01:45,035 This is, this is the item that we are searching for. 23 00:01:45,035 --> 00:01:50,036 And let's say that we start with some superposition. 24 00:01:50,036 --> 00:01:56,020 Sum over all X of alpha X, X. So let me draw a picture of it. 25 00:01:56,020 --> 00:02:01,060 So let's say that this is X. And that's, alpha sub X. 26 00:02:01,060 --> 00:02:09,057 Okay, so, so let's say alpha sub X is just some function like that, you know, it's a 27 00:02:09,057 --> 00:02:13,070 V, this is the superposition. And there is X star. 28 00:02:13,070 --> 00:02:20,011 Okay, in phase inversion, what we want to do is take the superposition. 29 00:02:20,011 --> 00:02:31,000 So, this is what phase, inversion means. You want to take the superposition, okay? 30 00:02:31,000 --> 00:02:37,000 So, so that's, that's what it, what it looked like. 31 00:02:37,000 --> 00:02:49,051 Except now what we want to do is, this was X star, we want to, we want to take, Yes, 32 00:02:49,051 --> 00:02:57,072 so, so, we want, we want a, we want a new super position to look like this blue 33 00:02:57,072 --> 00:03:07,057 super position where, where X star gets its, its, its amplitude multiplied by 34 00:03:07,057 --> 00:03:12,005 -one. So what, what I mean by this is, on the 35 00:03:12,005 --> 00:03:20,009 phase inversion. The new superposition is sum of all X, 36 00:03:20,009 --> 00:03:32,050 nought equal to X star, nought alpha X, X. - alpha sub X star, X star. 37 00:03:32,050 --> 00:03:37,091 Great, so instead of a plus alpha of x star, you get a minus alpha of x star. 38 00:03:37,091 --> 00:03:44,008 So, I'm going to assume for the purposes of this video, that we can implement phase 39 00:03:44,008 --> 00:03:49,091 inversion so we can see how to actually design a circuit that, that does this in 40 00:03:49,091 --> 00:03:53,055 the next video. Okay, there's, there's one other. 41 00:03:53,055 --> 00:03:59,024 Primitive that we are going to need, which is inversion about the mean. 42 00:03:59,024 --> 00:04:05,025 So what's inversion about the mean? So again, let's say that we have a 43 00:04:05,025 --> 00:04:12,052 superposition summation of all x of x, x. So again this is our diagram. 44 00:04:12,052 --> 00:04:20,011 That's X, half plus X. And we are given some such, some such a, 45 00:04:20,011 --> 00:04:25,077 super position. Now, corresponding to this super position, 46 00:04:25,077 --> 00:04:37,069 we can, we can say what it's, you know what the mean value of alphas of X is, so 47 00:04:37,069 --> 00:04:42,005 take the average value of alphas of X, so maybe. 48 00:04:42,008 --> 00:04:48,005 That's something like this. So that's the average value of alpha sub 49 00:04:48,005 --> 00:04:51,000 x. Let's let the average be MU. 50 00:04:51,000 --> 00:04:57,003 So now, what we're going to do is flip everything about this, this mean line. 51 00:04:57,003 --> 00:05:01,005 So, so what, whatever the amplitude of x used to be. 52 00:05:01,005 --> 00:05:08,004 If it was below MU, then you reflect it, and make it as much above MU as it used to 53 00:05:08,004 --> 00:05:12,006 be below. So the new amplitude is going to, is going 54 00:05:12,006 --> 00:05:25,041 to follow this blue curve. So, so in other words, the amplitude of X, 55 00:05:25,041 --> 00:05:34,001 instead of being alpha sub X. It's two Mu, minus alpha sub X. 56 00:05:34,005 --> 00:05:38,009 Okay, so why is it two Mu minus alpha sub x? 57 00:05:38,009 --> 00:05:44,000 So let's see. If it, if it used to be at alpha sub x, 58 00:05:44,000 --> 00:05:49,000 what you do is, so, from alpha sub x, you go to what? 59 00:05:49,000 --> 00:05:52,083 Well. The difference between Mu and alpha sub x 60 00:05:52,083 --> 00:06:00,041 is, is, is Mu alpha sub x, so this is how much below Mu alpha sub x is, let's say, 61 00:06:00,041 --> 00:06:06,003 let's say that's positive. So, now you flip it around, you put it as 62 00:06:06,003 --> 00:06:12,053 much about Mu as it's used to be below. So the new amplitude is plus Mu minus 63 00:06:12,053 --> 00:06:16,057 alpha sub x, which is, two Mu - alpha sub of x. 64 00:06:16,057 --> 00:06:20,005 Okay. So that's, that's this operator called 65 00:06:20,005 --> 00:06:24,090 inversion about the mean. So now let's see, again we are going to 66 00:06:24,090 --> 00:06:29,005 see in the next video how to implement this transformation. 67 00:06:31,004 --> 00:06:33,004 So there's a quantum circuit that will carry this out for us. 68 00:06:33,004 --> 00:06:40,006 But for now What we care about is given these two operations, how do we actually 69 00:06:40,006 --> 00:06:48,002 solve the search problem? Okay, so, so this is a problem given in, 70 00:06:48,002 --> 00:06:54,004 given in a boolean function which is, which is one for exactly one value of X, 71 00:06:54,004 --> 00:06:57,002 find this value of X. Okay. 72 00:06:57,002 --> 00:07:05,009 So, so we first start with a equal super position over all the N items. 73 00:07:08,001 --> 00:07:12,005 Then we do an inversion, a phase inversion. 74 00:07:12,005 --> 00:07:19,009 So, so X star, the marked value. They make its, you know, instead of having 75 00:07:19,009 --> 00:07:25,009 amplitude one over square root in it, now has amplitude minus one over square root 76 00:07:25,009 --> 00:07:29,000 n. Now, the next step what we're going to do 77 00:07:29,000 --> 00:07:33,004 is inversion about the mean. So, what's the mean of this super 78 00:07:33,004 --> 00:07:37,001 position? Well the mean is pretty close to one over 79 00:07:37,001 --> 00:07:42,002 square root of n. So, now when we do an inversion about the 80 00:07:42,002 --> 00:07:47,003 mean. All these amplitudes more or less stay the 81 00:07:47,003 --> 00:07:50,002 same. So, they go, you know, they were just a 82 00:07:50,002 --> 00:07:55,005 little bit above the mean and now they become just a little below the mean. 83 00:07:55,005 --> 00:08:01,000 But what happens to x star is more dramatic because it used to be roughly two 84 00:08:01,000 --> 00:08:06,003 over square root of n below the mean. So, now it swings over and it goes two 85 00:08:06,003 --> 00:08:09,009 over, roughly two over square root n above the mean. 86 00:08:09,009 --> 00:08:14,071 But the mean was already roughly one over square root N, so, so the amplitude of X 87 00:08:14,071 --> 00:08:20,051 star becomes roughly three over square root of N, very close to three of square 88 00:08:20,051 --> 00:08:26,001 root N. Okay, so the negative factors. 89 00:08:26,001 --> 00:08:34,050 This sequence of two steps grows the amplitude of X star by two over square 90 00:08:34,050 --> 00:08:39,090 root of N, roughly. And it reduces everything else just by a 91 00:08:39,090 --> 00:08:45,056 tiny amount. Okay, but now what happens if you do this 92 00:08:45,056 --> 00:08:50,015 again? Well if, if we do this again in the next 93 00:08:50,015 --> 00:08:54,081 step and we do, a phase inversion, this now. 94 00:08:54,081 --> 00:09:02,000 X star now, goes, has an amplitude of -three over square root of N. 95 00:09:03,000 --> 00:09:08,008 When we do an inversion about the mean. Well it's four times four over square root 96 00:09:08,008 --> 00:09:14,002 of N below the mean and so it'ill go four over square root N above the mean. 97 00:09:14,002 --> 00:09:19,005 Which means it goes roughly to five over square root of N Okay. 98 00:09:19,005 --> 00:09:28,000 So in the next step if we repeat this sequence of two steps, we go to about five 99 00:09:28,000 --> 00:09:35,006 or square root and above the mean. All the other amplitudes, well they go 100 00:09:35,006 --> 00:09:44,000 down a little bit more, but they still stay very close to If you go all the way 101 00:09:44,000 --> 00:09:49,035 up to one over square root two. And now if you make a measurement, the 102 00:09:49,035 --> 00:09:55,009 chance that we see X star is. The square of one over square root two, so 103 00:09:55,009 --> 00:10:00,005 we see X star with probability half, that's Grovers' algorithm. 104 00:10:00,008 --> 00:10:05,009 Okay, so how long does it take? How many, how many saturatations does it 105 00:10:05,009 --> 00:10:08,007 take? Well, we seem to be increasing the 106 00:10:08,007 --> 00:10:12,009 amplitude by roughly two over square root N each time. 107 00:10:13,005 --> 00:10:18,004 So how many, how many durations does it take to, to make that, to, for the 108 00:10:18,004 --> 00:10:21,007 amplitude to grow all the way up to a constant? 109 00:10:21,007 --> 00:10:26,004 It's, it's, it's about square root of n. Maybe square root n over two. 110 00:10:26,004 --> 00:10:30,006 Maybe square root n over four. But that's roughly what it is. 111 00:10:30,006 --> 00:10:35,001 Now, of course, this analysis was bogus, because, because, of course. 112 00:10:35,008 --> 00:10:40,004 All these amplitudes keep decreasing from one over square root N. 113 00:10:41,004 --> 00:10:44,007 Each time we do this inversion about the mean. 114 00:10:44,007 --> 00:10:49,007 Which, which also implies that, when we do the inversion about the mean. 115 00:10:49,007 --> 00:10:55,001 You know, we, when we, when we do the inversion about the mean, the amplitude of 116 00:10:55,001 --> 00:10:59,006 x star doesn't quite go up by two over square root n each step. 117 00:10:59,006 --> 00:11:03,009 But it goes up by smaller and smaller amounts as we go along. 118 00:11:03,009 --> 00:11:07,004 Okay, so, but this is not a, this is not a big deal. 119 00:11:07,004 --> 00:11:11,004 This is, you know, it, it goes down only by a small amount. 120 00:11:11,004 --> 00:11:15,004 You know, this, this, this, this effect is sort of small. 121 00:11:15,004 --> 00:11:22,006 And by the time the amplitude of x star gets to one over square root two, actually 122 00:11:22,006 --> 00:11:29,005 these, you know, the, these, the amplitude of everything else doesn't decrease too 123 00:11:29,005 --> 00:11:35,091 much below one over square root n. So, so lets, lets try to figure this out. 124 00:11:35,091 --> 00:11:44,053 What's the, what's the amplitude of the, of, of the rest of these you know of the, 125 00:11:44,053 --> 00:11:52,065 of the rest of the entries when the needle X star has amplitude one over square of 126 00:11:52,065 --> 00:11:54,096 two? Well at this point. 127 00:11:54,096 --> 00:12:03,062 The remaining n minus one elements have amplitude one over square root two, and so 128 00:12:03,062 --> 00:12:13,000 roughly their, their amplitude is not one over square root n, but one over square 129 00:12:13,000 --> 00:12:18,022 root 2n. So now, at this point, how much, how much 130 00:12:18,022 --> 00:12:26,069 improvement are we making per step. So remember what happens, so our picture 131 00:12:26,069 --> 00:12:37,089 is this, we had as X, you know that the, the amplitude of everything else is above. 132 00:12:37,089 --> 00:12:45,097 One over square root 2n, right? It never falls below this, which means 133 00:12:45,097 --> 00:12:54,019 that whatever the, you know, whatever the, the amplitude of the needle was, when we 134 00:12:54,019 --> 00:13:03,005 do this, inversion about the mean. Well, the mean is one over square root n. 135 00:13:03,005 --> 00:13:07,003 One over square root 2n above the, above zero. 136 00:13:07,003 --> 00:13:11,003 And then when we flip it, flip it about the mean. 137 00:13:11,003 --> 00:13:16,072 It goes to a length of whatever its original length was plus one over square 138 00:13:16,072 --> 00:13:22,008 root 2n above the mean. And therefore, the increase in its length 139 00:13:22,008 --> 00:13:28,002 is two 1over square root 2n. Which is square root two over n. 140 00:13:29,002 --> 00:13:37,049 Okay, so, so now if it's, if you are, if you are increasing it by square root two 141 00:13:37,049 --> 00:13:44,037 over square root n, then how many steps does it take before you reach one over 142 00:13:44,037 --> 00:13:48,000 square root two? Well, the answer is clear. 143 00:13:48,000 --> 00:13:54,007 It's, it's, it's one over square root two / square root two over square root n, 144 00:13:54,007 --> 00:14:01,060 which is square root n / two. So that's, that's an upper bound on the 145 00:14:01,060 --> 00:14:06,021 number of steps required for Grover's algorithm. 146 00:14:06,021 --> 00:14:12,095 Okay now of course in all of this I have not told you how to implement each step, 147 00:14:12,095 --> 00:14:15,009 but this is what we'll do in the next video.