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.