Okay. So in this video, we are going to talk about Grover's algorithm. Okay? So remember, the problem that we are trying to solve. We are given a table with capital n entries. We think of, capital n as two to the little n. And then we are given a, you know, this, this, this table is given to us in the form of a function which maps. Zero, three and minus one to zero, one. It's a Boolean function. And what we want to do is find an x such that f of x equal to one. We're going to assume we have the hardest case when, you know, the case in which there's exactly one such x, where f of x equal to one, and. There the question is. How many times do we have to evaluate f(x)? Okay, and of course classically, we have to do this at least capital land over two times. And they are aiming to do it and solve this problem with, with only square root of capital land evaluations of f(x). Okay, so it turns out that, that the algorithm to do this, the quantum algorithm to do this. Has, has two different primitives that it's going to rely on. So the first primitive that, that it relies on is what's called phase inversion. So, let's say that so, so, let's say that f(x) = 1.< /i> So that's the unique X, such that f(x) = one. Right? This is, this is the item that we are searching for. And let's say that we start with some superposition. Sum over all X of alpha X, X. So let me draw a picture of it. So let's say that this is X. And that's, alpha sub X. Okay, so, so let's say alpha sub X is just some function like that, you know, it's a V, this is the superposition. And there is X star. Okay, in phase inversion, what we want to do is take the superposition. So, this is what phase, inversion means. You want to take the superposition, okay? So, so that's, that's what it, what it looked like. Except now what we want to do is, this was X star, we want to, we want to take, Yes, so, so, we want, we want a, we want a new super position to look like this blue super position where, where X star gets its, its, its amplitude multiplied by -one. So what, what I mean by this is, on the phase inversion. The new superposition is sum of all X, nought equal to X star, nought alpha X, X. - alpha sub X star, X star. Great, so instead of a plus alpha of x star, you get a minus alpha of x star. So, I'm going to assume for the purposes of this video, that we can implement phase inversion so we can see how to actually design a circuit that, that does this in the next video. Okay, there's, there's one other. Primitive that we are going to need, which is inversion about the mean. So what's inversion about the mean? So again, let's say that we have a superposition summation of all x of x, x. So again this is our diagram. That's X, half plus X. And we are given some such, some such a, super position. Now, corresponding to this super position, we can, we can say what it's, you know what the mean value of alphas of X is, so take the average value of alphas of X, so maybe. That's something like this. So that's the average value of alpha sub x. Let's let the average be MU. So now, what we're going to do is flip everything about this, this mean line. So, so what, whatever the amplitude of x used to be. If it was below MU, then you reflect it, and make it as much above MU as it used to be below. So the new amplitude is going to, is going to follow this blue curve. So, so in other words, the amplitude of X, instead of being alpha sub X. It's two Mu, minus alpha sub X. Okay, so why is it two Mu minus alpha sub x? So let's see. If it, if it used to be at alpha sub x, what you do is, so, from alpha sub x, you go to what? Well. The difference between Mu and alpha sub x is, is, is Mu alpha sub x, so this is how much below Mu alpha sub x is, let's say, let's say that's positive. So, now you flip it around, you put it as much about Mu as it's used to be below. So the new amplitude is plus Mu minus alpha sub x, which is, two Mu - alpha sub of x. Okay. So that's, that's this operator called inversion about the mean. So now let's see, again we are going to see in the next video how to implement this transformation. So there's a quantum circuit that will carry this out for us. But for now What we care about is given these two operations, how do we actually solve the search problem? Okay, so, so this is a problem given in, given in a boolean function which is, which is one for exactly one value of X, find this value of X. Okay. So, so we first start with a equal super position over all the N items. Then we do an inversion, a phase inversion. So, so X star, the marked value. They make its, you know, instead of having amplitude one over square root in it, now has amplitude minus one over square root n. Now, the next step what we're going to do is inversion about the mean. So, what's the mean of this super position? Well the mean is pretty close to one over square root of n. So, now when we do an inversion about the mean. All these amplitudes more or less stay the same. So, they go, you know, they were just a little bit above the mean and now they become just a little below the mean. But what happens to x star is more dramatic because it used to be roughly two over square root of n below the mean. So, now it swings over and it goes two over, roughly two over square root n above the mean. But the mean was already roughly one over square root N, so, so the amplitude of X star becomes roughly three over square root of N, very close to three of square root N. Okay, so the negative factors. This sequence of two steps grows the amplitude of X star by two over square root of N, roughly. And it reduces everything else just by a tiny amount. Okay, but now what happens if you do this again? Well if, if we do this again in the next step and we do, a phase inversion, this now. X star now, goes, has an amplitude of -three over square root of N. When we do an inversion about the mean. Well it's four times four over square root of N below the mean and so it'ill go four over square root N above the mean. Which means it goes roughly to five over square root of N Okay. So in the next step if we repeat this sequence of two steps, we go to about five or square root and above the mean. All the other amplitudes, well they go down a little bit more, but they still stay very close to If you go all the way up to one over square root two. And now if you make a measurement, the chance that we see X star is. The square of one over square root two, so we see X star with probability half, that's Grovers' algorithm. Okay, so how long does it take? How many, how many saturatations does it take? Well, we seem to be increasing the amplitude by roughly two over square root N each time. So how many, how many durations does it take to, to make that, to, for the amplitude to grow all the way up to a constant? It's, it's, it's about square root of n. Maybe square root n over two. Maybe square root n over four. But that's roughly what it is. Now, of course, this analysis was bogus, because, because, of course. All these amplitudes keep decreasing from one over square root N. Each time we do this inversion about the mean. Which, which also implies that, when we do the inversion about the mean. You know, we, when we, when we do the inversion about the mean, the amplitude of x star doesn't quite go up by two over square root n each step. But it goes up by smaller and smaller amounts as we go along. Okay, so, but this is not a, this is not a big deal. This is, you know, it, it goes down only by a small amount. You know, this, this, this, this effect is sort of small. And by the time the amplitude of x star gets to one over square root two, actually these, you know, the, these, the amplitude of everything else doesn't decrease too much below one over square root n. So, so lets, lets try to figure this out. What's the, what's the amplitude of the, of, of the rest of these you know of the, of the rest of the entries when the needle X star has amplitude one over square of two? Well at this point. The remaining n minus one elements have amplitude one over square root two, and so roughly their, their amplitude is not one over square root n, but one over square root 2n. So now, at this point, how much, how much improvement are we making per step. So remember what happens, so our picture is this, we had as X, you know that the, the amplitude of everything else is above. One over square root 2n, right? It never falls below this, which means that whatever the, you know, whatever the, the amplitude of the needle was, when we do this, inversion about the mean. Well, the mean is one over square root n. One over square root 2n above the, above zero. And then when we flip it, flip it about the mean. It goes to a length of whatever its original length was plus one over square root 2n above the mean. And therefore, the increase in its length is two 1over square root 2n. Which is square root two over n. Okay, so, so now if it's, if you are, if you are increasing it by square root two over square root n, then how many steps does it take before you reach one over square root two? Well, the answer is clear. It's, it's, it's one over square root two / square root two over square root n, which is square root n / two. So that's, that's an upper bound on the number of steps required for Grover's algorithm. Okay now of course in all of this I have not told you how to implement each step, but this is what we'll do in the next video.