Okay.
So in the, in our last video, we saw how
to, how, how Grover's algorithm works.
And we showed that it requires order
square root and iterations.
But then, what we, what we also assumed is
that we have two primitives.
And one was phase inversion.
So in phase inversion what, what, what we
do is we are, we are given some
superposition over you know, over our
entries from zero to N - one.
One of which is special, you know, this,
so we are given this function from this
domain of size of a boolean function, so
it maps it to 0.1.
And we are assuming that, that this
function evaluates to one for exactly one
such x.
This is the needle in the haystack, we are
calling it x star.
And what we want to do is, we want to
implement phase inversion, by which I mean
where you look at the amplitude of x star
and you multiply it by -one.
Okay?
So, so that's what we want to actually
implement.
So how do we implement this, this
primitive?
Okay?
So first remember what, what we're
actually given is, is, is a quantum
circuit, which on input x and zero,
outputs x and f(x).
Actually you could, you know, may, maybe,
maybe it's even better to think of, think
of this as, on input x and b.
So if your answer bet is b then, then you
get b exclusive or f(x).
So, so your answer bet gets toggled, if
and only f(x) = one.
So now, what we'd like to do is, is we'd
like instead, instead of getting the
output bit, we, what we want this circuit
to do in effect for us, is we'd like it to
map x.
So, so this is, this is what, you know,
this is what, what an ideal circuit does
for us.
What we want it to do is map x to
-one^f(x)x.
Right?
So, remember f is a boolean function.
And they're saying that f(x) is zero for
almost every input, the only input on
which f(x) is one is the needle x star.
Okay, so now, if we could implement this
kind of a, of a quantum circuit, then of
course what it does is, if, if you give it
as input summation over all x of alpha x,
x, what do we get as output?
Well, we get as output summation over all
x of -one^f(x) alpha x, x.
Right?
But, but now we are saying, f(x) is, is
one, if only for the needle x star.
And so what this would do is it would
invert the phase only of the needle, which
is exactly what they wanted.
So, how do we carry this out?
Well, remember what our, what our
observation is.
Our observation was, okay.
So this is, this is our main observation,
that, if you take this function use of f,
this circuit use of f, tou input x.
And instead of inputting this, this bit b,
you input this, this, this bit b in the
state minus.
The claim is, what this outputs is x
minus, but with the phase of -one^f(x)
Okay so where does this phase of -one^f(x)
come from?
So remember, what use of f does is, it
toggles the output bit, the, the answer
bit, if and only f(x) = one.
So, if f(x) = zero, it leaves the output
bit alone.
If f of, f(x) = one, it toggles it, it
switches it.
So now, what does it do to the minus
state?
So, remember, minus is one / square root
to zero + one / square root to one.
So, we have two cases, so, case one.
F(x) = zero.
If f(x) = zero, it leaves the answer a bit
unchanged, so, so minus gets mapped to
minus.
Case two, f(x) = one.
In this case the answer bit gets doubled.
Sorry.
Minus was one / square root to zero - one
/ square root to one.
Okay, now let's look at case two, f(x) is
one it, it toggles the answer bit.
So, if the answer bit was zero, it gets
back to one, if it's one, it gets back to
zero.
So, what is it, what is minus go to?
So, so now, minus gets mapped to one /
square root to zero gets mapped to one and
one gets mapped to zero, so this is equal
to, well, this is the same as a minus
state but with the phase of -one.
Okay?
So, so the phase you get is +, in the case
f(x)=0 and minus in the case, f(x) = one
which is exactly -one^f(x).
So that's what we were looking for.
Okay.
So, so the circuit to do phase inversion
is exactly this.
So you just, you just use the circuit for
comp, quantum circuit for computing f,
except in the answer bit, instead of
having it start at zero, you have it start
in the minus state.
So, very simple.
Now how about reflection about the mean?
So what was this reflection about the mean
operator?
So remember what we wanted, we, we, we
were, we started with some superposition
over, over, over a domain from zero to N
-one.
And now, let's compute, let, we, we are
letting MU be the, be the average of the
alpha sub X's.
Right?
So, so, we start with some superposition.
X of alpha sub x, x.
And we let MU be summation of alpha x
divided by, divided by, I guess they are
capital N elements.
And now, what we want the new
superposition to be after it is the
reflection about the mean is, well, each
amplitude, if it's above the mean, it goes
as much below the mean as it was above.
If it's below, then it gets reflected and
goes above.
Alright?
So we want the new superposition to be sum
/ x of two MU - alpha sub x, x.
Okay.
So how does, what, what kind of circuit
implements this?
So actually the circuit to implement this
is very simple.
So all you do is you take your N and put
bits, you first do another mark transform
on them.
Then, you put them through a circuit.
Okay, so, so this is x, this is minus.
Okay, so same trick as with the phase
inversion, but now what this circuit does
is, it, it's supposed to output.
Okay so, so this is computing the function
f, so it's computing the function g, where
g(x) = zero if x is all 0's and it's one
otherwise.
Okay?
So, so only if, if the, if all N input
bits are zero does, does this function
output one, and otherwise it outputs all
outputs.
Sorry, it, it outputs zero, otherwise it
outputs one.
Meaning that once you put minus in the
output bit, what it's doing is it's
putting a phase of -one on all those X's.
On all X's except, except when x is all
0's.
And then we, again, do a Hadamard
transform over the, over the first N
cubits.
Okay, so why does this work?
Okay, so here's, here's why it works.
So let's try to understand it.
So, doing a reflection about the mean is
the same as doing a reflection about.
Okay, here, here's, here's intuitive,
intuitively what, what you want to do is a
reflection about this uniform
superposition over all x.
Okay, so, so how would you do this?
Well, what we do is we first move this
uniform superposition to the all 0's
vector.
So we want to first do some transformation
that maps, maps U.
We want to map it to the all zero string.
So which transformation maps you to the
all zero string?
Of course its a Hadamard Transform.
So, we first map U to the all zero string.
And now we want to, we want to make sure
that we do an inversion about zero.
So how do you do an inversion about zero?
Well, you use this transformation.
So use the transformation where you leave
the all zero string alone but you invert
the phase of everything else.
Alright?
You, you reflect everything else.
Okay.
So to the Hadamard transform to transform
this, and then you do a Hadamard transform
back.
Okay, well this is the intuition but now
lets see that this does the right thing.
So you could write this as Hadamard
transform times.
Well, you could try this as two, zero
minus Identity matrix times the Hadamard
transform.
Okay, so, so what is this?
This is the Hadamard transform times two
zero, zero, zero.
The Hadamard transform minus H identity h.
But remember this, The Hadamard transform
times itself is just identity, so you just
get identity.
And so.
So, what about this first term, how do you
figure this out?
So remember what, what, what, you know, if
you, if you, if you try and multiply this
out, remember the first, the first row and
column of the Hadamard matrix is just,
every entry is one / square root of N.
Right?
And so if you, if you multiply this out,
what you get is, is, you, you, you will,
you will multiply one / square root ten
one / square root ten two for every entry
so you'll get a, get a matrix, which is
two / N. The every entry is, okay so every
entry is two / N minus identity.
Okay so, so if you were to write out this,
this, this transformation, it's two / N -
one, two / N - one And then, every other
entries two / N. Okay.
Okay.
So now, let's, let's try to understand why
this is a reflection about the mean.
So remember what, what, what, what we,
what we are saying, we are saying that the
Hadamard transform, sorry, the, the
reflection about the mean is, you do a
Hadamard transform, you do this, this,
this kind of phase inversion, where you
invert the phase of everything which is
not the all zero string and then you do a
Hadamard transform again.
Okay, and we, we are claiming that this
operator.
If you work it out, is to the diagonal.
Every entry on the diagonal is two / N -
one.
And every other entry, every off diagonal
entry is two / N. Okay.
So, so now, let's understand what this
does if our input superposition is
summation / x, alpha x, x.
Okay, so, so we have alpha zero, alpha N -
one.
Okay.
So what do we get?
But what's the, what's the, what's the
first entry going to be?
Well, you'll get, first you'll get a two /
N alpha not plus, so what's two / N alpha
not + two / N alpha one + alpha N - one
Where this is just two times the average
of these alphas, so it's two mean.
Right, so what's, what's the first entry
going to be?
Well you'll get two MU - alpha not.
What's the second entry?
We'll again get two MU, but now the -one
is in the second entry so you'll get two
MU - alpha one, two MU - alpha N - one.
So, so this gets mapped to summation over
all x of 2MU - alpha sub x, x.
This is exactly the inversion about the
mean operation that we were looking for.
Okay.
So now we are, we are all set to go.
We understand how to do a reflection about
the mean, and how to do a phase in
version.
Okay, so, so remember what, what, what
are, you know, what, what we wanted to do
in our, in our implementation of the of
Grover's algorithm was, was we first start
off with an equal super position.
So, remember this, these, these were the
steps.
So, so we first wish to start off with an
equals super position.
Over all the, over all numbers from zero
to N.
Or in other words above all the ended
strings so we do a Hadamard transform.
So, that's our initialization.
Okay, so this is initialize.
Then we want to do a phase reflection.
So if this was x star, we want to take
this and reflect it.
Okay.
So how do you do a, do a phase reflection?
Remember?
So this was, this is, what does the,
sorry.
The phase inversion.
Right?
We feed in a minus in the, in the answer
bit and we compute U sub f.
Right?
Our quantum circuit for computing f.
Then we want to do a inversion about the
mean.
And remember, our circuit for that was you
do a Hadamard transform, then you do this,
you have the circuit for checking whether,
whether the input is the all zero string,
and if, if not, then it outputs one.
But again, since our answer bit is a
minus, that puts the answer in the phase.
And then we do a Hadamard transform again
to switch back into the standard basis.
Okay.
So, so when we do the inversion about the
mean that increases, you know so, so when
we do the inversion about the mean the
amplitude of x star shoots up, and then we
want to repeat these, these two steps over
and over again.
So you want to do a phase inversion and
inversion about mean.
Okay, and so that's what that's what the
circuit looks like, so we initialize, we
do phase inversion, inversion about the
mean, then we do a phase inversion again,
we do an inversion about the mean again,
and so on and so on.
So the circuit sort of gets extended out
and there are, there are, there are order
square root of N such phases.
Right?
So, initialization followed by this, this
circuit, this part of the circuit.
Phase inversion plus inversion about the
mean gets repeated order square root N
times.
And then, you measure.
You measure this, this first, these first
N cubits.
And with probability at least a half, you
get to see the needle.
Okay.
But with probability of about a half, you
may not get the needle.
So what you do, you go, you, you, you now
take the outcome of your measurement and
you look inside that entry, if its marked
you are done, if not you repeat this whole
process again.
Okay.
One other observation about Grover's
algorithm which is that, you have to, you
have to get this number right.
If you let the, let Grover's algorithm run
for too long, then it might uncompute the
answer, so, you know, it, it keeps going
along, this keeps increasing in height,
the, the, amplitude of the needle keeps
increasing in height.
But eventually, and this is a good
exercise for you to work out, you should
check that the, that the amplitude of the
needle after it attains its maximum value,
it'll start reducing.
And the amplitudes of these other entries
will keep going up until the needle then
becomes extremely unlikely.
So, so, one of the important things in
Grover's algorithm is that you've got to,
you've got to set this parameter.
So, for example, if there were more than
one marked items, then Grover's algorithm
will run faster.
But you'll, you'll actually have to reduce
this number of iterations appropriately.
Okay.
Grover's algorithm also is fairly general,
you know.
Even though it only gives a quadratic
speeder so it doesn't give an exponential
speeder But, the trade off is, that it, it
solves an extremely general problem.
And this, you know, the ideas behind
Grover's algorithm have since been used in
a number of different settings to solve a,
you know, a, a range of different kinds of
problems.
And so if you look in the, in the notes,
you will find, find pointers to some of
the applications of Grover's algorithm.