WEBVTT
00:13.679 --> 00:19.750
so we are continuing on shors algorithm so
here will do the shors algorithm once more
00:19.750 --> 00:26.900
in the actual quantum stepwise and will explain
to you how this can be done stepwise so the
00:26.900 --> 00:32.520
first step which is very important is the
preparation of the data as i mentioned earlier
00:32.520 --> 00:40.370
please remember that although the quantum
aspect of the process is being utilize in
00:40.370 --> 00:48.370
only one of the many steps of the shors algorithm
the moment you are dealing with quantum data
00:48.370 --> 00:54.920
we have no choice but to essentially process
the whole thing in a slightly different manner
00:54.920 --> 01:01.430
so although the quantum principle is only
going be used may be not all the time it will
01:01.430 --> 01:06.409
still be important to understand how this
is system so in the first step which is preparing
01:06.409 --> 01:13.140
of the data will be loading the input register
with an equally weighted superposition of
01:13.140 --> 01:22.460
all integers from zero to q equal to q minus
one which is basically zero to two fifty five
01:22.460 --> 01:31.240
because we said we are dealing with two fifty
six sets so the the output register will be
01:31.240 --> 01:37.130
loaded with all zeros because we dont know
anything about the output yet so the total
01:37.130 --> 01:44.530
state of the system at this point will be
the output register all zeros and the input
01:44.530 --> 01:52.231
register containing every possible value from
zero to two fifty five the comma that i have
01:52.231 --> 01:57.799
just put here denotes the registers are entangled
so thats actually very important so this pat
01:57.799 --> 02:04.869
particular part where we are preparing the
data has the quantum part incorporated in
02:04.869 --> 02:11.629
it in recognition of the fact that we are
considering this to be in the entangled condition
02:11.629 --> 02:16.670
so thats the part which is important in this
quantum principle
02:16.670 --> 02:24.159
the next part which is essentially modular
arithmetic on this entire quantum system is
02:24.159 --> 02:33.480
to apply the transformation x to the power
a mod of n to each member of the input register
02:33.480 --> 02:39.450
sorting the results of each computation in
the output register so these output register
02:39.450 --> 02:46.620
which was essentially unpopular or where
all equally propagated with zero are now going
02:46.620 --> 02:53.870
to have the values which are going to be the
numbers which have based on the values that
02:53.870 --> 03:01.280
we do and as you can see here these are now
going to have repeats
03:01.280 --> 03:06.870
so this is the part which is one kind and
this is the part if the other kind and this
03:06.870 --> 03:15.159
kind of shows up the principle that we have
been talking about periodicity earlier ok
03:15.159 --> 03:26.610
so once we have got in to this step ok which
were all working with entangle qubits we
03:26.610 --> 03:35.650
need to have the case were we can do as superposition
collapse so that we can understand the result
03:35.650 --> 03:42.129
because until that point of time we make the
collapse we do not have the result and so
03:42.129 --> 03:48.959
we make a we take a measurement on the output
register and this will collapse the superposition
03:48.959 --> 03:55.319
into represent just one of the results of
the transformation and if you call this value
03:55.319 --> 04:00.540
c then this is exactly how it will look like
or output register will collapse to represent
04:00.540 --> 04:10.559
one of the following one four seven or thirteen
right because if you look at it these are
04:10.559 --> 04:16.660
the distinct number we are getting again the
next time all its just repeating so at any
04:16.660 --> 04:22.460
point of time if you look at the solution
you will only get these four solutions thats
04:22.460 --> 04:28.510
it
so for an example say let us say that we have
04:28.510 --> 04:37.590
collapsed to one and see what happens this
is a result of that so now since the two registers
04:37.590 --> 04:43.449
are entangled measuring the output register
will have the effect of partially collapsing
04:43.449 --> 04:49.310
the input register into an equal superposition
of each state between zero and q minus one
04:49.310 --> 04:58.520
that yielded the value of the collapsed output
register this is the quantum aspect of
04:58.520 --> 05:06.289
this entire problem ok the very fact that
my input output registers were entangled when
05:06.289 --> 05:15.870
i measured the output register it automatically
effected what was there and what happened
05:15.870 --> 05:22.310
was it partially collapse the input register
into an equals super position of each state
05:22.310 --> 05:30.300
between zero and one such that the result
that we measured c of the collapse output
05:30.300 --> 05:40.159
register was there so essentially if we have
found the value of one as my output register
05:40.159 --> 05:47.389
then so so considering the case that we are
just saying then the input register will partially
05:47.389 --> 05:53.759
collapse to this the probabilities of each
of these case as you can see would therefore
05:53.759 --> 05:59.349
be probability will be one hour sixty four
since our register is now in an equals superposition
05:59.349 --> 06:06.129
of sixty four values which range from zero
to two fifty but if you notice we already
06:06.129 --> 06:13.169
have zero four eight so on so forth that is
periodicity sitting in there but let us see
06:13.169 --> 06:20.229
how it works so the quantum fourier transform
that you have been eluding to if you now apply
06:20.229 --> 06:27.290
that on the partially collapse input register
what happens the fourier transform has the
06:27.290 --> 06:35.499
effect of taking as state a and transforming
it to a state by given by this so in order
06:35.499 --> 06:41.681
those of you dont remember this is what quantum
fourier transformed does essentially n if
06:41.681 --> 06:48.800
we are transform does which takes any state
ok you can in this case quantum state so itself
06:48.800 --> 06:58.830
bracket a otherwise its any state get state
a which has been transformed into the other
06:58.830 --> 07:08.849
get state which has this particular
exponential function but associated with it
07:08.849 --> 07:19.689
and this this is just the normalization that
which is attach to this kind away transformation
07:19.689 --> 07:28.740
so we get this as our overall solution
for all of them a is the set of all values
07:28.740 --> 07:36.289
that seven to the power a mod fifteen yielded
one in our particular case a is going to have
07:36.289 --> 07:41.660
all these values so final state of the input
register after quantum to the transform will
07:41.660 --> 07:52.310
be of this kind right because i already have
as i had mentioned in my last slide that
07:52.310 --> 08:03.689
this is my internal register ok because all
of these values zero four eight twelve whatever
08:03.689 --> 08:09.020
with these particular weightage factor can
be represented by these now it is in entangle
08:09.020 --> 08:15.120
mod with the value that i have just measured
which is one which meant that when i apply
08:15.120 --> 08:24.249
the quantum fourier transform the the other
part the partially collapsed the the
08:24.249 --> 08:30.710
input register would now have this value so
what will happen is the final state of the
08:30.710 --> 08:35.289
input register after the quantum fourier transform
therefore look like this entire thing which
08:35.289 --> 08:46.740
is as the result of getting one as my output
register ok when i look at this what we have
08:46.740 --> 08:52.779
essentially done is the quantum fourier transform
will essentially peak the probability amplitudes
08:52.779 --> 09:00.180
at integer multiple of q by four in our case
two fifty six by four or sixty four
09:00.180 --> 09:05.769
so what will happen is will be getting values
like zero sixty four one twenty eight one
09:05.769 --> 09:15.339
ninety two and so on so forth clear so we
no longer have an equals superposition of
09:15.339 --> 09:20.560
states as we have started so that was the
basic thing to understand here that although
09:20.560 --> 09:28.320
we started with the equal superposition the
act of measurement of one of them created
09:28.320 --> 09:41.380
the input states to also have changed such
that it no longer represents an equal superposition
09:41.380 --> 09:47.920
and the quantum fourier transform essentially
peaks the probability amplitudes in such a
09:47.920 --> 09:53.149
way that we can now distinguish them ok and
we no longer have an equal superposition to
09:53.149 --> 09:57.959
state the probability amplitudes of the above
states of now higher than the other states
09:57.959 --> 10:04.380
in our register ok we measure the register
and it will collapse with high probability
10:04.380 --> 10:12.320
to one of these multiples of sixty four lets
call this value p ok with our knowledge now
10:12.320 --> 10:20.470
of q and p there are method of calculating
the period of this function one method is
10:20.470 --> 10:25.600
the continuous fraction expansion of the ratio
between q and p
10:25.600 --> 10:31.290
now this is again a classical principle and
i can explain that in a minute now this classical
10:31.290 --> 10:38.001
principle works out and since we have now
essentially measured both the cases both q
10:38.001 --> 10:44.589
and p we are in the classical domain so we
can easily do the rest of the process in a
10:44.589 --> 10:49.820
classical way however until now whatever we
did was quantum mechanical although we used
10:49.820 --> 10:57.470
many principles of classical economic but
we have to remember that this quantum fourier
10:57.470 --> 11:08.480
transform was essential to sort of understand
the or highlight the differences from the
11:08.480 --> 11:15.139
equal superposition state in order to collapse
them to the periodic function so it was essentially
11:15.139 --> 11:19.970
the one which find out the way how thinks
are in a state which can now be used very
11:19.970 --> 11:25.529
simply to get to period of the function and
in this case particularly its like continuous
11:25.529 --> 11:32.040
fraction expansion and let us to see how that
works now that we have the period the factors
11:32.040 --> 11:38.149
of n can be determine by taking the greater
common deviser n with respect to x to the
11:38.149 --> 11:44.620
power p divided by two plus one and x super
p by two minus one that idea here is that
11:44.620 --> 11:49.490
the computation will be done on a classical
computer now this part is all classical thats
11:49.490 --> 11:54.810
because any way we are out about cubic system
entanglement everything else as associated
11:54.810 --> 11:59.430
is done
so for instance then in this particular case
11:59.430 --> 12:07.410
when we know the numbers we have periodicity
coming out as four so it will be seven divide
12:07.410 --> 12:13.380
into the power four by two plus one fifteen
g c d of that is five and the other one g
12:13.380 --> 12:20.220
c d of seven to the power four divided two
way to minus one fifteen is three so here
12:20.220 --> 12:25.350
we have successfully factor fifteen now the
point is for a simple severe problem where
12:25.350 --> 12:29.829
we wanted to explain the idea to you it is
how this goes but if you want to generalize
12:29.829 --> 12:35.110
it this is where we had started with this
can be done in an much more effective manner
12:35.110 --> 12:40.259
ok
now let me also look at a few aspects which
12:40.259 --> 12:48.680
can be of concerned while we are doing this
the few problems to look at is that the
12:48.680 --> 12:54.610
quantum fourier transform comes of short and
reveals the wrong period ok how how to handle
12:54.610 --> 13:00.639
that the probability is actually dependent
on your choice of the q the larger the q the
13:00.639 --> 13:05.959
higher the probability of finding the correct
probability ok so thats the point which we
13:05.959 --> 13:12.000
have to remember that if you want to choose
so so even for factoring a number like fifteen
13:12.000 --> 13:19.170
we choose q to be as largest to fifty six
if i have chosen say sixty four or you
13:19.170 --> 13:25.019
know eight or something small like that
the probability of finding the right answer
13:25.019 --> 13:31.110
would have been much much wrong and the period
would have been a difficulty so the reason
13:31.110 --> 13:35.750
why this happens is that if you if you really
want to find a period of any function you
13:35.750 --> 13:42.029
really want to extent the you really want
to see how this one behaves so you want enough
13:42.029 --> 13:47.790
cycles to go and so if you are working with
a very small number to start with the finding
13:47.790 --> 13:52.920
of the period the oscillation or whatever
you want to do in this would be difficult
13:52.920 --> 14:00.331
more and more difficult so its better so use
a larger number to work with this the the
14:00.331 --> 14:08.300
period of series ends up being odd now
the this is one of the case where we have
14:08.300 --> 14:15.870
to actually just go back and pick a new number
to start with because start with a new
14:15.870 --> 14:19.920
co prime in that particular case because
if the period of the series ends up being
14:19.920 --> 14:25.410
odd then the further on whatever we want do
does not work properly because as you can
14:25.410 --> 14:31.750
see the final step essentially mean that we
have to actually compute g c d of the period
14:31.750 --> 14:37.089
function divided by two and once you have
odd number this doesnt come out be a proper
14:37.089 --> 14:43.829
way of looking at the fractions and so
you can run into trouble so its not a good
14:43.829 --> 14:53.390
idea if you have odd numbers to go forward
the other part of the problem is that it may
14:53.390 --> 14:59.350
be a situation where you can actually get
into a quantum modular exponentiation problem
14:59.350 --> 15:06.360
which which can which can be much slower
than the quantum fourier transform and we
15:06.360 --> 15:14.720
always often want to avoid this modular exponentiation
part which we generally do and we always stick
15:14.720 --> 15:19.990
to the quantum fourier transform method
quantum modular exponentiation can be always
15:19.990 --> 15:26.990
applied but its not going to benefit us so
we dont want get into those as processes
15:26.990 --> 15:32.879
now the other part which have mention was
the continued fraction algorithm and here
15:32.879 --> 15:38.839
is one of the cases its continued fraction
is an expression of the form where we can
15:38.839 --> 15:52.769
represent function series by just in
terms of the fractional part of the starting
15:52.769 --> 16:01.160
point so if i have mathematical form contains
a zero all the way up to a m if it can be
16:01.160 --> 16:07.319
represented in this form then i can actually
look at these and get a continued fraction
16:07.319 --> 16:13.850
approach in this way all of the guesses will
work if a zero to a m are all positive
16:13.850 --> 16:21.790
integers and any rational number actually
can be represented as continued fraction and
16:21.790 --> 16:31.480
so generally we say that the a zero to a m
components are is a convergent of any of these
16:31.480 --> 16:41.209
sets of zero to say m where so small m verses
large m whenever we have these two cases
16:41.209 --> 16:49.670
we know that we can find out we can state
that these one of them is a subset or essentially
16:49.670 --> 16:57.690
a convergent form of the other in the case
that m is less than small m is less than capital
16:57.690 --> 17:01.320
m
so you can have an example here for example
17:01.320 --> 17:07.130
if you have the number thirty one by thirteen
you can write it down in the form of continued
17:07.130 --> 17:15.770
fraction so basically thirty one by
thirteen can be written in terms of two plus
17:15.770 --> 17:26.080
one by thirteen or two plus one over thirteen
by five which is then in equivalent to this
17:26.080 --> 17:32.580
form and then that can be again brought down
to this form essentially what i am doing is
17:32.580 --> 17:42.830
i am bringing it down to a form where all
the terms have similar forms so we get two
17:42.830 --> 17:57.450
is the first term second term we get also
two third time i get is one fourth one i get
17:57.450 --> 18:11.440
is also one and finally we get the term two
so this is how a continued fraction can
18:11.440 --> 18:19.690
be represented for a number which has been
given ok takes a little bit practice but once
18:19.690 --> 18:25.500
you understand the representation as we have
just shown you here in an example would be
18:25.500 --> 18:35.300
able to do this thats the idea ok continued
fraction algorithm terminates after a finite
18:35.300 --> 18:41.990
number of splits and inverts steps for any
rational number s over r so thats actually
18:41.990 --> 18:52.120
good thing all right this s over r is unique
ok and r will be the order of the order finding
18:52.120 --> 18:56.890
problem and thats the advantage of use in
the continued fraction algorithm because you
18:56.890 --> 19:06.080
can always then find the order of the function
so for example for n equal to fifteen if
19:06.080 --> 19:10.200
you go through now the entire process which
we have just now discussed all through several
19:10.200 --> 19:19.740
time let me do this once more from the
for all the steps for n equal to fifteen we
19:19.740 --> 19:27.220
choose the random co prime integer x is equal
to seven ok we get the order r equal to four
19:27.220 --> 19:37.240
from the function as we have done before which
is x to the power r mod n ok so the g c
19:37.240 --> 19:43.890
d of this function is three which is an non
trivial factor of fifteen and the g c d of
19:43.890 --> 19:51.260
the plus formed fifteen is another non trivial
factor and so thats how we have done this
19:51.260 --> 20:00.210
now there are several applications of shors
algorithm one is the as we discussed earlier
20:00.210 --> 20:06.820
in very beginning is the encryption problem
ok so the factoring is very important for
20:06.820 --> 20:13.430
encryption because what happens is that if
you have a large enough integer it will take
20:13.430 --> 20:20.750
a long time for any computer to find its primes
and therefore its an important approach
20:20.750 --> 20:27.040
of being encryption which is what is happening
here today nowadays thats the principle it
20:27.040 --> 20:33.420
also very effective in terms of quantum stimulation
because in many applications of quantum stimulation
20:33.420 --> 20:39.920
we require factorization as the part of problem
and then there are many other cases where
20:39.920 --> 20:47.810
the technology aspect come in will deal with
that later there are issues related to
20:47.810 --> 20:53.520
both technology as well as theory but we will
get into these things later on we have just
20:53.520 --> 21:00.740
listed a few of them here anyway cryptography
related to your factorization issues and not
21:00.740 --> 21:06.320
being able to factorization issues these
are technologies which are used to how to
21:06.320 --> 21:13.510
do this problem and spin off the theory lies
in complexity theory d m r g theory represent
21:13.510 --> 21:19.760
ability theory not all of this are important
for this particular course is just mentioned
21:19.760 --> 21:26.100
here to completeness
recent works on shors algorithm is something
21:26.100 --> 21:32.370
which is of interest in two thousand one for
example a seven qubit machine was built and
21:32.370 --> 21:37.700
programmed to run the shors algorithm to successfully
factor number fifteen but no entanglement
21:37.700 --> 21:45.540
was observed this was because this was done
in an n m r machine in an n m r machine it
21:45.540 --> 21:52.310
is extreamly difficult to observe entanglement
although the process of factorization is possible
21:52.310 --> 21:57.400
it is a something which is very difficult
to observe that so that was one thing
21:57.400 --> 22:04.530
in two thousand twelve the this principle
was updated better and factorization was of
22:04.530 --> 22:10.900
twenty one was achieved and in april two
thousand twelve the factorization of one forty
22:10.900 --> 22:18.830
three as was also achieved so presently
the the process of shors algorithm becoming
22:18.830 --> 22:24.360
better and better is in hope i am sure they
have been more work beyond the two thousand
22:24.360 --> 22:32.320
twelve which has done a lot on shors algorithm
however many a time its not just the number
22:32.320 --> 22:38.400
which matters but its more important to find
out how you can do better in terms of understanding
22:38.400 --> 22:44.970
and thats why the first few are mentioned
here the later on it is more important to
22:44.970 --> 22:51.450
understand whatever you have missed when we
were doing the shors algorithm in earlier
22:51.450 --> 22:59.290
cases so that is one part of the problem
that we have finished
22:59.290 --> 23:08.220
now the other thing which i wanted to do
here was to actually give you a few examples
23:08.220 --> 23:15.450
of the applications and building scenario
which i have been doing earlier also in a
23:15.450 --> 23:23.270
couple of time not sure how these are going
to come by right now i will just take a many
23:23.270 --> 23:29.260
time get back you on that
so after having gone through this entire process
23:29.260 --> 23:36.030
of shors algorithm completely in many different
steps over two lectures i would like to actually
23:36.030 --> 23:41.010
do this once more in one go so that you are
able to understand how this entire process
23:41.010 --> 23:46.740
goes so it is a process of revisit so let
me actually tell you we have done as of
23:46.740 --> 23:55.840
now the shors algorithm essentially contains
of five steps with technically only step two
23:55.840 --> 24:02.270
requires the use of quantum computer however
as we have mentioned over and over again use
24:02.270 --> 24:10.900
of qubits make sure that we are essentially
going to always use most of the step in this
24:10.900 --> 24:17.610
process to be in the quantum way except one
we have started measure so that i will mention
24:17.610 --> 24:24.480
where we go to point where we have started
the measure so we need not follow the quantum
24:24.480 --> 24:32.130
way anymore
so the first step is the random integer finding
24:32.130 --> 24:37.050
which is going to be less than n such that
they are co prime so given a number n that
24:37.050 --> 24:46.030
we want to factorize we are going to choose
an integer m which is less than the number
24:46.030 --> 24:51.760
that we are going to factorize such that they
are going to be co prime thats the first step
24:51.760 --> 24:57.660
now this can be classical however the point
you have to note is that this part would also
24:57.660 --> 25:03.870
mean that we are strict in ourselves on the
qubit space that we are going to use for a
25:03.870 --> 25:08.690
quantum computer so thats why this is something
where we want to keep as many qubits as
25:08.690 --> 25:13.690
available to us
the next step after setting it up which is
25:13.690 --> 25:20.740
technically a classical one is to use quantum
computer to determine the non period of the
25:20.740 --> 25:26.990
function so that is the p for the period the
function which we showed that it could done
25:26.990 --> 25:32.540
by using quantum fourier transform in the
most effective manner initially we create
25:32.540 --> 25:39.660
the entanglement between the the input
states and the output states the output states
25:39.660 --> 25:46.170
essentially contain nothing to start out but
its entangle to the input register that we
25:46.170 --> 25:52.480
have created and then we can apply quantum
fourier transform to go ahead and find out
25:52.480 --> 25:58.680
how they can be distinguish from being equal
superposition to a point that we can then
25:58.680 --> 26:07.550
follow it on to the next step were we can
find the period the period finding can be
26:07.550 --> 26:13.510
done in a continued fraction manner which
is again a classical step once we get there
26:13.510 --> 26:19.250
then everything further on can be done in
a classical manner so the step three which
26:19.250 --> 26:27.620
is where the period if it is integer does
not allow the to further because the next
26:27.620 --> 26:35.500
periods the next part essentially involve
mathematics which would not work precisely
26:35.500 --> 26:40.020
if we keep using the odd integer so we have
to go back to step one and start the process
26:40.020 --> 26:47.280
again however its an integer even integer
then we can go to the step where we can find
26:47.280 --> 26:53.800
out the cases of mods between the plus one
and minus one case of the number that we have
26:53.800 --> 27:00.320
found with the periods and we can find out
the case were if we get trivial solution then
27:00.320 --> 27:05.460
we go back to the first step if we dont get
the trivial solution we can continue on to
27:05.460 --> 27:16.880
get the the final solution which will be the
the factors of the numbers that we have
27:16.880 --> 27:30.210
chosen so this is basically the principle
the order finding problem can be classical
27:30.210 --> 27:36.530
but when the case when we are actually using
quantum mechanics we generally also would
27:36.530 --> 27:44.500
like to put this under the quantum sense
by applying a quantum fourier transform however
27:44.500 --> 27:49.830
once we have measured the periods or once
we have measured the factors once again we
27:49.830 --> 27:57.630
do the process continued fraction to be able
to get these problem and then we can go ahead
27:57.630 --> 28:03.080
with the first part so the classical part
essentially includes four steps except the
28:03.080 --> 28:10.460
step two which we did
so in the classical form the random number
28:10.460 --> 28:16.960
is the one which is chosen then this part
which is again which is doing the euclidean
28:16.960 --> 28:25.340
arithmetic which does the g c d finding can
all be done by using euclidean arithmetic
28:25.340 --> 28:33.920
so in between this random number generation
part to the part where we are going to find
28:33.920 --> 28:44.700
the orders we we do the critical step of setting
up the register and the output register setting
28:44.700 --> 28:58.890
up the entanglement after them and finding
quantum fourier transform so that we could
28:58.890 --> 29:07.500
make sure that the member of the incident
input bits are different and we started off
29:07.500 --> 29:16.230
from equal superposition here these different
set of number are then helping us to find
29:16.230 --> 29:21.710
the measure of their numbers the collapsed
measure numbers and those measure numbers
29:21.710 --> 29:29.890
are then utilized in a continued fraction
method to find the period and once the period
29:29.890 --> 29:36.950
of the function is found then that can be
again used to find the g c d and then the
29:36.950 --> 29:40.880
factors and then we can keep on going back
and forth by this principle
29:40.880 --> 29:46.950
so the only path which is quantum mechanical
is essentially embedded in this part which
29:46.950 --> 29:54.140
is which is where the part is explained
you can for trivial problems you can actually
29:54.140 --> 29:58.780
see how it works in terms of the classical
way of finding the way of periodicity you
29:58.780 --> 30:07.190
find the values of all the possibilities of
raising it to the numbers and then taking
30:07.190 --> 30:11.941
the mods and getting the values and you can
see that every fourth number after every four
30:11.941 --> 30:19.950
numbers in this particular example of factorize
in fifteen with a choice of the co prime
30:19.950 --> 30:27.630
seven after every fourth number the the repeating
starts so we have period of four now this
30:27.630 --> 30:33.630
in the quantum way of looking is able to happen
is possible to be made understood when we
30:33.630 --> 30:40.760
do the registers and this is what was being
explore explained here where we choose the
30:40.760 --> 30:48.230
number such that we were able to first pick
the particular value of x once we pick the
30:48.230 --> 30:53.650
value of x which is the co prime then we went
into the q c mod and in this q c mod it was
30:53.650 --> 31:00.060
important that the integer that we choose
will large enough ok now that also we have
31:00.060 --> 31:05.820
seen in the pit falls of the shors algorithm
case that this larger enough number is important
31:05.820 --> 31:12.040
and so this is something where the this part
is to be taken care once more
31:12.040 --> 31:20.110
so once we have understood this idea that
the principle of picking the value of the
31:20.110 --> 31:29.390
co prime is the part which is classical we
have to be careful in making sure that we
31:29.390 --> 31:38.120
choose the number q which lies between the
n squared and two n squared values thats the
31:38.120 --> 31:44.670
part which is not going to be too small then
we can use that number to set up our registers
31:44.670 --> 31:50.880
because this number q is something where the
periodicity will be finally coming out from
31:50.880 --> 31:55.860
and if the number are too small then our periodicity
doesnt form find out to be good so thats the
31:55.860 --> 32:00.260
reason why these are the periods where we
have to careful the quantum part was once
32:00.260 --> 32:07.340
again explained slightly better here when
we use the fourier transform method to sort
32:07.340 --> 32:13.230
of make sure that one of the registers which
is input register which was effected as a
32:13.230 --> 32:19.760
result of measuring the output register
could be made to set in away so that it
32:19.760 --> 32:28.630
can be utilize later to find the period
and so the way it was done was take the
32:28.630 --> 32:38.510
idea of measuring the first register and then
to the second register which was left over
32:38.510 --> 32:43.330
was then continued to go ahead with the continued
fraction approach
32:43.330 --> 32:50.010
so here is the once more the idea of the preparing
the data which we focused on today where we
32:50.010 --> 32:53.900
loaded the input register with an equally
weighted superposition all the integers from
32:53.900 --> 33:01.400
zero to minus one with the value of q that
we had chosen the number better be a large
33:01.400 --> 33:05.890
number otherwise it will be difficult to get
the proper period and then the total system
33:05.890 --> 33:13.500
at that point is then utilized as an entangle
set with the input register and the output
33:13.500 --> 33:21.250
register we measure the output register
when we apply the transformation x to power
33:21.250 --> 33:28.360
a mod a to each member of the input register
this is the quantum approach and store the
33:28.360 --> 33:35.740
result of each computation in the output register
these output register measure essentially
33:35.740 --> 33:44.691
ensures that the input register values dependant
on the exact value that is measured is the
33:44.691 --> 33:50.660
output register so of all the possibilities
so here here we go when we make a measurement
33:50.660 --> 33:54.490
of the output register this will collapse
the superposition to just one step now this
33:54.490 --> 33:59.940
is the part which is most important because
it is a entangle situation once we have focused
33:59.940 --> 34:05.850
on one of the measurement that we make which
is just one then the rest of the result which
34:05.850 --> 34:14.450
exists in the input register is now collapsed
also to represent only one of the following
34:14.450 --> 34:18.580
sets
so so once we say that our output register
34:18.580 --> 34:26.260
will collapse to represent one of following
of the possibilities we have in turn also
34:26.260 --> 34:32.609
effected the input register so this is the
part which is very important where we remove
34:32.609 --> 34:38.629
the equals equation principle of the input
registration case because of the way how thinks
34:38.629 --> 34:48.869
are now
so when we take a measurement of the output
34:48.869 --> 34:55.919
register this will collapse to superposition
to just one of the result of the transformation
34:55.919 --> 35:00.809
and once we choose that let say the value
c in this case it can be any one of them in
35:00.809 --> 35:11.589
this particular example we had to chosen one
then d input registers also got transformed
35:11.589 --> 35:17.430
from their original value but please note
it would still be in an equal superposition
35:17.430 --> 35:21.809
of each state between zero to q minus one
which yielded the c state so this is the part
35:21.809 --> 35:27.790
which is very important still that the input
register still remains in an equal superposition
35:27.790 --> 35:35.270
once we have done this collapse measurement
of the output case
35:35.270 --> 35:42.269
so the partially collapsed inputs input register
will of this kind with each probability coming
35:42.269 --> 35:48.400
out as one over sixty four which means these
are all equals superposition right now with
35:48.400 --> 35:53.539
this we cannot go further because if we have
equal superposition now we do not have a way
35:53.539 --> 35:58.859
of going forward to find periodicity or other
things in a quantum register we have to do
35:58.859 --> 36:03.420
something more and thats the part where we
applied quantum fourier transform once we
36:03.420 --> 36:08.109
applied the quantum fourier transform the
partially collapse input register the fourier
36:08.109 --> 36:13.829
transform has the effect of taking the state
taking the state and transform it into a state
36:13.829 --> 36:23.339
which has the periodicity sitting in there
which makes the inputs set no longer equivalent
36:23.339 --> 36:30.559
that is the most important part here
so in our particular case what happened was
36:30.559 --> 36:34.710
the final state of the input register after
the quantum fourier transform ended up being
36:34.710 --> 36:39.089
something like that which is entangled
to our measurement that we serve which is
36:39.089 --> 36:47.250
one which meant that it peaks the probability
amplitudes at integer multiples of q by four
36:47.250 --> 36:52.910
which in over particular case is sixty four
right and we no longer have equals superposition
36:52.910 --> 36:58.359
of states so only those states which are represented
as zero sixty four one twenty eight one ninety
36:58.359 --> 37:04.920
two and so forth multiples of sixty four which
have been seen the others which where suppose
37:04.920 --> 37:12.359
to have equals superpositions are no longer
available in that sense
37:12.359 --> 37:18.520
so that so in this particular way if we now
measure the register it will collapse to the
37:18.520 --> 37:24.630
high probability one of these multiples of
sixty four which we can call as some value
37:24.630 --> 37:33.420
p now given the value of now p and the q that
we started off with we can then find methods
37:33.420 --> 37:41.349
classical methods which will help us to find
the period of this ok so this allow us methods
37:41.349 --> 37:47.260
of finding calculating the periods one method
is continuous fraction approach expansion
37:47.260 --> 37:51.619
approach of the ratio between q and p which
is quite popular in turns out to be computationally
37:51.619 --> 37:57.270
quite good and thats the classical one which
which i have shown later on in one of the
37:57.270 --> 38:03.779
slides to show it to you as to how that represents
the actual result that we are looking for
38:03.779 --> 38:08.349
so for example once we have the so that
actually gives you period so basically once
38:08.349 --> 38:12.440
you do this you would be finding out that
that will give rise to the period of four
38:12.440 --> 38:18.109
and once we get that we can essentially automatically
calculate the two factors now in order to
38:18.109 --> 38:25.460
get to that period of four so these
are the error parts that we look at but in
38:25.460 --> 38:30.109
order to get to the period of four what we
did was we basically showed you an example
38:30.109 --> 38:37.820
where we essentially showed how the continued
fraction principle works we took any two
38:37.820 --> 38:42.410
numbers and we showed that you know basically
can write it down in terms of this and write
38:42.410 --> 38:50.269
it in these forms and similarly if you do
that for the case that we are looking at
38:50.269 --> 38:56.819
for any rational number there is a unique
value and the number as long as the value
38:56.819 --> 39:02.630
which is going to be given by so what we will
be finding is we will be finding s over r
39:02.630 --> 39:09.829
where this r is going to be s over r will
be unique the r will be the order of the finding
39:09.829 --> 39:18.089
process of the problem and thats what we found
and this is the way will finally showed you
39:18.089 --> 39:25.539
that for the number fifteen found in a random
co prime integer in integer x which is
39:25.539 --> 39:34.009
seven we got the we get the order r for the
function ok by applying this principle once
39:34.009 --> 39:39.839
we get that which is how we showed in terms
of continued fraction methods and others we
39:39.839 --> 39:47.500
can go and find out the non trivial factors
of fifteen and that was the basic idea
39:47.500 --> 39:54.079
so with this i hope we have understood
the principle of shors algorithm to a level
39:54.079 --> 40:03.180
that it can be utilized and implemented
in the quantum way and this is one of the
40:03.180 --> 40:09.299
cases where the actual entanglement of process
of quantum qubits i have being utilize
40:09.299 --> 40:15.410
and so this is the most effective approach
and shows exponential advantage over the classical
40:15.410 --> 40:23.680
case in the next few cases lectures would
go into more and more application based on
40:23.680 --> 40:30.569
all the understanding that we are developed
as of now
40:30.569 --> 40:32.869
thank you