WEBVTT
00:13.480 --> 00:17.869
we have been summarizing all the aspects of
quantum computing implementations that we
00:17.869 --> 00:24.260
have been dealing with in this course in this
week what we are now trying to do is trying
00:24.260 --> 00:29.640
to see how all the different aspects that
we have discussed in this course as a part
00:29.640 --> 00:35.670
of implementation how does it work in conjunction
to make sure that quantum computing becomes
00:35.670 --> 00:42.390
a viability it is an interdisciplinary field
so it takes a lot of different areas and therefore
00:42.390 --> 00:48.850
we are spending this last week in a lot of
detailed discussions of the different aspects
00:48.850 --> 00:51.430
of subjects that we have covered
00:51.430 --> 00:58.320
so in this lecture we will be looking into
the digital verses quantum computing aspects
00:58.320 --> 01:06.920
from the principle of looking at the traveling
salesman problem what we have learned until
01:06.920 --> 01:13.789
now is the digital computing produces serial
results on the other hand quantum is truly
01:13.789 --> 01:25.619
concurrent or parallel digital computers need
an exponential amount of resources to accomplish
01:25.619 --> 01:33.819
a task which can become polynomial in the
quantum sense thats because quantum computers
01:33.819 --> 01:41.709
perform two to the power n computations where
n is the number of qubits so these are the
01:41.709 --> 01:48.700
basic advantages we have taken when we went
from digital to quantum so some of the very
01:48.700 --> 01:58.899
simple examples of the quantum nature has
been told in terms of very basics of interference
01:58.899 --> 02:09.009
for example the two slit experiment where
if it is a classical case then for a single
02:09.009 --> 02:15.700
slit the bullets will only come from one of
the two places where the holes are on the
02:15.700 --> 02:21.489
other hand when both of them are simultaneously
present then it produces interference for
02:21.489 --> 02:31.379
example take a look at a wave for example
the sound waves their behavior is something
02:31.379 --> 02:38.209
which is very different from when only particles
have being considered classical particles
02:38.209 --> 02:42.310
so to appreciate this let me show this once
more
02:42.310 --> 02:48.230
so bullets are classical particles let us
consider the case where we are going to have
02:48.230 --> 02:57.219
two slits going on to a detector but for understanding
this let us start with one slit so when we
02:57.219 --> 03:03.049
have bullets passes through one here is the
distribution on the other hand if we have
03:03.049 --> 03:07.260
the bullet on the going through the other
slit there is the distribution only one of
03:07.260 --> 03:12.769
them are open if both of them are open then
what will happen is will get a total distribution
03:12.769 --> 03:22.810
which is of this kind so one two and this
one is one plus two on the other hand when
03:22.810 --> 03:32.650
we do sound waves let say then if we have
the similar situation of one slit or the other
03:32.650 --> 03:41.219
slit the initial idea of having one each is
fine but when we have both the slits open
03:41.219 --> 03:47.389
they dont simply show the addition that we
just showed you for the bullets instead it
03:47.389 --> 03:54.739
shows an oscillating pattern which is the
superposition which is distinct from the individuals
03:54.739 --> 04:03.700
that we talked about so that is the wave part
or the interference nature of this so this
04:03.700 --> 04:10.799
same thing extend to the electrons and just
going to show this for completeness and so
04:10.799 --> 04:15.889
we know that electrons essentially although
they are particles may be a light wave but
04:15.889 --> 04:22.720
when we are observing electrons then we do
see them as bullets
04:22.720 --> 04:29.570
so they be a waste particles so that is the
dilemma with quantum mechanics which is what
04:29.570 --> 04:36.600
we are working on when we go to fundamental
particles which are quantum then they have
04:36.600 --> 04:43.070
both the properties when we observe them that
is when we make that classical then they behave
04:43.070 --> 04:53.500
exactly like a particle analogues to the bullets
that we talked about but many of their other
04:53.500 --> 05:00.640
phenomena behave like wave like which is what
when we talked about the sound wave so that
05:00.640 --> 05:05.480
is all the principles of quantum mechanics
just summarized here so in terms of quantum
05:05.480 --> 05:14.720
computation we have been utilizing the concept
of superposition both zero and one and the
05:14.720 --> 05:20.380
qubit representation has been in terms of
the number of wave functions that we are using
05:20.380 --> 05:28.020
so the superposition of states for instance
would essentially have a concept of amplitude
05:28.020 --> 05:33.380
square of which leads to probability these
are all the concepts that we have taken as
05:33.380 --> 05:39.500
a result a summation of all the square of
the amplitudes for the states would always
05:39.500 --> 05:47.470
be equal to one in order to make the probability
loss to be sustained so we have been using
05:47.470 --> 05:56.300
these kinds of states entangled states superposition
states and we have been representing them
05:56.300 --> 06:02.930
either in vector term or in the matrix term
and whenever we want to change them we talk
06:02.930 --> 06:09.990
in terms of unitary transformations which
are essentially unitary matrices whose conjugate
06:09.990 --> 06:13.020
transpose is the inverse
06:13.020 --> 06:19.030
essentially ensuring their harmitian nature
of the system is preserved so we have shown
06:19.030 --> 06:28.240
many a times hadamard transforms where we
can go from a particular pure state to a mix
06:28.240 --> 06:34.460
state for instance we also have talked about
other simpler gates for example the c naught
06:34.460 --> 06:40.870
gate the not gate c naught is the two qubit
gate not gate can be single qubit gate and
06:40.870 --> 06:48.680
so on and so forth there are visual representations
which essentially tell us about the circuits
06:48.680 --> 06:58.530
the wires the representation of the gates
and how they interact the hadamard c naught
06:58.530 --> 07:03.940
and so on and so forth in order to do something
more interesting we would like to use one
07:03.940 --> 07:09.710
of the algorithms which help us in getting
forward with ideas of computation and one
07:09.710 --> 07:15.280
of the major once as we have discussed is
the grovers search algorithm which is in polynomial
07:15.280 --> 07:22.650
time whereas the one in shors algorithm is
in exponential time however the grovers algorithm
07:22.650 --> 07:28.960
has the advantage of wider applicability because
it is looking for research
07:28.960 --> 07:35.470
so its analogy is always given with respect
to searching in unsorted set of data for example
07:35.470 --> 07:44.150
a phone book to find a specific number without
rearranging so the idea always have been to
07:44.150 --> 07:49.750
magnify the amplitude of the chosen number
and always we use the concept that there is
07:49.750 --> 07:55.860
an oracle which knows the solution so you
flip the amplitudes of the selected items
07:55.860 --> 08:02.860
and rotate all the amplitudes around the average
and repeat this until the selected items probability
08:02.860 --> 08:09.590
of being red is greater than half so that
it can be observed so in terms of graphical
08:09.590 --> 08:18.520
representation this is what we have done earlier
at once we get a marked system basically can
08:18.520 --> 08:25.050
go through the flip and then average them
and then flip all the amplitudes around the
08:25.050 --> 08:28.390
average to get the mark state amplified
08:28.390 --> 08:39.050
the time complexity as i mentioned its in
terms of square root of n whereas in terms
08:39.050 --> 08:45.029
of a normal classical surge the minimum number
on an average that you require is an n by
08:45.029 --> 08:51.689
two so there is a large in hands men when
we go to grovers algorithm now we would like
08:51.689 --> 08:59.120
to actually extend this problem to the traveling
salesmen problem thats because the principle
08:59.120 --> 09:08.519
of a traveling salesmen problem is that they
require going through the different paths
09:08.519 --> 09:18.209
with different levels and the difficulty
is that its not possible to go through the
09:18.209 --> 09:23.430
search in this particular case in a simple
polynomial structure as it is possible for
09:23.430 --> 09:29.139
a classical computer so here is an example
of a traveling salesman problem where the
09:29.139 --> 09:37.670
a b c d e are the vertices or the points into
which these traveling salesman is suppose
09:37.670 --> 09:44.100
to go that individual can take different paths
and thats roughly the basic idea behind this
09:44.100 --> 09:50.670
problem to start with and they can have different
weightage factors depending on how many times
09:50.670 --> 09:54.500
a particular path is being traveled verses
the other
09:54.500 --> 10:01.120
so here is an example of a path which is being
shown here where this particular path route
10:01.120 --> 10:08.519
can be taken to go to all the five points
that we have discussed so this is sort of
10:08.519 --> 10:15.019
like a moving target traveling salesman that
we just discussed that the target itself is
10:15.019 --> 10:20.430
moving so that you can do a traveling salesman
moving target point to be problem so we have
10:20.430 --> 10:28.949
this origin from where it starts and we have
the particles or the points move with respect
10:28.949 --> 10:33.860
to the origin so these two are moving away
whereas the other two are moving closer to
10:33.860 --> 10:42.800
the origin and while this happens as you can
see here we define this problem as the moving
10:42.800 --> 10:53.600
target traveling salesman problem and depending
on how they move we have this initial and
10:53.600 --> 11:00.750
the different positions as we have defined
here so this is the basic idea behind this
11:00.750 --> 11:06.240
moving target traveling salesman problem so
its a very difficult problem because it is
11:06.240 --> 11:13.649
an intractable problem it is non determinate
polynomial hard because the classical traveling
11:13.649 --> 11:19.089
salesman problem which is generally without
the moving target is a np complete problem
11:19.089 --> 11:26.209
whereas the classical tsp can be reduced to
a moving target traveling salesman problem
11:26.209 --> 11:30.410
tsp under this regime where it is a np
hard problems
11:30.410 --> 11:37.069
so by giving some velocity to each of them
we can get this so the non determinant polynomial
11:37.069 --> 11:44.259
complete set means that it is contained in
the in non determinant polynomial kind
11:44.259 --> 11:51.249
of principles and the decision version is
based on the tree path with time which is
11:51.249 --> 11:56.880
less than the time that it takes non deterministically
travel all the paths if one exists with time
11:56.880 --> 12:05.649
less than our time t return true else return
false so this is one option this is contained
12:05.649 --> 12:11.839
in both of them are contained in our the non
determinant polynomial version the other version
12:11.839 --> 12:17.870
is the optimization version which is the what
is the minimum time path minimum time path
12:17.870 --> 12:28.730
that is taken where the upper bound up time
with initial random path then binary search
12:28.730 --> 12:35.689
the range by testing t by two t by four etcetera
to find the optimal minimum time path so this
12:35.689 --> 12:43.079
is a np complete problem n to which we are
trying to see how the search is going to work
12:43.079 --> 12:50.279
or not so in the classical sense it is a very
difficult problem because whenever this
12:50.279 --> 12:59.350
is necessary it needs to be able to visit
each and every element of the path which means
12:59.350 --> 13:06.639
that each of these would take that many time
travel paths and thats why its a very a non
13:06.639 --> 13:12.360
determinate polynomial kind of a complete
path that is necessary to be taken classically
13:12.360 --> 13:20.550
in the quantum computing case however it is
possible to traverse every possible path why
13:20.550 --> 13:26.100
using some tricks of quantum computing that
will be shown and then once that is possible
13:26.100 --> 13:31.420
then we can have a search through all the
paths superposition to find the shortest route
13:31.420 --> 13:37.760
so this key element of superposition which
exist in the quantum computing way of looking
13:37.760 --> 13:44.790
into this problem enables to take advantage
of superposition of the different paths once
13:44.790 --> 13:52.360
they are all possible to be traversed his
was a problem which was initially out by
13:52.360 --> 14:00.050
rudolph by utilization of superposition of
cubic bipartite graph in linear time in
14:00.050 --> 14:05.179
terms of cubic means the all the nodes have
degree three bipartite means the the nodes
14:05.179 --> 14:13.120
are partitioned into two groups each node
is only adjacent to nodes in other group so
14:13.120 --> 14:22.089
this is the advantage of making this particular
approach where it was possible to come
14:22.089 --> 14:27.839
up with a cubic bipartite graph in linear
time by utilizing this principle so here is
14:27.839 --> 14:35.340
an example of this problem we take this same
condition of a bipartite cubic graph in which
14:35.340 --> 14:47.070
we will be using the four qubits such that
they are going to come in a set so that they
14:47.070 --> 14:53.639
can interact with the first part and then
can get superimposed into the two different
14:53.639 --> 15:00.550
sets one set is between one end two and one
end three and the other one would then be
15:00.550 --> 15:10.399
put up with the other two sets and so the
superposition grows as we have shown here
15:10.399 --> 15:17.929
now the potential problem in these cases is
that the extracting the hamiltonian path and
15:17.929 --> 15:24.459
the second problem would be finding the cycle
but not the path and the actual fact of these
15:24.459 --> 15:30.420
kind of a graph theoretical approach is that
only works for cubic graphs so in terms of
15:30.420 --> 15:37.709
solution to the first problem of extracting
the hamiltonian path only the paths containing
15:37.709 --> 15:43.410
all ones in the first register is the question
which we so in that case we can use the grovers
15:43.410 --> 15:49.439
algorithm so the first part where we are only
going to focus n only the ones in the first
15:49.439 --> 15:55.149
register we can utilize the grovers algorithm
for the second part we can use the black box
15:55.149 --> 16:04.869
for hamiltonian paths to solve for hamiltonians
cycles and that corresponds to the graph theoretic
16:04.869 --> 16:15.870
approach of hamiltonian paths and finally
for non cubic graphs we can make all nodes
16:15.870 --> 16:22.399
have the same degree where in the degree must
be a power of two and the algorithm when all
16:22.399 --> 16:28.920
nodes have degree two to the power i so in
step one we can give all nodes same degree
16:28.920 --> 16:39.600
of two x the graph g has n nodes we find the
nodes with the largest degree d and we find
16:39.600 --> 16:47.399
a value x where the node degree lies in between
the two possibilities so this is essentially
16:47.399 --> 16:55.690
how it looks we have situation which is
of this particular kind in this format where
16:55.690 --> 17:03.360
in we are making the groups of x nodes of
the path which can be then mapped into this
17:03.360 --> 17:14.829
set and we can try to find out how these nodes
can be contain within this set so we go through
17:14.829 --> 17:25.429
the graph g node by node and go through the
new nodes set by set and what we get is a
17:25.429 --> 17:37.840
set where we can put them together in this
kind of a path and link them by using this
17:37.840 --> 17:41.510
particular principle
17:41.510 --> 17:47.299
so the algorithm which requires this quantum
transition for nodes with two to the power
17:47.299 --> 17:53.390
x degree would be having of this format where
we have the control bit coming if it is all
17:53.390 --> 18:00.750
zeros then it essentially just as a mixing
of two states whereas if goes through the
18:00.750 --> 18:10.710
other sets then it will be going through this
particular set of operations so the first
18:10.710 --> 18:17.269
operation when the control bit comes it is
going through a hadamard so thats how the
18:17.269 --> 18:22.750
first hadamard works the next one essentially
takes another hadamard of the two and then
18:22.750 --> 18:32.820
we are putting in a control naught on top
of that so the final one is another set of
18:32.820 --> 18:42.029
the control naught and here we are then going
back to the set where we start the other control
18:42.029 --> 18:47.799
naught set and then finally we get to the
sets that we are interested in so here is
18:47.799 --> 18:53.730
the circuit that we get here it goes through
that many elements that we are going by and
18:53.730 --> 19:02.990
its in iterative a b c are the nodes adjacent
to the input a is the register keeping track
19:02.990 --> 19:10.539
of which nodes have been transversed and in
this way all the nodes are being covered
19:10.539 --> 19:17.620
once that is done the minimum is being found
by measuring the lengths register m we create
19:17.620 --> 19:24.580
a superposition again now we search for all
paths such that its less than m on an average
19:24.580 --> 19:30.290
we have to do this log of k times and k is
the number of items in the superposition so
19:30.290 --> 19:40.070
this is how it looks we go through iteration
one then in the second time make the flip
19:40.070 --> 19:47.399
and so the point about the average keeps on
moving and then finally we are able to go
19:47.399 --> 19:56.370
through this entire step so we can do this
on an average log of k times so that we can
19:56.370 --> 20:04.500
get the number of items in this super position
so what we have understood here is the
20:04.500 --> 20:09.110
same principle that we did at the very beginning
where we said that we started off with the
20:09.110 --> 20:18.120
idea of particles and electrons which have
quantum system have the properties of wave
20:18.120 --> 20:23.360
like the sound waves but when observed they
behave like particles like the bullets thats
20:23.360 --> 20:30.630
what we did so the algorithm works well for
all graphs it may double number of nodes but
20:30.630 --> 20:38.150
it takes order n steps when we search the
first register for all ones and the added
20:38.150 --> 20:44.320
nodes do not effect the solution so these
are the key observations for this operation
20:44.320 --> 20:51.230
now this can be extended to the overall traveling
salesman problem where we need another register
20:51.230 --> 20:57.850
large enough to hold the longest path and
at each step add a edge weight into the register
20:57.850 --> 21:04.240
all the paths of length n and their weights
would run an algorithm for hamiltonian cycles
21:04.240 --> 21:12.190
and we will looks for ones in the first register
superposition of all the hamiltonian cycles
21:12.190 --> 21:17.740
and then the grovers algorithm on some register
finds the minimum so now after having seen
21:17.740 --> 21:24.149
this how it works on regular tsp it can be
then extended to the moving target tsp in
21:24.149 --> 21:32.000
this moving target tsp each node has a velocity
we find the minimum weight a round trip for
21:32.000 --> 21:42.500
each of them so we add a time register track
the total time elapsed so far for each of
21:42.500 --> 21:50.200
these motions each step would calculate the
time to reach the next node as the motion
21:50.200 --> 21:58.250
occurs and the unknowns for us are the velocity
along this direction vx vy and the time so
21:58.250 --> 22:05.330
in order to determine the optimal path need
to add time to reach the next node to the
22:05.330 --> 22:12.870
total sum need to find the minimum which is
similar to the tsp problem that we just did
22:12.870 --> 22:21.690
before and we need we have an added time complexity
is which is linear the added time complexity
22:21.690 --> 22:28.750
in this case is linear because of the velocity
component so in summary what we have shown
22:28.750 --> 22:33.870
in this particular approach of rudolph is
that the have extended the hamiltonian path
22:33.870 --> 22:42.669
algorithm for cubic bi parted graphs for traveling
salesman problem and for moving target traveling
22:42.669 --> 22:49.820
salesman problem paths superposition can be
obtained in linear time the grover search
22:49.820 --> 22:55.740
algorithm works in square root of number of
objects in superposition and there are two
22:55.740 --> 23:01.480
to the power n different paths so the total
time is order two to the power n over two
23:01.480 --> 23:09.549
which is still in polynomial time and therefore
this has a benefit over the way how algorithms
23:09.549 --> 23:16.690
can be applied to non determinate polynomials
and their principles
23:16.690 --> 23:24.390
we will also look at another kind of problem
in this context which is related to traveling
23:24.390 --> 23:30.429
salesman problem in a slightly different way
but generally at this point this idea the
23:30.429 --> 23:36.549
fact that we can search an appropriate path
for the different trajectories which are involved
23:36.549 --> 23:43.840
in traveling salesman are very important for
making progress in terms of algorithm
23:43.840 --> 23:49.080
development as well as application of these
algorithm developments to problems which
23:49.080 --> 23:56.480
are quite difficult to be taken care in terms
of classical computing so all the non determinate
23:56.480 --> 24:02.809
polynomial problems have been targeted and
attempted through quantum computing by using
24:02.809 --> 24:09.190
these kinds of principles so may be if time
actually do one more of this kind of problem
24:09.190 --> 24:11.210
in the next class
24:11.210 --> 24:34.630
thank you