Okay. So let's write out our general for a
transform matrix. So F sub N. It's, just
some matrix one / square root N. Ones
across the first row. One Omega, omega
squared, omega^N-1. One Omega^N-1. Omega^
N - one squared. Okay, so it's some matrix
like this. And then of course, what you
can do is in general, you give it as input
some N dimensional vector alpha naught to
alpha N-1 and you get as output a complex
vector beta naught through beta N-1. Okay.
So, so the computing the Fourier transform
is the, the fourier transform is a
transformation which takes as input an N
dimensional vector alpha and outputs and N
dimensional vector, beta. Now, how
difficult is this task? Well classically
the algorithm takes order N squared steps.
And the reason is because to, to compute
some arbitrary entry, beta sub J, what
you'd have to do is take the J-th column,
sorry the J-th row of this matrix and take
the inner product with the, with this
column vector. And that, of course
requires order N multiplications and
additions but now, you have to repeat this
for every entry. And so, so that takes N
times all the N steps which is all the N
squared steps. Now there was one of the,
one of the great breakthroughs in, in the
field of algorithms was this was, was the,
was the fast fourier transform which was
also called the FFT. Which was formalized
by Cooley and Tukey in the 60s. And what
this does is it gives a, it gives an
algorithm which runs in order, N log N
steps so nearly linear time. This speed up
of a quadratic factor was a very dramatic
was a very important speed up. And this is
responsible, you know this is, are the
basis of much of digital signal
processing. So, you know the, the, the use
of digital technology in audio and video
processing is basically made possible by
this algorithm. Now let's, let's turn
instead to the quantum case. So in the
quantum case, of course this, this input,
this, this N dimensional input vector,
it's natural to interpret it as the state
of a, of a system of log N quantum bits.
So if you let litt le n, equal to log of
capital N so think of capital N as a power
of two. Then, this is the state of little
n qubits which happen to be in the state
sum over J of alpha J and J. And what the
quantum fourier transform does is it
transforms this state into the new state,
sum / K of beta(K), okay. And now the, the
remarkable thing about this is that the
circuit, the quantum circuit to carry this
out works in a number of steps that only
scales or nominally in little n. So in the
next video we will see that we can, we can
carry out this quantum fourier transform
in big O of little n squared steps. Which
is just big O of log squared capital N
steps. It turns out that if you work a
little harder you can get down to nearly
linear in little n steps. Which means,
nearly linear n log n steps. But, but it
doesn't matter so, the, the main thing is
you can go from, going from here to here
is an exponential improvement. Okay. And
this is, you know this is where the power
of quantum mechanics comes in, the power
of quantum computation comes in. Except
that there's a bit of a rub here. The rub
is that when the quantum fourier transform
does carry out this transform from the
alpha vector to the beta vector,
exponentially faster than the classical
fourier transform can, can carry out this
transformation. The problem is that the
quantum state of course, you know the,
the, the amplitudes within the quantum
state are inaccessible to us. And so all
we can do is we can perform a measurement.
And when we measure, we just see K with
probability beta sub K magnitude squared.
So we just see one of these indices K,
right? With, with some, with probability,
beta sub K magnitude squared so we don't
get access to the beta, beta sub K but
just to this much simpler probability
distribution, to a sample, from this
distribution. So, you know there was once
the, the family of Intel Corporation
quoted more of his giving lecture. There
he was talking about Moore's Law in this,
this phenomenon that the you know that the
number of transistors that you c an pack
onto a chip has been doubling roughly
every eighteen months going back several
decades now. You know, so this exponential
increase in the number of transistors in
computing power, you know decrease in size
decrease in cost. So he was talking about
how you know if, if this kind of if the
automobile industry had been on, on the
same trajectory, then, you know already he
was giving this, this speech over a decade
ago. He was, he was saying well, then if,
if the automobile industry had, had been
on that same, same trajectory, then a
Rolls Royce would give you hundreds of
thousands of miles to a gallon of, of
petrol. It would travel at a tenth of the
speed of light. And it would cost, you
know less than a nickel. And then some
wise guy in the audience piped up and
said, and it would be smaller than a
matchbox. Well, so that's sort of what we
have here. We have, in the quantum fourier
transform, we have something which is
incredibly powerful. You know, it's very
fast. It's incredibly powerful. It's, you
know there is this exponential speed up
but then on the other hand, by being so,
so powerful, you know there is the price
to pay which is very little of it. So, you
get, you don't get the entire output. You
just to get, get a sample of the output.
And so the whole trick to using the
quantum fourier transform is, you know how
do you use this effectively in the
algorithm. And that's what we will see in
the, in the next lecture actually.