okay.
So, this week we are finally get ready to
get the shores of in factoring numbers but
before we can talk about that in today's
lecture we have to build up some
primitives for that will prove to be
useful and in factoring.
Okay.
So, this primitive is called period
finding And, in period finding, we are
giving some function f.
So F is some function that matches the
numbers from.
Zero to N minus one, so it's the domain of
size capital N, and it maps it to some,
some set S.
S could be the numbers from zero to N
minus one or it could be something else.
We don't care.
Now the, the property of F that we are,
that we are promised is that F is
periodic.
And.
Let's say, let's say the period is R.
Say, it's periodic.
With, period.
R, except that this period R is secret.
Okay.
So, what do I mean by saying that f is
periodic with period R.
What I mean is, that f(x) = f(x+R).
We off-course, this addition we are, we
are going to do modulo n so that, so that
x+r is always between zero and n-1,
meaning if we overflow then we just
subtract R and make sure that.
Now this number is always between zero,
and minus one.
Okay.
So this is true, for all X.
And we also want to make sure that.
This the only.
Sort of you know.
That, that other than this there's no.
There's no equality.
Meaning.
What we want to make sure is that.
We, we, we also want to say that if x is
not congruent to y mode r then.
F of x is not equal to f of y.
Okay, so what, what do we mean by this,
so, so what we have is, here's our, here's
what our graph looks like.
So here's, here's x, you know, let's say
we go from zero to n minus one.
Let's say f of x is, is just a number now
for us.
Right?
And let's say that you know, that r was,
was five.
So, so for example, so if r equal to five,
it might be that f of zero was, was this,
f of one was that, f of two was, was that,
f of three was that, f of four.
What's that?
Right?
So, notice that half of zero is not
equivalent to half of one is not
equivalent to half of two and so on.
All these are distinct.
That's this condition.
This condition says.
They are distinct until you get to'R'.
And now'R' is five, so'f' of'5', what
should it be?
It should be exactly'f' of zero.
So, so, it mean it will be naught.
What's'f' of'6'?'f' of'6' should be
exactly'f' of'1'.
So, it's naught.'f' of'7', it should be
exactly naught.
Right?
So that's the condition that they are
given.
And think of N-1 as being, you know.
N, N is large.
So, sorry, so.
You know, let's, let's have everything
move over a little bit.
So.
Lets see that that's'x' going all the way
out and that's in minus'1'.
So, so this is very far.
Note it.
So we are working with, period'n' large,
we are given a function which is, which is
periodic'n', okay, so the challenge we
have So.
The challenge is to find R.
Okay so this is very much like Symon's
problem, right.
There, there also we were given a function
with some hidden property to it and then
we wanted to find this, this secret right.
There, there was a secret string and here
we have a period R which we want to find
out.
Okay so again as in Symon's problem we
are, what are we given about F.
Well we are given a circuit.
That computes amp.
So they can get c sub f is a circuit,
which is given to us as a black box, and
we can input...
'X' you know outputs'f' of'x'.
And now the question is, how could you
ever use this box, this circuit to compute
out.
Well, what you could do is you could keep,
keep trying different'x'es until you get
to whether, where'f' of'x' is equal to'f'
of'I'.
But then in order to do this, the number
of times you have to try is, is some what,
you know its, its, it gets large if, if N
and R are large.
So if R is exponentially large and N is
exponentially large, then the number of,
number of trials that you have to do grows
exponentially.
So that's the hard part, right.
So, so the number of.
Trials is proportionate to some function
of R and N.
Right?
So you, you, you really have to try, you
know, some number of tries.
Which is, which, which grows quickly as r
grows.
Whereas, what we want is something that
grows much, much more slowly.
So what we'll see is that there's a
quantum algorithm For this problem, that
works in time, which grows binomially, in
[inaudible].
Okay.
So, so, so if you have a, you have a very
fast quantum algorithm that's
exponentially faster than the best
classical algorithm for this problem.
Okay so, so now, wha, what does this You
know, what, what does this, quantum
algorithm look like?
Well, remember, you know, as we always
did, what we, what we can do is given the
circuit C sub F, we can, we can convert it
into a quantum circuit U sub F, where we
can now give a superposition over X as
input.
And now we, we normally have X as input
but we also have.
Some other, work bits and answer bits, and
what we get as output.
Is.
X.
And F of X.
Right?
Better in superpositions.
Summa-, summation over alpha x, x, f of x.
Okay, so that's what, that's, that's the
box that we are given to play with.
And what we want to do is, we want to, we
want to very quickly figure out how to,
you know what this, what this R is.
Okay.
So, how does the algorithm for this work?
Well it turns out that it, it works very
similarly to [inaudible] algorithm.
So the, the algorithm for, for the quantum
algorithm.
For period finding.
The second faith looks very similar to the
second that your used to.
So what we do is we start with the circuit
like the Hadamard transform, except now
what we'll call it is the quantum Fournier
transform.
[inaudible].
And if [inaudible].
Zero into this into this quantum transform
you get it's output.
You feed that into this function f, the
periodic function.
[inaudible] zeros, you get some output.
Right?
You take this output.
So, so here you'ld have, F of X.
So this is some super position of all X.
Here you get some of the all X.
Of x, f(x).
So I am just giving you an overview of
what this quantum theory of finding is
going to look like.
We are going to come back and look at this
in detail.
But this is just to give a big picture of
where we are going with all of this.
So, so now you feed this so, so as before
what we do is we, we measure this output
and we throw it away.
And remember from what we said.
If you are going to measure and throw
away, you can also just throw away the
output.
So if you ignore this output, F of X,
that, that, that's the same thing as
though you measured it.
And now we [inaudible].
What's left.
And do another quantum [inaudible]
transform.
[inaudible].
And this answer is going to reveal to us
what the period R is So, if he, if he let
this answer be "L", Then the claim is.
So, so this our output.
So the, the, the claim that we make is
that L.
Divided by N is a very close approximation
to.
Some, multiple of one over r.
So it's a, it's a rational number of the
form, k over r.
Okay.
And because we know, we know L, we know N,
what we can do is, we can, you know, if.
So, so the claim is that if.
If m is much, much larger than r, then
there are, there's a certain procedure by
which you can actually use the fact that,
you know, you can use the fact that you're
given l and m.
You can efficiently.
Reconstruct r.
Okay so this is the primitive that we are
we are trying to you know, we are trying
go through we are trying to develop and
this is going to be a primitive that's
used in factory Okay, now, let me just say
one other thing.
So, it turns out that it's much, much
easier to develop this primitive in a
special case, and that's the case that
we'll be, we'll be discussing for most of
this lecture and most of the next lecture.
And then if there's a chance, I'll tell
you about the general case you know, which
is what I talked about so far.
So in the special case, what we'll assume.
Is that, now remember, you have your
function, F, which maps.
The domain of size, cardinality, and to
something, F.
F of X equal to F of X plus R, more N
[inaudible] x.
We'll also make one more assumption.
We'll also assume that R divides N, that N
is a multiple of R.
This is going to be useful for us because,
you know, in, when, when R divides N, then
this is, this is our situation.
So you have, this is X, this is F of X.
And you have, you know, F of X might.
You know, let's, let's say, let's say f of
x looks like this.
And that's r minus one, that's zero, and
then it looks the same, looks the same, so
on and you get to n minus one.
And it's the same.
Right so, so we don't cut off in the
middle, and it turns out that having this,
having the pattern actually complete makes
things a lot easier to analyze.
And that's what they're going to be
talking about for most of this and the
next lecture, and then if there's a
chance, I'll tell you about what happens
in the general case, and it's not that
much more difficult, but, but it's just
easier to talk like this.
Okay, so.
All right, so, so where does all this
leave us?
Now we've, now that leaves us, we've got
to understand what this quantum Fourier
transform is, which was the analog of the
Hademard transform that we talked about
last time.
Okay so let's, let's move on to that.