So, just to remember what we, what we
already said is, in order to carry out
right, carry this out efficiently,
quantumly what we do is we put even inputs
sorry, plus three we put even inputs here,
the even numbers its here, odd numbers
inputs sorry odd number inputs here we do
the ffts and [inaudible] on top and the
bottom, what we do is.
The Jth of output on the top is, is this
Jth output from the, you know you take the
sum of the Jth output from the, from the,
from the top, FFT.
And you take the Jth output from the
bottom, NFT multiplied by omega to the J,
and you add the two up.
For the bottom, what you do is you, take
the, take the difference, but now.
Again you take the J type from the top,
the J from the bottom, but multiply by
omega to the J, and then you subtract.
Okay so we want to carry this out
quantumly, so how do we do this?
Okay, so first remember what happens in
the, in the quantum case well we only
instead of two to the little n inputs we
now only have little n inputs and we want
to carry out a quantum Fourier transform.
So.
So the first thing to observe is that, in
separating out these intputs into the even
numbered ones and the aught numbered ones,
all we need to do.
Is.
Separate them out according to the least
significant bits.
Right?
So we want to take everything with least
significant bit= to zero.
And we want to apply a quantum Fourier
transform to, to those inputs.
And take everything with least significant
bit, bit = to one, and apply a quantum
Fourier transform to those.
But remember, all we have to do,
quantumly, in order to make this happen
is.
We just take the least significant bit and
lead it out of this circle.
And we apply quantum Fourier transform to
these m-1 cubits.
And automatically.
This [inaudible] transform get, gets
applied, seperately in super position.
Do everything where the least significant
bit is zero, because these cannot
interfere with those where the least
significant bit is one.
To make sure you understand this fact.
So what we're doing is.
Just by putting the least significant bit
aside and applying upon the Fourier
transform to these m - one bits.
That applies the qfd sub two to the m -
one, which is qfd sub M/2 to these little
m - one q bits.
In superposition it applies it.
In parallel to the, to, to, to the zero,
to the even numbered ones and separately
to the odd numbered ones.
Okay, this is fantastic.
Okay, this is, you know, because, because,
this is the quantum magic coming in.
Now what's the, what's the next thing that
we want to do?
The next thing we want to do is, remember
we want to, we want to the, take the jet
output from here and the jet output from
there, add it.
To get the.
To, to get.
This answer.
And subtract to get that answer.
So how do we do this quantumly?
It turns out, in the simplest possible
way.
All we do is take the three significant
bit that we left out.
And we apply a harder map transform to it.
And that does the right thing.
It takes.
Remember what it does.
It, it takes, the zero output.
Yeah so, so the aptitude of zero out here
for, for this cubit is, is one over square
root of zero plus one and for one it's one
over square root of zero minus one.
And so what it ends up doing is exactly
adding and subtracting the appropriate
[inaudible].
And for the final thing what we want to do
is, we want to apply the appropriate
phrases right.
So, so if this.
If, if, if these wires.
If what this number is, is, is J, then we
want to.
And if this, if this cubit happens to be a
one, then we want to apply a phase of
omega to the J All right.
Okay.
So how do you apply, you know, how do you
do that?
Well, what you do is, you, you, you now
write J as the bits of J.
So remember there are little M minus one
bits, so let's call them J sub, J sub, M
minus one.
J sub M minus two.
Up to J sub one.
Okay, so maybe I should have started at,
at zero to say that that's the least
significant bit.
So n minus two minus three.
Okay, so these, these are the bits of, of
g so these are, each of these are zero or
one.
Okay?
And okay, so, so what is this?
Well this is exactly omega to the power.
This is, this is the m minus 2f bit, so
it's two to the, it, it's place value is
two to the m minus two, so what you want
is, you'd want to apply omega to the
[inaudible] of m minus two.
Times two to the M-2 right.
If, if, if this is one then you want to,
then you want to it to be omega two to the
omega m-2 otherwise you want it to be
omega-0.
Times, omega to the gsl m-1 and so m-3 to
do m-3 so on to omega [inaudible].
J not times two to the zero.
Okay.
So, so, but, but you want to.
But, but now, you see what this says is
you want to apply the conditional phase
gate.
Where if this is a one, if this happens to
be a one.
And if this happens to be a one.
Then you apply a phase of omega.
Okay, so this should be.
Think maybe I'll write it out here.
Should be omega to the two to the M minus
two.
And so on, all the way up to two here.
And the conditional case is just omega to
the two to the zero.
So, omega to the two to the zero is omega
squared.
No, sorry, omega to the one.
Sorry.
So omega to the two to the zero is just
omega to the one.
So you just apply conditional omega grate
and so on.
So you apply, you know, to each of these,
you apply the appropriate conditional
phase, two to the, omega to the two to the
M minus two, two to the M minus three, and
so on, up to just omega.
And then do you, you do a Hadamard.
So what does this tell us about the size
of the circuit?
So.
So what we have is the size of the circuit
you started of with, we have, we had n
wires coming in all together.
Is the size of the circuit with M minus
one Y is coming in.
Class, how many gates are these.
Well, this is, this is bigger of N.
Right.
And if you.
What's the, what does this [inaudible]
solve to?
It solves to S of N equal to big of M
squared.
Right, so, remember what we are carrying
out.
We are carrying out the key [inaudible] of
capital M where capital M was too to the
little m and so the size of a circuit is
little low of M2 which is little.
Little m2, which is low square
[inaudible].
I'd say it's exponentially better than our
classical circuit.