Okay. So this week, we are going to talk about Shor's Factoring Algorithm. But
before we get there, we have to talk about the Quantum Fourier Transform. Now, this
is a generalization of the Hadamard transform. In fact, the Hadamard transform
is a special case of the Quantum Fourier transform. It happens to be the Fourier
transform when you restrict to the group of integers marked two. So, in this
lecture, we're going to talk about the general transform mode n, which we'll call
the Quantum Fourier transform. Okay. So, before we do that, we have to, we have to
talk about the nth root of unity or you know, or the primitive nth root of which
we'll denote by Omega. So, let's, let's look at this figure. So, we have the nth
root of unity satisfies this equation. Omega to the n is one, so there are n
roots of this equation. And the n roots of this equation are complex numbers and they
are of the form omega is e to the two pi i over n. So for example, if, if n was five
then this would be omega. It's, you, in the complex plane where this is, this is
the this is the real axis. That's the imaginary axis. Well then, this angle is
two pi divided by five, so this is the fifth root of unity. And then, of course,
omega to the j will just be e to the two pi, j times i over n where i, of course,
is the square root of minus one. Right? It's the, it's the basic imaginary number.
And now, you can, you can see that the, that, that the fifth roots of unity are
just omega, omega squared, omega cubed, omega to the fourth, and one. Okay. So, so
for example, well, omega is the fifth root of unity because when you, you know, as
you raise it to the fifth power, you just keep multiplying this, this angle by two,
three, four, and five. On the other hand, omega squared is also the fifth root of
unity because when we multiply this angle by two, you get omega to the fourth, then
six, then eight and then ten back to, back to one. Okay. So, make sure you
understand, you know, you remember your nth roots of unity. And now, the Fourier
transform or t he, the discrete Fourier transform is, is this n by n matrix. Okay.
So here, here's the way to think about it. It's, it's normalized so, you know, we
want it to be unitary matrix. So, you normalize by one over square root n. And
it's this n by n matrix where the first row is all ones and the second row is one
omega squared omega, omega squared, so on up to omega to the n minus one. The, the j
through is one omega to the j, omega to the 2j, and so on. So in general, f sub n
is an n by n matrix whose j kth entry is omega to the j times k. Right? Where omega
is a, is the primitive jth root of unity. Omega is e to the two pi i over n. Okay.
So that's, that's our Fourier transform. It, it's a unitary transform. Okay. So, so
now, let, let me just tell you how one shows that this is a unitary transform.
Well, what we want to do is we want to, to show that it's unitary. We want to show
that, of course, we want to show that the norm of any row or column is one and we
want to show that any two distinct columns are orthogonal, alright? So, well the
basic, you know, there are two facts that we'd use to show this. What we are going
to show is that, well, one over n times one plus omega to the j plus omega to the
2j plus omega to the n minus one times j. If you sum this geometric series, what you
get is, okay, so this, this, the summation is equal to one if j equal to zero and
zero if, if j is, j is anywhere between one and n minus one. Okay? So if you, if
you look at j between zero and n minus one, then this sums to one if and only if
j equal to zero and otherwise, it's zero. Okay. How would you do this? Well, you can
sum this as geometric series. So, just try some English geometric series and this is
what you will get. Okay? You, you just use the formula for, for geometric series. But
now, I claim the following two things are true. If you take the inner product of a
row with itself, a, a column with itself, so when you, when you write up the inner
product, you will get the sum of n terms and they'll be of the form, one plus omega
to the zero plus omega to the zero plus so on to omega to the two times zero and so
on. And so you'll get one all together. On the other hand, if you take two distinct
columns, then you'll get, the inner product is going to be a geometric series
where j is not equal to zero. And so, it'll, you know, this, this inner product
will turn out to be zero and, and so that show us that f, so f sub n is unitary.
Okay? So, the rows and columns are orthonomal, are orthogonal to each other
and they have unit, unit norm. Okay. So, let's, let's go through an example. So
let's set, let n equal to four. So omega, which is the fourth, primitive fourth root
of unity is, is just i, right? It's square root of minus one. And so now, what's,
what does f4 look like? Well, we have a normalization factor, one over square root
n, so that's a half. And then our matrix look like one, one, one, one, one, i, and
then i squared is minus one, i cubed is minus i, one i squared. I squared is minus
one, i to the fourth is one, i to the sixth is minus one. One i cubed. I cubed
is minus i, ito the sixth minus one, ito the ninth is i. Okay. So that's, that's
what f4 looks like. And now, let's see what happens when, when we apply this
unitary transformation to some superposition. So, what, what does our
superposition look like? So, remember we are working math four so our superposition
is alpha zero, zero plus alpha one, one plus alpha two, two plus alpha three,
three which we can write as alpha nought, alpha one, alpha two, alpha three. Okay.
So, what should we take this to be? Well, so suppose our initial superposition was,
was just that, right? So alpha one was zero, was one. All the others were zero.
So then our, then our new superposition looks like one-half. And then we'll pick
up the, this second column, right? So it's one i minus one minus i which is just one
over two, zero plus i over two, one minus one over two, two minus i over two, three.
So we get a superposition of all the, a the four numbers math four with equal
amplit, amplitu des except for phase, right? And the phase sort of distinguishes
where we are. Okay. So, so you can see this, the Fourier transform the Fourier
transform looks a little bit like the Hadamard transform, except that the phases
are more interesting now.