1
00:00:00,000 --> 00:00:04,030
Okay.
So, in the last video we saw how to

2
00:00:04,030 --> 00:00:09,074
construct an algorithm for factoring
integers on a quantum computer.

3
00:00:09,074 --> 00:00:14,086
So, we saw the actual quantum circuit that
carries it out except that the quantum

4
00:00:14,086 --> 00:00:18,009
circuit involved a quantum Fourier
transform.

5
00:00:18,009 --> 00:00:24,013
And we haven't yet seen how to carry out
the quantum Fourier transform efficiently

6
00:00:24,013 --> 00:00:28,067
using the quantum circuit.
So in this video, I'll show you how that

7
00:00:28,067 --> 00:00:33,034
can be done, implemented efficiently.
So in order to do this, we have to

8
00:00:33,034 --> 00:00:39,000
understand some of the structure of the
Fourier transform, and this is a beautiful

9
00:00:39,000 --> 00:00:45,002
structure that actually goes into, into
the construction of a fast Fourier

10
00:00:45,002 --> 00:00:51,009
transform circuit in the classical case.
So let's, let's do a review of that first.

11
00:00:51,009 --> 00:00:57,094
So first, remember what the Fourier
transform matrix looks like, it, it looks

12
00:00:57,094 --> 00:01:04,036
like you know it, the, the entries, it's
an inbound matrix whose, whose entries are

13
00:01:04,036 --> 00:01:10,046
the, the primitive nth roots of unity.
So, so omega is a, is a, is a complex

14
00:01:10,046 --> 00:01:19,006
number such that omega^n = one.
And in fact, there are n such routes, so

15
00:01:19,006 --> 00:01:26,058
omega is primitive roots of unity so omega
is, is e to the two pi, pi/n.

16
00:01:26,058 --> 00:01:34,094
Which is, which is cosine of two pi by n
plus i sine of two pi by n, and here's

17
00:01:34,094 --> 00:01:40,048
this complex number.
And now, how does the, how does the okay.

18
00:01:40,048 --> 00:01:46,096
So in the classical case we don't actually
normalize our, our Fourier transform

19
00:01:46,096 --> 00:01:51,014
matrix so we don't multiply by one over
square root n.

20
00:01:51,014 --> 00:01:54,000
So it's not actually unitary.
Okay.

21
00:01:54,000 --> 00:02:00,078
And it takes as input and n dimensional
vector, complex vector and then outputs

22
00:02:00,078 --> 00:02:08,076
and, and dimensional complex vector.
So b naught b1.

23
00:02:08,076 --> 00:02:12,064
N - one.
So, okay, so that's how, that's how n

24
00:02:12,064 --> 00:02:17,000
dimensional Fourier transform, a discreet
way to transform.

25
00:02:17,000 --> 00:02:22,065
And now we want to understand how to, how
to implement this efficiently.

26
00:02:22,065 --> 00:02:28,044
So first let's see how to implement it
efficiently using a classical circuit.

27
00:02:28,044 --> 00:02:33,074
Okay, so remember usually if you multiply
a matrix and by a matrix by an n

28
00:02:33,074 --> 00:02:40,083
dimensional vector it requires n squared
operations, because for each entry of the

29
00:02:40,083 --> 00:02:47,006
output, we must take the corresponding
row, and multiply it by this column.

30
00:02:47,006 --> 00:02:52,000
And that takes n operations.
And so it's n per entry.

31
00:02:52,000 --> 00:02:56,007
So n squared total.
So in the fast Fourier transform, we do it

32
00:02:56,007 --> 00:03:02,005
much, much more efficiently.
In order, n log n operations and this

33
00:03:02,005 --> 00:03:06,008
relies on the structure of the Fourier
transform matrix.

34
00:03:06,008 --> 00:03:11,002
So what's the structure of the Fourier
transform matrix?

35
00:03:11,002 --> 00:03:16,055
So what we, you know remember what, what,
what we said the j-th, k-th entry of, of,

36
00:03:16,055 --> 00:03:22,053
of the Fourier transform matrix is
omega^jk Now what we're going to do is,

37
00:03:22,053 --> 00:03:27,098
we're going to sort the inputs.
In this clever manner, so we sort them

38
00:03:27,098 --> 00:03:31,090
into the even numbered ones and the odd
numbered ones.

39
00:03:31,090 --> 00:03:34,058
So, that corresponds to sorting the
columns.

40
00:03:34,058 --> 00:03:39,074
Where we put the even columns here, and
the odd columns there.

41
00:03:39,074 --> 00:03:48,093
So now, the, the, the entry in this, in
this, this particular entry is going to be

42
00:03:48,093 --> 00:03:54,048
omega to the 2j k.
And this entry is omega to the 2jk

43
00:03:54,048 --> 00:03:58,038
omega^j.
Now let's go ahead and solve the, you

44
00:03:58,038 --> 00:04:02,034
know, let's, let's divide the columns into
two.

45
00:04:02,034 --> 00:04:08,038
So the columns, the first half is, is a
columns with index less than n / two.

46
00:04:08,038 --> 00:04:13,026
And the second half is that is greater
than n / two.

47
00:04:13,027 --> 00:04:20,041
So, so we have row j versus j + n/2.
And now, notice that this entry, of

48
00:04:20,041 --> 00:04:26,001
course, was omega^2jk but this is also
omega^2jk, right?

49
00:04:26,001 --> 00:04:38,043
Because, because what we have is, this
entry is omega^j + n/2 2k which is

50
00:04:38,043 --> 00:04:45,053
omega^2jk + n k.
But remember omega^n <i>, omega^n = one so</i>

51
00:04:45,053 --> 00:04:51,009
omega^nk< /i> is just one.
So we can drop that, that's what this is.

52
00:04:51,009 --> 00:04:58,007
And similarly you can check that this
entry is omega^j omega^2jk.

53
00:04:58,007 --> 00:05:07,033
And this entry is minus omega^j omega^2jk.
Now here's one more important thing to

54
00:05:07,033 --> 00:05:11,033
realize.
So remember omega was a primitive and

55
00:05:11,033 --> 00:05:15,031
through affinity.
It was e^2 pi i / n.

56
00:05:15,031 --> 00:05:22,032
Now what's omega squared?
So omega squared is an n / two e-th root

57
00:05:22,032 --> 00:05:26,081
affinity.
In fact it's the primitive n over two e-th

58
00:05:26,081 --> 00:05:33,000
root affinity.
It's e^2 pi / n/2, right?

59
00:05:33,004 --> 00:05:44,077
So, so if you look at this matrix, it's a
n/2 by n/2 matrix who's jk-th entry is

60
00:05:44,077 --> 00:05:48,062
omega squared to the jk.
Okay.

61
00:05:48,062 --> 00:05:57,062
So this is really, this equals this large
matrix f sub n, then this matrix is f sub

62
00:05:57,062 --> 00:06:01,090
n/2.
So its this matrix, it's f sub n/2.

63
00:06:01,090 --> 00:06:07,030
How about this one?
Well, it's almost f sub n/2 except that

64
00:06:07,030 --> 00:06:11,061
the j-th row of this matrix is multiplied
by omega^j.

65
00:06:11,061 --> 00:06:17,050
So let's write it like this, even though
that's notation we've just invented.

66
00:06:17,050 --> 00:06:22,008
How about this matrix?
It's, it's also f sub n/2 except that the

67
00:06:22,008 --> 00:06:27,000
j-th row is now multiplied by minus
omega^j, okay?

68
00:06:27,000 --> 00:06:32,005
This should make it a little reminiscent
of the Hadamard matrix, where you have,

69
00:06:32,005 --> 00:06:35,003
the Hadamard matrix was.
H sub n/2.

70
00:06:35,003 --> 00:06:42,002
H sub n/2, h sub n/2, And - h sub n/2.
So now it's slightly more complicated, but

71
00:06:42,002 --> 00:06:46,001
it's still very reminiscent affair of the
Hadamard matrix.

72
00:06:46,001 --> 00:06:51,002
And so it's this structure that allows us
to get this efficient circuit for

73
00:06:51,002 --> 00:06:57,026
computing this, this transformation.
So, now let's see what, you know if we, if

74
00:06:57,026 --> 00:07:04,002
we sort our inputs in this way, evens
first, odds later, then how do we actually

75
00:07:04,002 --> 00:07:09,056
do this multiplication?
So well let's, let's, well what we can do

76
00:07:09,056 --> 00:07:14,003
is move this inside.
And so it's as though, what we would be

77
00:07:14,003 --> 00:07:20,005
doing is, we'd be taking the stop half and
multiplying it here, and the stop half and

78
00:07:20,005 --> 00:07:24,008
multiplying it here.
Both in half, multiplying this with it,

79
00:07:24,008 --> 00:07:31,074
and both in half multiplying that.
So let's, let's just write it out

80
00:07:31,074 --> 00:07:38,005
carefully.
So, so we, we basically have our.

81
00:07:39,008 --> 00:07:45,004
A Fourier transform sub n/2.
Sorry, we changed notations in the middle.

82
00:07:45,004 --> 00:07:51,048
By, by this n I mean just, f sub n/2, f
sub n/2 and, and now we are taking the

83
00:07:51,048 --> 00:07:54,003
evens, evens here.
Odds, odds here.

84
00:07:54,003 --> 00:08:00,002
And of course, we must multiply the j-th
through by omega^j-th and - omega^j-th.

85
00:08:00,002 --> 00:08:06,022
Okay, so now this should, this should tell
you how to construct a circuit for this

86
00:08:06,022 --> 00:08:11,077
problem and how to meet the circuit, it's
going to be a recursive circuit.

87
00:08:11,077 --> 00:08:17,008
So what we'll do is here, here, these are
input bits, so we sort them.

88
00:08:17,008 --> 00:08:22,001
We take the even ones on top, odd ones on
the bottom.

89
00:08:22,001 --> 00:08:27,003
And now these we, we, we put through a
Fourier transform matrix.

90
00:08:27,003 --> 00:08:31,000
You know, we do a Fourier transform of
these.

91
00:08:31,000 --> 00:08:37,005
It's an n/2 Fourier transform.
We do a Fourier transform of these.

92
00:08:37,005 --> 00:08:41,000
And then, what do we need to do about
them?

93
00:08:41,000 --> 00:08:47,001
So remember what we need to do is, on top
you need to take this clusters except in

94
00:08:47,001 --> 00:08:52,009
the j-th row we have to multiply this
answer by omega^j-th.

95
00:08:52,009 --> 00:08:58,009
In the bottom we, we need to take this
minus this except in the j^th row we

96
00:08:58,009 --> 00:09:04,009
multiply this founding out of it.
And so if you think about it, what that

97
00:09:04,009 --> 00:09:09,002
means is you take, put this through the
Fourier transform matrix.

98
00:09:09,002 --> 00:09:15,013
And now, on the j-th output, you take, you
take this, the j-th output from the

99
00:09:15,013 --> 00:09:18,093
bottom.
Multiply it by omega^j and you add these

100
00:09:18,093 --> 00:09:25,033
two values, right?
On the bottom what you do is, here let's,

101
00:09:25,033 --> 00:09:32,003
let's take this out.
What we do is you multiply the bottom

102
00:09:32,003 --> 00:09:39,017
value by omega^j.
You take this value and you subtract this

103
00:09:39,017 --> 00:09:43,009
from that.
And that's your, and that's your output.

104
00:09:43,009 --> 00:09:47,041
Okay.
So that's our circuit for, for the Fast

105
00:09:47,041 --> 00:09:52,005
Fourier Transform.
And now you can see that the size of the

106
00:09:52,005 --> 00:09:59,005
circuit for size n is two times the size
for n/2 and plus you get what n gates and

107
00:09:59,005 --> 00:10:03,009
this gives you that the total size is
order n log n.

108
00:10:03,009 --> 00:10:09,002
Right, this is the, this is the Fast
Fourier Transform circuit.

109
00:10:09,002 --> 00:10:15,008
It's the it's a size n log n instead of n
squared which is what you'd expect

110
00:10:15,008 --> 00:10:20,002
naively.
So now let's apply this in the quantum

111
00:10:20,002 --> 00:10:25,001
state.
Okay.

112
00:10:25,001 --> 00:10:32,001
So in the quantum setting let's, let's go
back and reinterpret everything.

113
00:10:32,001 --> 00:10:36,007
So now I'm going to switch from n to
capital M.

114
00:10:36,007 --> 00:10:43,004
Okay, why are we doing capital M?
So we'll think of okay, so we'll, we'll,

115
00:10:43,004 --> 00:10:52,010
we'll think of capital M as being two^m.
And the reason we do that is because our

116
00:10:52,010 --> 00:11:01,016
inputs, these are the amplitudes for our,
you know so, so we think of, we think of

117
00:11:01,016 --> 00:11:13,023
having little m cubits.
And so, their quantum state is described

118
00:11:13,023 --> 00:11:18,099
by two^m dimensional complex vector, so
that's the capital m dimensional complex

119
00:11:18,099 --> 00:11:23,077
vector so those amplitudes are often odd
to alpha capital m - one.

120
00:11:23,077 --> 00:11:29,012
And now what they want to do is we want
to, we want to perform a certain unitary

121
00:11:29,012 --> 00:11:32,061
transformation.
So to make this transformation unitary, we

122
00:11:32,061 --> 00:11:36,086
have the usual fourier transform matrix
that we did classically.

123
00:11:36,086 --> 00:11:41,003
Except now we must normalize it by one /
square root of M.

124
00:11:41,003 --> 00:11:45,048
So now this becomes unitary, it preserves
length.

125
00:11:45,048 --> 00:11:50,087
And, and so in order to carry out this
transformation, what we do is we take

126
00:11:50,087 --> 00:11:58,025
these little m cubits and we feed them
into Quantum Fourier Transformed sub M

127
00:11:58,025 --> 00:12:04,067
circuit, and what we get out is little m
cubits whose state now is described by

128
00:12:04,067 --> 00:12:08,037
this.
There it's beta naught to beta M - one

129
00:12:08,037 --> 00:12:14,047
which is exactly this fourier transform
applied to the input vector.

130
00:12:14,047 --> 00:12:21,015
Okay, so now we want to understand how to
carry out this transformation using an

131
00:12:21,015 --> 00:12:23,000
efficient circuit.
Okay.