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.