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. 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.