so we are continuing on shors algorithm so here will do the shors algorithm once more
in the actual quantum stepwise and will explain to you how this can be done stepwise so the
first step which is very important is the preparation of the data as i mentioned earlier
please remember that although the quantum aspect of the process is being utilize in
only one of the many steps of the shors algorithm the moment you are dealing with quantum data
we have no choice but to essentially process the whole thing in a slightly different manner
so although the quantum principle is only going be used may be not all the time it will
still be important to understand how this is system so in the first step which is preparing
of the data will be loading the input register with an equally weighted superposition of
all integers from zero to q equal to q minus one which is basically zero to two fifty five
because we said we are dealing with two fifty six sets so the the output register will be
loaded with all zeros because we dont know anything about the output yet so the total
state of the system at this point will be the output register all zeros and the input
register containing every possible value from zero to two fifty five the comma that i have
just put here denotes the registers are entangled so thats actually very important so this pat
particular part where we are preparing the data has the quantum part incorporated in
it in recognition of the fact that we are considering this to be in the entangled condition
so thats the part which is important in this quantum principle
the next part which is essentially modular arithmetic on this entire quantum system is
to apply the transformation x to the power a mod of n to each member of the input register
sorting the results of each computation in the output register so these output register
which was essentially unpopular or where all equally propagated with zero are now going
to have the values which are going to be the numbers which have based on the values that
we do and as you can see here these are now going to have repeats
so this is the part which is one kind and this is the part if the other kind and this
kind of shows up the principle that we have been talking about periodicity earlier ok
so once we have got in to this step ok which were all working with entangle qubits we
need to have the case were we can do as superposition collapse so that we can understand the result
because until that point of time we make the collapse we do not have the result and so
we make a we take a measurement on the output register and this will collapse the superposition
into represent just one of the results of the transformation and if you call this value
c then this is exactly how it will look like or output register will collapse to represent
one of the following one four seven or thirteen right because if you look at it these are
the distinct number we are getting again the next time all its just repeating so at any
point of time if you look at the solution you will only get these four solutions thats
it so for an example say let us say that we have
collapsed to one and see what happens this is a result of that so now since the two registers
are entangled measuring the output register will have the effect of partially collapsing
the input register into an equal superposition of each state between zero and q minus one
that yielded the value of the collapsed output register this is the quantum aspect of
this entire problem ok the very fact that my input output registers were entangled when
i measured the output register it automatically effected what was there and what happened
was it partially collapse the input register into an equals super position of each state
between zero and one such that the result that we measured c of the collapse output
register was there so essentially if we have found the value of one as my output register
then so so considering the case that we are just saying then the input register will partially
collapse to this the probabilities of each of these case as you can see would therefore
be probability will be one hour sixty four since our register is now in an equals superposition
of sixty four values which range from zero to two fifty but if you notice we already
have zero four eight so on so forth that is periodicity sitting in there but let us see
how it works so the quantum fourier transform that you have been eluding to if you now apply
that on the partially collapse input register what happens the fourier transform has the
effect of taking as state a and transforming it to a state by given by this so in order
those of you dont remember this is what quantum fourier transformed does essentially n if
we are transform does which takes any state ok you can in this case quantum state so itself
bracket a otherwise its any state get state a which has been transformed into the other
get state which has this particular exponential function but associated with it
and this this is just the normalization that which is attach to this kind away transformation
so we get this as our overall solution for all of them a is the set of all values
that seven to the power a mod fifteen yielded one in our particular case a is going to have
all these values so final state of the input register after quantum to the transform will
be of this kind right because i already have as i had mentioned in my last slide that
this is my internal register ok because all of these values zero four eight twelve whatever
with these particular weightage factor can be represented by these now it is in entangle
mod with the value that i have just measured which is one which meant that when i apply
the quantum fourier transform the the other part the partially collapsed the the
input register would now have this value so what will happen is the final state of the
input register after the quantum fourier transform therefore look like this entire thing which
is as the result of getting one as my output register ok when i look at this what we have
essentially done is the quantum fourier transform will essentially peak the probability amplitudes
at integer multiple of q by four in our case two fifty six by four or sixty four
so what will happen is will be getting values like zero sixty four one twenty eight one
ninety two and so on so forth clear so we no longer have an equals superposition of
states as we have started so that was the basic thing to understand here that although
we started with the equal superposition the act of measurement of one of them created
the input states to also have changed such that it no longer represents an equal superposition
and the quantum fourier transform essentially peaks the probability amplitudes in such a
way that we can now distinguish them ok and we no longer have an equal superposition to
state the probability amplitudes of the above states of now higher than the other states
in our register ok we measure the register and it will collapse with high probability
to one of these multiples of sixty four lets call this value p ok with our knowledge now
of q and p there are method of calculating the period of this function one method is
the continuous fraction expansion of the ratio between q and p
now this is again a classical principle and i can explain that in a minute now this classical
principle works out and since we have now essentially measured both the cases both q
and p we are in the classical domain so we can easily do the rest of the process in a
classical way however until now whatever we did was quantum mechanical although we used
many principles of classical economic but we have to remember that this quantum fourier
transform was essential to sort of understand the or highlight the differences from the
equal superposition state in order to collapse them to the periodic function so it was essentially
the one which find out the way how thinks are in a state which can now be used very
simply to get to period of the function and in this case particularly its like continuous
fraction expansion and let us to see how that works now that we have the period the factors
of n can be determine by taking the greater common deviser n with respect to x to the
power p divided by two plus one and x super p by two minus one that idea here is that
the computation will be done on a classical computer now this part is all classical thats
because any way we are out about cubic system entanglement everything else as associated
is done so for instance then in this particular case
when we know the numbers we have periodicity coming out as four so it will be seven divide
into the power four by two plus one fifteen g c d of that is five and the other one g
c d of seven to the power four divided two way to minus one fifteen is three so here
we have successfully factor fifteen now the point is for a simple severe problem where
we wanted to explain the idea to you it is how this goes but if you want to generalize
it this is where we had started with this can be done in an much more effective manner
ok now let me also look at a few aspects which
can be of concerned while we are doing this the few problems to look at is that the
quantum fourier transform comes of short and reveals the wrong period ok how how to handle
that the probability is actually dependent on your choice of the q the larger the q the
higher the probability of finding the correct probability ok so thats the point which we
have to remember that if you want to choose so so even for factoring a number like fifteen
we choose q to be as largest to fifty six if i have chosen say sixty four or you
know eight or something small like that the probability of finding the right answer
would have been much much wrong and the period would have been a difficulty so the reason
why this happens is that if you if you really want to find a period of any function you
really want to extent the you really want to see how this one behaves so you want enough
cycles to go and so if you are working with a very small number to start with the finding
of the period the oscillation or whatever you want to do in this would be difficult
more and more difficult so its better so use a larger number to work with this the the
period of series ends up being odd now the this is one of the case where we have
to actually just go back and pick a new number to start with because start with a new
co prime in that particular case because if the period of the series ends up being
odd then the further on whatever we want do does not work properly because as you can
see the final step essentially mean that we have to actually compute g c d of the period
function divided by two and once you have odd number this doesnt come out be a proper
way of looking at the fractions and so you can run into trouble so its not a good
idea if you have odd numbers to go forward the other part of the problem is that it may
be a situation where you can actually get into a quantum modular exponentiation problem
which which can which can be much slower than the quantum fourier transform and we
always often want to avoid this modular exponentiation part which we generally do and we always stick
to the quantum fourier transform method quantum modular exponentiation can be always
applied but its not going to benefit us so we dont want get into those as processes
now the other part which have mention was the continued fraction algorithm and here
is one of the cases its continued fraction is an expression of the form where we can
represent function series by just in terms of the fractional part of the starting
point so if i have mathematical form contains a zero all the way up to a m if it can be
represented in this form then i can actually look at these and get a continued fraction
approach in this way all of the guesses will work if a zero to a m are all positive
integers and any rational number actually can be represented as continued fraction and
so generally we say that the a zero to a m components are is a convergent of any of these
sets of zero to say m where so small m verses large m whenever we have these two cases
we know that we can find out we can state that these one of them is a subset or essentially
a convergent form of the other in the case that m is less than small m is less than capital
m so you can have an example here for example
if you have the number thirty one by thirteen you can write it down in the form of continued
fraction so basically thirty one by thirteen can be written in terms of two plus
one by thirteen or two plus one over thirteen by five which is then in equivalent to this
form and then that can be again brought down to this form essentially what i am doing is
i am bringing it down to a form where all the terms have similar forms so we get two
is the first term second term we get also two third time i get is one fourth one i get
is also one and finally we get the term two so this is how a continued fraction can
be represented for a number which has been given ok takes a little bit practice but once
you understand the representation as we have just shown you here in an example would be
able to do this thats the idea ok continued fraction algorithm terminates after a finite
number of splits and inverts steps for any rational number s over r so thats actually
good thing all right this s over r is unique ok and r will be the order of the order finding
problem and thats the advantage of use in the continued fraction algorithm because you
can always then find the order of the function so for example for n equal to fifteen if
you go through now the entire process which we have just now discussed all through several
time let me do this once more from the for all the steps for n equal to fifteen we
choose the random co prime integer x is equal to seven ok we get the order r equal to four
from the function as we have done before which is x to the power r mod n ok so the g c
d of this function is three which is an non trivial factor of fifteen and the g c d of
the plus formed fifteen is another non trivial factor and so thats how we have done this
now there are several applications of shors algorithm one is the as we discussed earlier
in very beginning is the encryption problem ok so the factoring is very important for
encryption because what happens is that if you have a large enough integer it will take
a long time for any computer to find its primes and therefore its an important approach
of being encryption which is what is happening here today nowadays thats the principle it
also very effective in terms of quantum stimulation because in many applications of quantum stimulation
we require factorization as the part of problem and then there are many other cases where
the technology aspect come in will deal with that later there are issues related to
both technology as well as theory but we will get into these things later on we have just
listed a few of them here anyway cryptography related to your factorization issues and not
being able to factorization issues these are technologies which are used to how to
do this problem and spin off the theory lies in complexity theory d m r g theory represent
ability theory not all of this are important for this particular course is just mentioned
here to completeness recent works on shors algorithm is something
which is of interest in two thousand one for example a seven qubit machine was built and
programmed to run the shors algorithm to successfully factor number fifteen but no entanglement
was observed this was because this was done in an n m r machine in an n m r machine it
is extreamly difficult to observe entanglement although the process of factorization is possible
it is a something which is very difficult to observe that so that was one thing
in two thousand twelve the this principle was updated better and factorization was of
twenty one was achieved and in april two thousand twelve the factorization of one forty
three as was also achieved so presently the the process of shors algorithm becoming
better and better is in hope i am sure they have been more work beyond the two thousand
twelve which has done a lot on shors algorithm however many a time its not just the number
which matters but its more important to find out how you can do better in terms of understanding
and thats why the first few are mentioned here the later on it is more important to
understand whatever you have missed when we were doing the shors algorithm in earlier
cases so that is one part of the problem that we have finished
now the other thing which i wanted to do here was to actually give you a few examples
of the applications and building scenario which i have been doing earlier also in a
couple of time not sure how these are going to come by right now i will just take a many
time get back you on that so after having gone through this entire process
of shors algorithm completely in many different steps over two lectures i would like to actually
do this once more in one go so that you are able to understand how this entire process
goes so it is a process of revisit so let me actually tell you we have done as of
now the shors algorithm essentially contains of five steps with technically only step two
requires the use of quantum computer however as we have mentioned over and over again use
of qubits make sure that we are essentially going to always use most of the step in this
process to be in the quantum way except one we have started measure so that i will mention
where we go to point where we have started the measure so we need not follow the quantum
way anymore so the first step is the random integer finding
which is going to be less than n such that they are co prime so given a number n that
we want to factorize we are going to choose an integer m which is less than the number
that we are going to factorize such that they are going to be co prime thats the first step
now this can be classical however the point you have to note is that this part would also
mean that we are strict in ourselves on the qubit space that we are going to use for a
quantum computer so thats why this is something where we want to keep as many qubits as
available to us the next step after setting it up which is
technically a classical one is to use quantum computer to determine the non period of the
function so that is the p for the period the function which we showed that it could done
by using quantum fourier transform in the most effective manner initially we create
the entanglement between the the input states and the output states the output states
essentially contain nothing to start out but its entangle to the input register that we
have created and then we can apply quantum fourier transform to go ahead and find out
how they can be distinguish from being equal superposition to a point that we can then
follow it on to the next step were we can find the period the period finding can be
done in a continued fraction manner which is again a classical step once we get there
then everything further on can be done in a classical manner so the step three which
is where the period if it is integer does not allow the to further because the next
periods the next part essentially involve mathematics which would not work precisely
if we keep using the odd integer so we have to go back to step one and start the process
again however its an integer even integer then we can go to the step where we can find
out the cases of mods between the plus one and minus one case of the number that we have
found with the periods and we can find out the case were if we get trivial solution then
we go back to the first step if we dont get the trivial solution we can continue on to
get the the final solution which will be the the factors of the numbers that we have
chosen so this is basically the principle the order finding problem can be classical
but when the case when we are actually using quantum mechanics we generally also would
like to put this under the quantum sense by applying a quantum fourier transform however
once we have measured the periods or once we have measured the factors once again we
do the process continued fraction to be able to get these problem and then we can go ahead
with the first part so the classical part essentially includes four steps except the
step two which we did so in the classical form the random number
is the one which is chosen then this part which is again which is doing the euclidean
arithmetic which does the g c d finding can all be done by using euclidean arithmetic
so in between this random number generation part to the part where we are going to find
the orders we we do the critical step of setting up the register and the output register setting
up the entanglement after them and finding quantum fourier transform so that we could
make sure that the member of the incident input bits are different and we started off
from equal superposition here these different set of number are then helping us to find
the measure of their numbers the collapsed measure numbers and those measure numbers
are then utilized in a continued fraction method to find the period and once the period
of the function is found then that can be again used to find the g c d and then the
factors and then we can keep on going back and forth by this principle
so the only path which is quantum mechanical is essentially embedded in this part which
is which is where the part is explained you can for trivial problems you can actually
see how it works in terms of the classical way of finding the way of periodicity you
find the values of all the possibilities of raising it to the numbers and then taking
the mods and getting the values and you can see that every fourth number after every four
numbers in this particular example of factorize in fifteen with a choice of the co prime
seven after every fourth number the the repeating starts so we have period of four now this
in the quantum way of looking is able to happen is possible to be made understood when we
do the registers and this is what was being explore explained here where we choose the
number such that we were able to first pick the particular value of x once we pick the
value of x which is the co prime then we went into the q c mod and in this q c mod it was
important that the integer that we choose will large enough ok now that also we have
seen in the pit falls of the shors algorithm case that this larger enough number is important
and so this is something where the this part is to be taken care once more
so once we have understood this idea that the principle of picking the value of the
co prime is the part which is classical we have to be careful in making sure that we
choose the number q which lies between the n squared and two n squared values thats the
part which is not going to be too small then we can use that number to set up our registers
because this number q is something where the periodicity will be finally coming out from
and if the number are too small then our periodicity doesnt form find out to be good so thats the
reason why these are the periods where we have to careful the quantum part was once
again explained slightly better here when we use the fourier transform method to sort
of make sure that one of the registers which is input register which was effected as a
result of measuring the output register could be made to set in away so that it
can be utilize later to find the period and so the way it was done was take the
idea of measuring the first register and then to the second register which was left over
was then continued to go ahead with the continued fraction approach
so here is the once more the idea of the preparing the data which we focused on today where we
loaded the input register with an equally weighted superposition all the integers from
zero to minus one with the value of q that we had chosen the number better be a large
number otherwise it will be difficult to get the proper period and then the total system
at that point is then utilized as an entangle set with the input register and the output
register we measure the output register when we apply the transformation x to power
a mod a to each member of the input register this is the quantum approach and store the
result of each computation in the output register these output register measure essentially
ensures that the input register values dependant on the exact value that is measured is the
output register so of all the possibilities so here here we go when we make a measurement
of the output register this will collapse the superposition to just one step now this
is the part which is most important because it is a entangle situation once we have focused
on one of the measurement that we make which is just one then the rest of the result which
exists in the input register is now collapsed also to represent only one of the following
sets so so once we say that our output register
will collapse to represent one of following of the possibilities we have in turn also
effected the input register so this is the part which is very important where we remove
the equals equation principle of the input registration case because of the way how thinks
are now so when we take a measurement of the output
register this will collapse to superposition to just one of the result of the transformation
and once we choose that let say the value c in this case it can be any one of them in
this particular example we had to chosen one then d input registers also got transformed
from their original value but please note it would still be in an equal superposition
of each state between zero to q minus one which yielded the c state so this is the part
which is very important still that the input register still remains in an equal superposition
once we have done this collapse measurement of the output case
so the partially collapsed inputs input register will of this kind with each probability coming
out as one over sixty four which means these are all equals superposition right now with
this we cannot go further because if we have equal superposition now we do not have a way
of going forward to find periodicity or other things in a quantum register we have to do
something more and thats the part where we applied quantum fourier transform once we
applied the quantum fourier transform the partially collapse input register the fourier
transform has the effect of taking the state taking the state and transform it into a state
which has the periodicity sitting in there which makes the inputs set no longer equivalent
that is the most important part here so in our particular case what happened was
the final state of the input register after the quantum fourier transform ended up being
something like that which is entangled to our measurement that we serve which is
one which meant that it peaks the probability amplitudes at integer multiples of q by four
which in over particular case is sixty four right and we no longer have equals superposition
of states so only those states which are represented as zero sixty four one twenty eight one ninety
two and so forth multiples of sixty four which have been seen the others which where suppose
to have equals superpositions are no longer available in that sense
so that so in this particular way if we now measure the register it will collapse to the
high probability one of these multiples of sixty four which we can call as some value
p now given the value of now p and the q that we started off with we can then find methods
classical methods which will help us to find the period of this ok so this allow us methods
of finding calculating the periods one method is continuous fraction approach expansion
approach of the ratio between q and p which is quite popular in turns out to be computationally
quite good and thats the classical one which which i have shown later on in one of the
slides to show it to you as to how that represents the actual result that we are looking for
so for example once we have the so that actually gives you period so basically once
you do this you would be finding out that that will give rise to the period of four
and once we get that we can essentially automatically calculate the two factors now in order to
get to that period of four so these are the error parts that we look at but in
order to get to the period of four what we did was we basically showed you an example
where we essentially showed how the continued fraction principle works we took any two
numbers and we showed that you know basically can write it down in terms of this and write
it in these forms and similarly if you do that for the case that we are looking at
for any rational number there is a unique value and the number as long as the value
which is going to be given by so what we will be finding is we will be finding s over r
where this r is going to be s over r will be unique the r will be the order of the finding
process of the problem and thats what we found and this is the way will finally showed you
that for the number fifteen found in a random co prime integer in integer x which is
seven we got the we get the order r for the function ok by applying this principle once
we get that which is how we showed in terms of continued fraction methods and others we
can go and find out the non trivial factors of fifteen and that was the basic idea
so with this i hope we have understood the principle of shors algorithm to a level
that it can be utilized and implemented in the quantum way and this is one of the
cases where the actual entanglement of process of quantum qubits i have being utilize
and so this is the most effective approach and shows exponential advantage over the classical
case in the next few cases lectures would go into more and more application based on
all the understanding that we are developed as of now
thank you