Okay.
So now, let's, let's prove this, this
period, this periodic property of the
Fourier Transform in this, in this in a
special case.
And the special case that we'll, we'll
look at involves, let's assume that, that
the period r divides N.
And let's assume that our initial
superposition is, is non-zero only on
multiples of r.
So, so, let's say that our initial super
position was of the form sum of j of times
r.
So, these are the only values which have
non-zero amplitude.
And in fact, how many of them are there
going to be?
Well, you know, since r goes into M, N
over r times.
So, we'll, we'll have j = zero to N / r -
one, alright?
So, there will be exactly N such, N / r
such values, and each should have, you
know, since we want them to have equal
amplitudes, each will have amplitude
square root r / N.
So, this is our initial superposition.
It's, it's non-zero only for these
multiples of r.
And it has, it has amplitude exactly this
much at each one of them.
So now, we want to understand what happens
when we apply the Fourier Transform to
this.
And the claim is, we get a similar
superposition with period N / r.
So, so, in other words, we get K = zero to
something.
And, we'll, we'll get non-zero amplitudes
only at multiples of N / r.
So, it's K N / r.
So, N / r, 2N / r and so on to r - one
times N / r.
So, so, there will be exactly r such
non-zero values.
And so, each should have amplitude, one /
square root of r.
And K goes from zero to what?
Well, you know, there are r of them so
you'll go to r - one.
Okay.
So, so, how do we prove this?
Well, to prove this, we have to remember
what, what our Fourier Transform is.
So, remember what our Fourier transform,
what F sub N looks like is, well, it's one
/ square root N, times this N by N matrix.
What's the N by N matrix?
Well, if you look at the x, yth entry,
it's Omega to the xy.
Okay.
So, what, what is this telling us?
Well, it's telling us, if you want to know
how much this particular entry gets mapped
to that one, well, what, how much does
this, this entry get mapped, you know,
what, what does it contribute?
So, we, we, okay, what are we trying to
do?
We are trying to figure out what is, you
know, if this was, if, if the amplitude of
this entry was, was beta.
What's beta, right?
Well, okay, so, so, so the, the amplitude
here will get, get some, some contribution
from every non-zero term here.
What, what contribution does it get?
Well, it gets Omega to the power of j r,
which is in this case, y times omega to
the x, which is times K times N / r, okay?
So, that's, that's, this omega to the,
this, times the amplitude you started
with, which is square root r / N and then
times one / square root N.
And now, we must sum this for all j going
from zero to N / r - one.
So, that should be the amplitude of, of,
this, this, particular entry.
Okay.
So, so, what is this value?
Well, you get this is equal to square root
of r / N summation j = zero to N / r - one
of omega to the power of these rs will
cancel and it's j times K times N.
But remember, Omega to the N is one.
So, this is just one, right?
So.
You, so, you'd get square root r / N times
one added N / r times, so times N / r,
which is exactly one / square root r.
Okay.
So, so, what they've prove is that for
each multiple of N / r, the amplitude is
exactly one / square root r.
Now, there are exactly r of these values,
right?
And so, so, the, the amplitude is exactly
one / square root r for, for these r
values.
What's the amplitude at, at these other
points?
Well, remember, this is a unit vector.
And we already have a unit vector.
The, the, the, this, this output vector
has to be a unit vector.
We've already accounted for, for a unit
norm in its amplitudes at zero N / r, 2N /
r, and so on.
And so, the amplitude at every other point
has got to be zero.
Okay.
That's one way of arguing it.
The other way you can argue it is if you,
if you, instead of taking, looking at a
point of this kind, a multiple of N / r.
You just look at, look at the amplitude
of, of some other point which is not a
multiple of N / r.
And then, what you'll see here is that
this Omega to, to these, powers, these
will just precess around and they'll
cancel out in the, in the [unknown].
Okay, so in either case, what we've shown
is, that if you start with this periodic
superposition with period r, you end up
with this periodic superposition with
period N / r.
Okay.
So now, we are ready to look at our
primitive, which is period finding.
This is what we are going to use in Shor's
algorithm for factoring.
So, so, this is sort of the last thing we
are going to do in this, in this
particular video.
So, lets try to understand how, how period
finding works.
So now, suppose we are given some function
f such that this set zero through N - one
is mapped to some set S, we don't care
what S is.
But we are told that f is periodic with
period, period r.
So, sum period r which divides N.
Okay, meaning f(x) = f(x) + r that's in
mod N.
So, we're working modular N, okay?
So, we're wrapping around.
Moreover, so, so we are told that f is
periodic but within each fundamental
period, we are, we are told it's one to
one.
So, f(0) is different from f(1) is
different from f(2), is different from f
of r - one.
But then, once you get, get past r - one,
you keep repeating.
So, if you were to plot out, if this was
x, that was f(x) then maybe, this is what
f looks like, it's, it's one to one up
through, let's say, that's r - one, that's
zero.
And then, starting from r, you have
exactly, the same, same shape.
And then, starting from 2r, you have
exactly the same shape and size.
Okay.
So, that's our function f.
And the way this function is specified to
you is by a black box or some program to
compute f.
So, you're given a black box or a circuit
C sub f.
And what you want to do is you want to
determine the period r, okay?
So now, now, in general, N is going to be
very large and so is r.
And so, what's, what's not a very
effective strategy is to just take your
circuit for computing f, and feed in
random values for x, hoping to see a
collision.
So, this is not going to be a very quick
way of, of, of computing r because you'd
have to do work proportional to r, or
square root of r, something like that.