Okay. So now, let's see how, how we can do
this, solve this period finding problem
very efficiently if we had if we had a
quantum circuit for doing it. So remember
our problem, we are, we are given a
function f. Sorry okay. So, we are, we are
changing notation again. We are, we are
going from n to m. But that's okay. That's
a small, small change. So, remember, we
have a function f which maps zero through
m - one to sum set s. And F is periodic
with period r. So, r divides m and with,
with the property that f(x) = f(x) + r,
for every x. And now, what we're trying to
do is figure out what r is. So, here's
what our circuit for, for period finding
looks like. And it's based on these
properties of the Quantum Fourier
Transform that we've already studied. So,
what do we do? We start in the all, in the
zero state and we apply the Quantum
Fourier Transform modem. So, remember,
what, what the Quantum Fourier Transform
model will do to the, to the zero state.
Zero state meaning, well, so, so let's
see, the QFTs of M, is what? One / square
root M. And then, you have this matrix,
which is, which is ones along the first
row, ones along the first column. Omega,
etc., Omega to n - one, and so on. But
now, what's the zero state? It's, it's
this factor, right? It's, it has amplitude
one for the, for when, when, when our,
when our quantum system is in the state
zero and zero, otherwise. And so, so the
result of this is, is the is this state,
right. So, it's, it's the first column,
which is, which is all ones, meaning we
end up in a, out here in a superposition,
sum over all x with, with amplitude one /
square root N, x = zero to n - one. Okay.
So, so now, when we apply our circuit for
computing f to this superposition, of
course, what we get is sum of all x = zero
to m - one where this register is in the
state x, and this answer register is in
the state, f (x). So, these two get
entangled with each other now. But now, if
we, if we, out here do a measurement, and
measure what f(x) is, we'll get some
outcome. And, let's say, that t he outcome
is f(p) for sum value k. So now, we can
ask, what's, what's the new state of this,
this, this register here? What are, what
are, what's the state of these wires?
Well, the answer is it's going to be,
remember what the rule of, rule of partial
measurement is? If you, if you measure
these wires, and the outcome is something,
you, you, you sort of cross out all of
those parts of the superposition that are
not consistent with this outcome. So, you
cross out all those xs such that f(x) is
not equal to f(k). And then you
re-normalize to get a unit vector,
meaning, what we will end up with is a
superposition over all those xs such that
f(x) = f(k). But what are all those xs?
Well, they are f of, they are k, k + r, k
+ 2r, and so on, because this is a
periodic function with period r. So, at
this point, this superposition is going to
be equal to k +, k + r + k + 2r + so on +
k + n - r. How many terms are there? Well,
there are m / r of them, so you must
normalize by square root r / n, alright?
Okay, so. This slide's getting a little
bit grungy. So, let's, let's remember
this. Let's carry this over, and let's,
let's try to clean everything up. So, at
this point, we're in the situation where
we made a measurement there, and, and this
superposition is, happens to be, right?
So, this is k + k + r, k + 2r, and k + 3r,
and so on. Okay. So now, what happens when
we perform a Fourier Transform on this?
What happens when we do a Quantum Fourier
Transform sub m of this? Well, remember,
what, what are we planning to do? Well, we
are planning to do a Quantum Fourier
Transform, and then do a measurement.
Okay, so, the two rules that we had about
Quantum Fourier Transforms followed by,
you know, so the first was, if you were to
cyclically shift the superposition, then
the only thing it'll, that, that, that
will change in a Quantum Fourier Transform
is the phases. So, if you are planning to
do a measurement right afterwards anyway,
those phases are not going to make any
difference to us. So, we may a s well get
rid of this c yclic shift, because it's
not going to make any difference to the
Fourier sampling that we are going to do.
Okay, but now, what are we left with? We
are left with this periodic superposition,
which is what we were looking at before.
This is, this, this is our periodic
superposition with period r. So, what's
the Quantum Fourier Transform? It's just a
superposition l m / r, right? Where l
ranges from zero to r -one, we have
normalization one / square root r. Okay.
So, so, what do we end up getting? We end
up, when we do a measurement we see a
random multiple of m / r. Okay. So, so,
here's the upshot. What we did was we've
managed to come up with a, with a quantum
circuit which is efficient because our
Quantum Fourier Transformer is efficient,
our circuit for computing f is efficient.
And every time we run the circuit, we make
a measurement here, and we see a random
multiple of m / r. So, we see some, some s
m / r, where s is a random number is s is
a random number between zero and r - one,
okay? So now, what are we going to do? How
do we figure out m / r from, from this
random multiple of m / r. Well, we just
repeat this a few times. So, you repeat
and you compute the, the greatest common
divisor of all the samples that you get.
And the claim is that pretty soon, you
will, you know, the GCD of, of these
numbers will be equal to m / r. Because,
you know, are, these are random numbers
between zero and r - one. If you pick
random numbers several times and you take
the GCD, you are, you are very likely to
get one. Because you know, this is an easy
argument, because what's the chances that,
that, that all these s are divisible by
two? Well, it's, you know, it's the, the,
the, the chance that, that the first of
these S's is even is, is a, a half. The
chance that the second time it's even is a
half, and so on. So, if you, if you repeat
a few times the chance that you'll get two
as a factor of the GCD is going to be
very, very small, and now. You can repeat
it with every possible factor and, y ou
know, the chance of havin g that common
factor falls off exponentially, in the
number of factor in the number of
repetitions. And so, you know, this shows
you that the G, the, the, that if you take
these samples. And you take the GCD, it's
very likely that, that the GCD is going to
be m / r. But once you know m / r, of
course, you can computer r because you
know m. Okay, so that's period finding.
And that's basic primitive that you are
going to use next time to, to factor.
Okay.