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.