Okay.
So, in this video we're gonna study some
properties of quantum Fourier transform
that make them useful in, in algorithms.
So let's, let's re, remember what quantum
Fourier transform is.
Its it's, it's an n by matrix, it's, it's
an n by unitary matrix which is which is
expressed in terms of the n through
infinity omega.
So, here omega is e to the two pi I over
n.
It's a primitive Nth root of unity.
And, and basically the, the, the matrix
has its, has its, JKTH, entry, omega to
the JK.
Let's see, so there are, there are two,
very interesting properties of, of this
quantum Fourier transform.
So, so let's say that this was, this was a
quantum Fourier transform matrix, one
omega, omega to the N minus one, one omega
to the N minus one.
Okay.
And, let's say we apply the two.
To this state and we got as output.
Right?
So we are assuming, so, so what we are
saying is that f sub n applied to the
state, summation over j alpha j, j.
Is equal to summation of a k, b to the sub
k, okay.
Alright?
That's the, that's the result of applying
this, this transform to this.
Okay, so now let's, let's consider what
happens if we, if we applies the same
transformation, the fourier, quantum
fourier transform so we, we apply this the
same matrix.
Okay?
So we apply it to a shifted version of
them.
So, so what we're going to do is we're
going to shift.
Our, our input superposition.
And so we sh-, we shifted cyclically, so
let's say we shifted by one position but
then, you know, as you'll see the same
principle will apply no matter how much
we, if we, if we shift by many positions.
So, so let's shift everything down by one
position.
So you have Alpha naught moves down to the
second position, alpha one, alpha n - two,
and then alpha n - one get knocked, gets
knocked out and move to the top position.
And now we want to understand, what's the
Quantum Fourier Transform?
Well, the answer is particularly nice.
So what it says is basically everything
stays unchanged.
Okay, so all these amplitudes, on this
side, basically remain the same, except
they get multiplied by faze.
And, and what phase is it?
It's some, it's some, some meaning,
meaning a complex number of unit
magnitude.
And in fact, it's, it's actually going to
be a power of omega.
So what power of omega do we have?
Well, it depends upon which row we have.
So, so this first one gets multiplied by
one The second one by omega, the third one
by omega^2, and so on, up to omega to the
N-1.
Okay, now, here's the important thing.
The important thing is that each of these,
it's not what the actual value is.
It's the fact that these are all unit
magnitude.
So now.
If we were to do a measurement at this
point.
What we'd see.
Is, is k with probability beta sub k
magnitude^2.
Exactly the same as if you did the
measurement up here.
You see k with probability beta sub k
magnitude^2.
So.
The moral of all this is, that if you
start with some superposition, and if you
are going to do a Fourier transform,
quantum Fourier transform and then
measure, so if you are going to do.
Quantum.
For a sampling.
Then.
Doing a cyclic shift, of the, of the input
super position doesn't change the output
distribution.
Okay, so, now to some of you, this you
know this, this property of quantum
Fourier transforms might look very
familiar, and the reason it looks familiar
is probably because it is.
So this, this property that when you shift
the, shift the input superposition, the
output superposition just gets multiplied
point-wise by phase.
This is the same thing as this is the
convolution.
Multiplication.
Property of the foray transform.
Okay so, well see if you can, you know, if
you, if you do know about the con-,
convolution multiplication property, see
if you can figure out why this is the
case.
So what are you convolving and what is
point-wise multiplication?
Right?
So just to give you a hint, this is where
you have point-wise multiplication.
You are multiplying point-wise by this.
You know, by these phases, right, so
really okay, so this, this what you are
doing, you are multiplying the fourier
transform of something which is the b term
of beta n minus one, point wise by one
omega, omega squared omega to the n minus
one, which is the fourier transform of
something else.
Okay and.
So what you're getting on the left inside,
you're getting, you're, you're starting
with this particular vector, and then
you're convolving it with something to get
the shifted vector.
So, that's why you're getting a
convolution on the left, and point-wise
multiplication on the, on the right.
See if you can figure it, if you, if you
happen to know about the convolution
multiplication property.
Okay.
So now, let's, let's prove a second very
important property of the Quantum Fourier
Transform.
The, this property says that if you start
off with a periodic function, then the
quantum theory transform is going to map
it to a periodic function.
So let me, let me say this in a, you know,
a little more carefully in terms of how
you've been thinking about it.
So, let's say that our input superposition
was.
Summation of a sub j and j.
So j, of course, goes from zero to a -one.
Alright?
So that's our input superposition.
And now we are applying the Fourier
transform to this.
And we get a output superposition,
summation k equal to zero to a -one of b
to a sub k.
Okay?
Okay, so wh-, what's periodic here?
So, so remember wh-, what we are doing
here is we are, we are, we are plotting J
along this axis and alpha sub J along that
axis.
So what we are saying is that these
amplitudes are periodic, meaning that.
Alpha sub j plus r equal to alpha sub j.
Right?
That's what it means for it to be periodic
with period r.
So, when you, when you add r to the index,
you get the, get back to the same
amplitude.
So we are claiming.
That this implies.
That beta must also be periodic.
Okay, so what's beta?
Well, you know, so, so here we are, we
are, we are plotting k along the x axis,
and beta sub k along this y axis.
Right?
And what we are claiming is, now, beta
must be periodic with period M over R.
So, beta sub k + m over r must be = to
beta sub k.
Okay, so we've already seen an, an extreme
case of this.
You know.
So, so, let's, let's write it out over
here.
So, suppose we apply f sub n to the
uniform superposition.
To one over square root n, sum of
everything.
J= to zero to n-1 of j.
Right?
So.
So it's, you know this is a super position
of everything from zero to N - one.
And what's the Fourier transform of this?
Well it's, it's, It's just, it's just
zero.
Right?
And so, well, this, this superposition has
period r = one.
So here, we have r equal to one.
And so m over r is equal to m.
So this is a, this is a superposition with
period exactly m, in the sense that, in
the sense that this is a superposition
which starts, near with which is a delta
function at zero.
And then there's nothing all the way up to
M minus one, you know, which is everything
we have.
And then of course if we, if we made it
[inaudible], you know we'd get another
delta function at M and then nothing all
the way up to 2M minus one and so.
But, but of course we are, we are only
limiting ourselves to zero through M minus
one, so the period is exactly M, which is,
which is, which is like saying we ended up
with this delta function.
Okay.
Okay.
So that's this, you know that's our second
property of the quantum foray transform
that.
It treats periodic functions extremely
nicely.
Okay, so let's start by proving a very
special case of this of this property of
the Fourier transform.
So would it in this special case we, you
know, the superposition we start with has
non-zero amplitudes only at multiples of
R.
And it has equal amplitudes at these
points.
So, so our initial superposition is, is
zero plus R plus 2R.
Plus one plus n minus r.
We have to remember that we are, we are
also working in the, in the special case
where R divides N, and so if you look at
the number of terms in this superposition
it's there's exactly N over R of them.
And so each of, to normalize each you'd
have amplitude R over N.
And then what, what they're claiming is
that under the Fourier transform you get N
equals superposition over zero, N over R,
2N over R, et cetera.
And again, the number of terms here is R.
So, to normalize, we put in one over
square root R.
So I think that this is, you know.
So, if you want to understand this
intuitively.
Well, let's, let's start by looking at the
very special case where you, where you
start with.
Just.
A super position which is which is
concentrated 110.
So that would correspond to a period of N.
Right?
And now, when you take the Fourier
transform.
What this should tell us, you get a super
position.
So, Zero + N over N so, one + two + one or
two, N - one or normalized by one over
square root n.
Okay?
And, the converse also holds that if we
start from the c equal superposition
before you transform gives us back just
the zero state So, let's see that this is
actually true.
So, remember what the Fourier transform
matrix is?
It's an N by N matrix, one over square
root N, the first row is all 1s, the first
column is all 1s, and here you have omega,
omega to the N minus one, omega squared,
omega to the N minus one.
Okay, so that's the Fourier transform
matrix.
And now, what's this state, just the zero
state?
Well that's one here.
Its, its amplitude is one.
Everything else has amplitude zero.
So this just picks out the first column.
Which is exactly that state, yes.
One more square exam.
One, one, one.
One, right so one in all the entries.
And so, so that's, that's exactly equal to
that state.
And similarly, if we start with all one
state.
Then, as you can see, you'd get the inner
product of the first row with that, and
that that'll give you a one in the, in the
top position and everything else will give
us 0s.
And so if you start with this state,
you'll, you'll get that.
So, now remember, you know, so intuitively
what the Fourier transform does is if you
start with this delta function.
They are concentrated at zero.
In the Fourier domain you spread out
completely.
So your, you, you have a superposition
over everything.
If you start off with N equals
superposition over everything, you get
completely focused result on the Fourier
domain so you get, just get a, get a
completely concentrated superposition on
the zero state.
Now what this, what this property is
telling us is that if you start, you know,
generalize this completely so if you start
with period of r then in the Fourier
domain, we get period n over r.
So this, so the smaller the period on this
side the larger the period in the
foredomain and vice-versa.
Okay so this is what we want to prove.