Alright, good morning. So in this lecture I would like to finish discussing Shor's

Algorithm. So first a quick reminder of what has been the topic of last lecture.

So mainly I discussed two things. The first was phase estimation. So where the

task is, there's a unitary transformation and one of its eigenvectors and then the

eigenvalues of such a unitary operator can be written as an exponential i times a real number,

which one can call a phase. And the task of phase estimation is of course to find this phase theta

nu. And so the basic idea is that one would prepare this superposition state

and the normalization is 1 over square root 2 to the power n and apply an inverse Fourier

transform onto that one, which would give a superposition of all possible y values and

I write the coefficients in this form. And the point is that these coefficients f theta nu

y are approximately 0 for all y except a value y that is a good approximation to

theta nu times 2 to the power n over 2 pi. And basically this precision increases with

the number of qubits n. Maybe to complete this, so the algorithm takes an input state of zeros

and the input state nu. So this is n qubits and this is a number of m qubits. And then

the usual thing, a Hadamard on each of these qubits and a specific controlled unitary that

we discussed in the last lecture. And then the inverse Fourier transform on that one

followed by a measurement. Okay and then I've started discussing Schor's algorithm as an

application of phase estimation. So what's the task in this one is to find for a large

integer number n a decomposition into prime factors. So all these pj are prime. And so

most of the, or one part of the algorithm uses some number theory properties to address

the task and there is one step which is the computationally most heavy one and that is

done quantum mechanically. So the quantum part of that algorithm is to find the smallest

R such that a to the power R modulo n is the same as one modulo n.

So modulo n meaning you divide by n and take the remainder. So this is called order or

also period finding. So with R being called the order or period of a function. And given

one found, one has found this R and then the greatest common divisor of a to the R over 2 plus

1 and n and the greatest common divisor of a to the R over 2 minus 1 and n. So these are both

non-trivial factors of n. Meaning these are integers, so the all of these are integers,

they both divide n and are not equal to n itself or not equal to 1. That is what non-trivial says.

Okay, so then rather than spending more time on this number theoretic things which are not so much

of interest for the topic here. I'd like to talk more about actually the quantum part of the algorithm.

Which is order finding. So order finding. Okay, so we consider n to be a large and positive integer.

And then I choose at random some a. So this is larger than 1 but smaller than n.

And the, so the task is then to find the period of a function f of x which is a to the power x

modulo n. So this is a periodic function, right? A is a number that is at least 2 and okay.

We do this for x larger than 0. So then, so without this modulo part this would just grow.

But because we always divide by n and take the rest it can never be larger than n. So it's

something that looks like that, right? It grows somehow then. There's something that periodically

repeats itself. So that if r is the period of f this means it's r is the smallest x

that f of x equals 1 or a to the r mod n equals 1 mod n.

Okay, so now we want to evaluate this function f using a quantum algorithm. Okay, so we should

implement f in quantum algorithm or quantum circuit. And the way this can be done is via

a controlled multiplication gate. So basically you want something that maps x and some b mod n

onto x e a to the power x mod n and specifically so we want to do b equals 1 and we do it via

implementing u to the power x with so u on x 1 mod, let me write it in general form, so b mod n

equals e a mod n.

So I already said we want to use phase estimation to do this. So this x here is an m,

qubit control state. So this means x can take values from 0 to m minus

1 where m is 2 to the power m and that's the precision of the phase estimation.

Yeah, I remember this that the phase estimation didn't necessarily find the exact phase but the