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 , omega^n = one so
omega^nk 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.