Okay.
So, in the last video we saw how to
construct an algorithm for factoring
integers on a quantum computer.
So, we saw the actual quantum circuit that
carries it out except that the quantum
circuit involved a quantum Fourier
transform.
And we haven't yet seen how to carry out
the quantum Fourier transform efficiently
using the quantum circuit.
So in this video, I'll show you how that
can be done, implemented efficiently.
So in order to do this, we have to
understand some of the structure of the
Fourier transform, and this is a beautiful
structure that actually goes into, into
the construction of a fast Fourier
transform circuit in the classical case.
So let's, let's do a review of that first.
So first, remember what the Fourier
transform matrix looks like, it, it looks
like you know it, the, the entries, it's
an inbound matrix whose, whose entries are
the, the primitive nth roots of unity.
So, so omega is a, is a, is a complex
number such that omega^n = one.
And in fact, there are n such routes, so
omega is primitive roots of unity so omega
is, is e to the two pi, pi/n.
Which is, which is cosine of two pi by n
plus i sine of two pi by n, and here's
this complex number.
And now, how does the, how does the okay.
So in the classical case we don't actually
normalize our, our Fourier transform
matrix so we don't multiply by one over
square root n.
So it's not actually unitary.
Okay.
And it takes as input and n dimensional
vector, complex vector and then outputs
and, and dimensional complex vector.
So b naught b1.
N - one.
So, okay, so that's how, that's how n
dimensional Fourier transform, a discreet
way to transform.
And now we want to understand how to, how
to implement this efficiently.
So first let's see how to implement it
efficiently using a classical circuit.
Okay, so remember usually if you multiply
a matrix and by a matrix by an n
dimensional vector it requires n squared
operations, because for each entry of the
output, we must take the corresponding
row, and multiply it by this column.
And that takes n operations.
And so it's n per entry.
So n squared total.
So in the fast Fourier transform, we do it
much, much more efficiently.
In order, n log n operations and this
relies on the structure of the Fourier
transform matrix.
So what's the structure of the Fourier
transform matrix?
So what we, you know remember what, what,
what we said the j-th, k-th entry of, of,
of the Fourier transform matrix is
omega^jk Now what we're going to do is,
we're going to sort the inputs.
In this clever manner, so we sort them
into the even numbered ones and the odd
numbered ones.
So, that corresponds to sorting the
columns.
Where we put the even columns here, and
the odd columns there.
So now, the, the, the entry in this, in
this, this particular entry is going to be
omega to the 2j k.
And this entry is omega to the 2jk
omega^j.
Now let's go ahead and solve the, you
know, let's, let's divide the columns into
two.
So the columns, the first half is, is a
columns with index less than n / two.
And the second half is that is greater
than n / two.
So, so we have row j versus j + n/2.
And now, notice that this entry, of
course, was omega^2jk but this is also
omega^2jk, right?
Because, because what we have is, this
entry is omega^j + n/2 2k which is
omega^2jk + n k.
But remember omega^n <i>, omega^n = one so</i>
omega^nk< /i> is just one.
So we can drop that, that's what this is.
And similarly you can check that this
entry is omega^j omega^2jk.
And this entry is minus omega^j omega^2jk.
Now here's one more important thing to
realize.
So remember omega was a primitive and
through affinity.
It was e^2 pi i / n.
Now what's omega squared?
So omega squared is an n / two e-th root
affinity.
In fact it's the primitive n over two e-th
root affinity.
It's e^2 pi / n/2, right?
So, so if you look at this matrix, it's a
n/2 by n/2 matrix who's jk-th entry is
omega squared to the jk.
Okay.
So this is really, this equals this large
matrix f sub n, then this matrix is f sub
n/2.
So its this matrix, it's f sub n/2.
How about this one?
Well, it's almost f sub n/2 except that
the j-th row of this matrix is multiplied
by omega^j.
So let's write it like this, even though
that's notation we've just invented.
How about this matrix?
It's, it's also f sub n/2 except that the
j-th row is now multiplied by minus
omega^j, okay?
This should make it a little reminiscent
of the Hadamard matrix, where you have,
the Hadamard matrix was.
H sub n/2.
H sub n/2, h sub n/2, And - h sub n/2.
So now it's slightly more complicated, but
it's still very reminiscent affair of the
Hadamard matrix.
And so it's this structure that allows us
to get this efficient circuit for
computing this, this transformation.
So, now let's see what, you know if we, if
we sort our inputs in this way, evens
first, odds later, then how do we actually
do this multiplication?
So well let's, let's, well what we can do
is move this inside.
And so it's as though, what we would be
doing is, we'd be taking the stop half and
multiplying it here, and the stop half and
multiplying it here.
Both in half, multiplying this with it,
and both in half multiplying that.
So let's, let's just write it out
carefully.
So, so we, we basically have our.
A Fourier transform sub n/2.
Sorry, we changed notations in the middle.
By, by this n I mean just, f sub n/2, f
sub n/2 and, and now we are taking the
evens, evens here.
Odds, odds here.
And of course, we must multiply the j-th
through by omega^j-th and - omega^j-th.
Okay, so now this should, this should tell
you how to construct a circuit for this
problem and how to meet the circuit, it's
going to be a recursive circuit.
So what we'll do is here, here, these are
input bits, so we sort them.
We take the even ones on top, odd ones on
the bottom.
And now these we, we, we put through a
Fourier transform matrix.
You know, we do a Fourier transform of
these.
It's an n/2 Fourier transform.
We do a Fourier transform of these.
And then, what do we need to do about
them?
So remember what we need to do is, on top
you need to take this clusters except in
the j-th row we have to multiply this
answer by omega^j-th.
In the bottom we, we need to take this
minus this except in the j^th row we
multiply this founding out of it.
And so if you think about it, what that
means is you take, put this through the
Fourier transform matrix.
And now, on the j-th output, you take, you
take this, the j-th output from the
bottom.
Multiply it by omega^j and you add these
two values, right?
On the bottom what you do is, here let's,
let's take this out.
What we do is you multiply the bottom
value by omega^j.
You take this value and you subtract this
from that.
And that's your, and that's your output.
Okay.
So that's our circuit for, for the Fast
Fourier Transform.
And now you can see that the size of the
circuit for size n is two times the size
for n/2 and plus you get what n gates and
this gives you that the total size is
order n log n.
Right, this is the, this is the Fast
Fourier Transform circuit.
It's the it's a size n log n instead of n
squared which is what you'd expect
naively.
So now let's apply this in the quantum
state.
Okay.
So in the quantum setting let's, let's go
back and reinterpret everything.
So now I'm going to switch from n to
capital M.
Okay, why are we doing capital M?
So we'll think of okay, so we'll, we'll,
we'll think of capital M as being two^m.
And the reason we do that is because our
inputs, these are the amplitudes for our,
you know so, so we think of, we think of
having little m cubits.
And so, their quantum state is described
by two^m dimensional complex vector, so
that's the capital m dimensional complex
vector so those amplitudes are often odd
to alpha capital m - one.
And now what they want to do is we want
to, we want to perform a certain unitary
transformation.
So to make this transformation unitary, we
have the usual fourier transform matrix
that we did classically.
Except now we must normalize it by one /
square root of M.
So now this becomes unitary, it preserves
length.
And, and so in order to carry out this
transformation, what we do is we take
these little m cubits and we feed them
into Quantum Fourier Transformed sub M
circuit, and what we get out is little m
cubits whose state now is described by
this.
There it's beta naught to beta M - one
which is exactly this fourier transform
applied to the input vector.
Okay, so now we want to understand how to
carry out this transformation using an
efficient circuit.
Okay.