1
00:00:00,000 --> 00:00:05,004
Okay. So this week, we are going to talk
about Shor's Factoring Algorithm. But

2
00:00:05,004 --> 00:00:11,037
before we get there, we have to talk about
the Quantum Fourier Transform. Now, this

3
00:00:11,037 --> 00:00:17,000
is a generalization of the Hadamard
transform. In fact, the Hadamard transform

4
00:00:17,000 --> 00:00:22,007
is a special case of the Quantum Fourier
transform. It happens to be the Fourier

5
00:00:22,007 --> 00:00:29,005
transform when you restrict to the group
of integers marked two. So, in this

6
00:00:29,005 --> 00:00:37,058
lecture, we're going to talk about the
general transform mode n, which we'll call

7
00:00:37,058 --> 00:00:46,001
the Quantum Fourier transform. Okay. So,
before we do that, we have to, we have to

8
00:00:46,001 --> 00:00:52,071
talk about the nth root of unity or you
know, or the primitive nth root of which

9
00:00:52,071 --> 00:01:01,003
we'll denote by Omega. So, let's, let's
look at this figure. So, we have the nth

10
00:01:01,003 --> 00:01:08,037
root of unity satisfies this equation.
Omega to the n is one, so there are n

11
00:01:08,037 --> 00:01:17,019
roots of this equation. And the n roots of
this equation are complex numbers and they

12
00:01:17,019 --> 00:01:24,018
are of the form omega is e to the two pi i
over n. So for example, if, if n was five

13
00:01:24,018 --> 00:01:32,046
then this would be omega. It's, you, in
the complex plane where this is, this is

14
00:01:32,046 --> 00:01:42,028
the this is the real axis. That's the
imaginary axis. Well then, this angle is

15
00:01:42,028 --> 00:01:52,025
two pi divided by five, so this is the
fifth root of unity. And then, of course,

16
00:01:52,025 --> 00:02:04,007
omega to the j will just be e to the two
pi, j times i over n where i, of course,

17
00:02:04,007 --> 00:02:12,065
is the square root of minus one. Right?
It's the, it's the basic imaginary number.

18
00:02:12,065 --> 00:02:19,037
And now, you can, you can see that the,
that, that the fifth roots of unity are

19
00:02:19,037 --> 00:02:25,002
just omega, omega squared, omega cubed,
omega to the fourth, and one. Okay. So, so

20
00:02:25,002 --> 00:02:31,099
for example, well, omega is the fifth root
of unity because when you, you know, as

21
00:02:31,099 --> 00:02:38,079
you raise it to the fifth power, you just
keep multiplying this, this angle by two,

22
00:02:38,079 --> 00:02:45,061
three, four, and five. On the other hand,
omega squared is also the fifth root of

23
00:02:45,061 --> 00:02:51,055
unity because when we multiply this angle
by two, you get omega to the fourth, then

24
00:02:51,055 --> 00:02:57,004
six, then eight and then ten back to, back
to one. Okay. So, make sure you

25
00:02:57,004 --> 00:03:03,002
understand, you know, you remember your
nth roots of unity. And now, the Fourier

26
00:03:03,002 --> 00:03:09,027
transform or t he, the discrete Fourier
transform is, is this n by n matrix. Okay.

27
00:03:09,027 --> 00:03:15,003
So here, here's the way to think about it.
It's, it's normalized so, you know, we

28
00:03:15,003 --> 00:03:20,070
want it to be unitary matrix. So, you
normalize by one over square root n. And

29
00:03:20,070 --> 00:03:26,036
it's this n by n matrix where the first
row is all ones and the second row is one

30
00:03:26,036 --> 00:03:33,038
omega squared omega, omega squared, so on
up to omega to the n minus one. The, the j

31
00:03:33,038 --> 00:03:45,015
through is one omega to the j, omega to
the 2j, and so on. So in general, f sub n

32
00:03:45,015 --> 00:03:57,069
is an n by n matrix whose j kth entry is
omega to the j times k. Right? Where omega

33
00:03:57,069 --> 00:04:07,049
is a, is the primitive jth root of unity.
Omega is e to the two pi i over n. Okay.

34
00:04:07,049 --> 00:04:15,068
So that's, that's our Fourier transform.
It, it's a unitary transform. Okay. So, so

35
00:04:15,068 --> 00:04:22,052
now, let, let me just tell you how one
shows that this is a unitary transform.

36
00:04:22,052 --> 00:04:29,069
Well, what we want to do is we want to, to
show that it's unitary. We want to show

37
00:04:29,069 --> 00:04:37,029
that, of course, we want to show that the
norm of any row or column is one and we

38
00:04:37,029 --> 00:04:44,049
want to show that any two distinct columns
are orthogonal, alright? So, well the

39
00:04:44,049 --> 00:04:51,072
basic, you know, there are two facts that
we'd use to show this. What we are going

40
00:04:51,072 --> 00:05:01,043
to show is that, well, one over n times
one plus omega to the j plus omega to the

41
00:05:01,043 --> 00:05:12,040
2j plus omega to the n minus one times j.
If you sum this geometric series, what you

42
00:05:12,040 --> 00:05:21,094
get is, okay, so this, this, the summation
is equal to one if j equal to zero and

43
00:05:21,094 --> 00:05:30,046
zero if, if j is, j is anywhere between
one and n minus one. Okay? So if you, if

44
00:05:30,046 --> 00:05:38,028
you look at j between zero and n minus
one, then this sums to one if and only if

45
00:05:38,028 --> 00:05:43,097
j equal to zero and otherwise, it's zero.
Okay. How would you do this? Well, you can

46
00:05:43,097 --> 00:05:51,011
sum this as geometric series. So, just try
some English geometric series and this is

47
00:05:51,011 --> 00:05:59,035
what you will get. Okay? You, you just use
the formula for, for geometric series. But

48
00:05:59,035 --> 00:06:05,094
now, I claim the following two things are
true. If you take the inner product of a

49
00:06:05,094 --> 00:06:11,044
row with itself, a, a column with itself,
so when you, when you write up the inner

50
00:06:11,044 --> 00:06:16,064
product, you will get the sum of n terms
and they'll be of the form, one plus omega

51
00:06:16,064 --> 00:06:21,074
to the zero plus omega to the zero plus so
on to omega to the two times zero and so

52
00:06:21,074 --> 00:06:27,028
on. And so you'll get one all together. On
the other hand, if you take two distinct

53
00:06:27,028 --> 00:06:34,014
columns, then you'll get, the inner
product is going to be a geometric series

54
00:06:34,014 --> 00:06:40,081
where j is not equal to zero. And so,
it'll, you know, this, this inner product

55
00:06:40,081 --> 00:06:50,011
will turn out to be zero and, and so that
show us that f, so f sub n is unitary.

56
00:06:50,011 --> 00:07:02,047
Okay? So, the rows and columns are
orthonomal, are orthogonal to each other

57
00:07:02,047 --> 00:07:10,041
and they have unit, unit norm. Okay. So,
let's, let's go through an example. So

58
00:07:10,041 --> 00:07:20,086
let's set, let n equal to four. So omega,
which is the fourth, primitive fourth root

59
00:07:20,086 --> 00:07:32,057
of unity is, is just i, right? It's square
root of minus one. And so now, what's,

60
00:07:32,057 --> 00:07:39,052
what does f4 look like? Well, we have a
normalization factor, one over square root

61
00:07:39,052 --> 00:07:49,001
n, so that's a half. And then our matrix
look like one, one, one, one, one, i, and

62
00:07:49,001 --> 00:07:58,006
then i squared is minus one, i cubed is
minus i, one i squared. I squared is minus

63
00:07:58,006 --> 00:08:06,003
one, i to the fourth is one, i to the
sixth is minus one. One i cubed. I cubed

64
00:08:06,003 --> 00:08:18,007
is minus i, ito the sixth minus one, ito
the ninth is i. Okay. So that's, that's

65
00:08:18,007 --> 00:08:27,007
what f4 looks like. And now, let's see
what happens when, when we apply this

66
00:08:27,007 --> 00:08:32,005
unitary transformation to some
superposition. So, what, what does our

67
00:08:32,005 --> 00:08:38,015
superposition look like? So, remember we
are working math four so our superposition

68
00:08:38,015 --> 00:08:44,003
is alpha zero, zero plus alpha one, one
plus alpha two, two plus alpha three,

69
00:08:44,003 --> 00:08:51,091
three which we can write as alpha nought,
alpha one, alpha two, alpha three. Okay.

70
00:08:51,091 --> 00:09:00,012
So, what should we take this to be? Well,
so suppose our initial superposition was,

71
00:09:00,012 --> 00:09:08,025
was just that, right? So alpha one was
zero, was one. All the others were zero.

72
00:09:08,025 --> 00:09:18,041
So then our, then our new superposition
looks like one-half. And then we'll pick

73
00:09:18,041 --> 00:09:28,056
up the, this second column, right? So it's
one i minus one minus i which is just one

74
00:09:28,056 --> 00:09:38,055
over two, zero plus i over two, one minus
one over two, two minus i over two, three.

75
00:09:38,055 --> 00:09:48,016
So we get a superposition of all the, a
the four numbers math four with equal

76
00:09:48,016 --> 00:09:54,010
amplit, amplitu des except for phase,
right? And the phase sort of distinguishes

77
00:09:54,010 --> 00:10:01,053
where we are. Okay. So, so you can see
this, the Fourier transform the Fourier

78
00:10:01,053 --> 00:10:08,088
transform looks a little bit like the
Hadamard transform, except that the phases

79
00:10:08,088 --> 00:10:11,007
are more interesting now.