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.