1
00:00:00,000 --> 00:00:10,004
Okay. So let's write out our general for a
transform matrix. So F sub N. It's, just

2
00:00:10,004 --> 00:00:20,006
some matrix one / square root N. Ones
across the first row. One Omega, omega

3
00:00:20,006 --> 00:00:30,056
squared, omega^N-1. One Omega^N-1. Omega^
N - one squared. Okay, so it's some matrix

4
00:00:30,056 --> 00:00:40,063
like this. And then of course, what you
can do is in general, you give it as input

5
00:00:40,063 --> 00:00:51,043
some N dimensional vector alpha naught to
alpha N-1 and you get as output a complex

6
00:00:51,043 --> 00:01:03,055
vector beta naught through beta N-1. Okay.
So, so the computing the Fourier transform

7
00:01:03,055 --> 00:01:12,099
is the, the fourier transform is a
transformation which takes as input an N

8
00:01:12,099 --> 00:01:21,006
dimensional vector alpha and outputs and N
dimensional vector, beta. Now, how

9
00:01:21,006 --> 00:01:31,098
difficult is this task? Well classically
the algorithm takes order N squared steps.

10
00:01:31,098 --> 00:01:39,025
And the reason is because to, to compute
some arbitrary entry, beta sub J, what

11
00:01:39,025 --> 00:01:47,006
you'd have to do is take the J-th column,
sorry the J-th row of this matrix and take

12
00:01:47,006 --> 00:01:52,086
the inner product with the, with this
column vector. And that, of course

13
00:01:52,086 --> 00:01:58,092
requires order N multiplications and
additions but now, you have to repeat this

14
00:01:58,092 --> 00:02:05,033
for every entry. And so, so that takes N
times all the N steps which is all the N

15
00:02:05,033 --> 00:02:11,089
squared steps. Now there was one of the,
one of the great breakthroughs in, in the

16
00:02:11,089 --> 00:02:25,009
field of algorithms was this was, was the,
was the fast fourier transform which was

17
00:02:25,009 --> 00:02:36,028
also called the FFT. Which was formalized
by Cooley and Tukey in the 60s. And what

18
00:02:36,028 --> 00:02:45,022
this does is it gives a, it gives an
algorithm which runs in order, N log N

19
00:02:45,022 --> 00:02:53,073
steps so nearly linear time. This speed up
of a quadratic factor was a very dramatic

20
00:02:54,001 --> 00:03:01,005
was a very important speed up. And this is
responsible, you know this is, are the

21
00:03:01,005 --> 00:03:10,005
basis of much of digital signal
processing. So, you know the, the, the use

22
00:03:10,005 --> 00:03:19,033
of digital technology in audio and video
processing is basically made possible by

23
00:03:19,033 --> 00:03:27,045
this algorithm. Now let's, let's turn
instead to the quantum case. So in the

24
00:03:27,045 --> 00:03:37,053
quantum case, of course this, this input,
this, this N dimensional input vector,

25
00:03:37,053 --> 00:03:46,059
it's natural to interpret it as the state
of a, of a system of log N quantum bits.

26
00:03:46,059 --> 00:03:56,090
So if you let litt le n, equal to log of
capital N so think of capital N as a power

27
00:03:56,090 --> 00:04:10,018
of two. Then, this is the state of little
n qubits which happen to be in the state

28
00:04:10,018 --> 00:04:20,016
sum over J of alpha J and J. And what the
quantum fourier transform does is it

29
00:04:20,016 --> 00:04:29,094
transforms this state into the new state,
sum / K of beta(K), okay. And now the, the

30
00:04:29,094 --> 00:04:38,078
remarkable thing about this is that the
circuit, the quantum circuit to carry this

31
00:04:38,078 --> 00:04:48,088
out works in a number of steps that only
scales or nominally in little n. So in the

32
00:04:48,088 --> 00:04:58,054
next video we will see that we can, we can
carry out this quantum fourier transform

33
00:04:58,054 --> 00:05:06,069
in big O of little n squared steps. Which
is just big O of log squared capital N

34
00:05:06,069 --> 00:05:13,058
steps. It turns out that if you work a
little harder you can get down to nearly

35
00:05:13,058 --> 00:05:21,004
linear in little n steps. Which means,
nearly linear n log n steps. But, but it

36
00:05:21,004 --> 00:05:28,040
doesn't matter so, the, the main thing is
you can go from, going from here to here

37
00:05:28,040 --> 00:05:36,031
is an exponential improvement. Okay. And
this is, you know this is where the power

38
00:05:36,031 --> 00:05:43,038
of quantum mechanics comes in, the power
of quantum computation comes in. Except

39
00:05:43,038 --> 00:05:50,054
that there's a bit of a rub here. The rub
is that when the quantum fourier transform

40
00:05:50,054 --> 00:05:56,068
does carry out this transform from the
alpha vector to the beta vector,

41
00:05:56,068 --> 00:06:03,082
exponentially faster than the classical
fourier transform can, can carry out this

42
00:06:03,082 --> 00:06:10,049
transformation. The problem is that the
quantum state of course, you know the,

43
00:06:10,049 --> 00:06:16,070
the, the amplitudes within the quantum
state are inaccessible to us. And so all

44
00:06:16,070 --> 00:06:29,021
we can do is we can perform a measurement.
And when we measure, we just see K with

45
00:06:29,021 --> 00:06:45,089
probability beta sub K magnitude squared.
So we just see one of these indices K,

46
00:06:45,089 --> 00:06:53,081
right? With, with some, with probability,
beta sub K magnitude squared so we don't

47
00:06:53,081 --> 00:07:00,036
get access to the beta, beta sub K but
just to this much simpler probability

48
00:07:00,036 --> 00:07:07,081
distribution, to a sample, from this
distribution. So, you know there was once

49
00:07:08,013 --> 00:07:16,083
the, the family of Intel Corporation
quoted more of his giving lecture. There

50
00:07:16,083 --> 00:07:26,038
he was talking about Moore's Law in this,
this phenomenon that the you know that the

51
00:07:26,038 --> 00:07:33,020
number of transistors that you c an pack
onto a chip has been doubling roughly

52
00:07:33,020 --> 00:07:39,037
every eighteen months going back several
decades now. You know, so this exponential

53
00:07:39,037 --> 00:07:45,083
increase in the number of transistors in
computing power, you know decrease in size

54
00:07:46,007 --> 00:07:53,000
decrease in cost. So he was talking about
how you know if, if this kind of if the

55
00:07:53,000 --> 00:08:00,025
automobile industry had been on, on the
same trajectory, then, you know already he

56
00:08:00,025 --> 00:08:06,081
was giving this, this speech over a decade
ago. He was, he was saying well, then if,

57
00:08:06,081 --> 00:08:13,063
if the automobile industry had, had been
on that same, same trajectory, then a

58
00:08:13,063 --> 00:08:20,034
Rolls Royce would give you hundreds of
thousands of miles to a gallon of, of

59
00:08:20,034 --> 00:08:27,092
petrol. It would travel at a tenth of the
speed of light. And it would cost, you

60
00:08:27,092 --> 00:08:35,054
know less than a nickel. And then some
wise guy in the audience piped up and

61
00:08:35,054 --> 00:08:41,020
said, and it would be smaller than a
matchbox. Well, so that's sort of what we

62
00:08:41,020 --> 00:08:46,031
have here. We have, in the quantum fourier
transform, we have something which is

63
00:08:46,031 --> 00:08:52,060
incredibly powerful. You know, it's very
fast. It's incredibly powerful. It's, you

64
00:08:52,060 --> 00:08:57,075
know there is this exponential speed up
but then on the other hand, by being so,

65
00:08:57,075 --> 00:09:03,069
so powerful, you know there is the price
to pay which is very little of it. So, you

66
00:09:03,069 --> 00:09:08,091
get, you don't get the entire output. You
just to get, get a sample of the output.

67
00:09:08,091 --> 00:09:14,069
And so the whole trick to using the
quantum fourier transform is, you know how

68
00:09:14,069 --> 00:09:20,018
do you use this effectively in the
algorithm. And that's what we will see in

69
00:09:20,018 --> 00:09:22,006
the, in the next lecture actually.