we have been summarizing all the aspects of quantum computing implementations that we
have been dealing with in this course in this week what we are now trying to do is trying
to see how all the different aspects that we have discussed in this course as a part
of implementation how does it work in conjunction to make sure that quantum computing becomes
a viability it is an interdisciplinary field so it takes a lot of different areas and therefore
we are spending this last week in a lot of detailed discussions of the different aspects
of subjects that we have covered
so in this lecture we will be looking into the digital verses quantum computing aspects
from the principle of looking at the traveling salesman problem what we have learned until
now is the digital computing produces serial results on the other hand quantum is truly
concurrent or parallel digital computers need an exponential amount of resources to accomplish
a task which can become polynomial in the quantum sense thats because quantum computers
perform two to the power n computations where n is the number of qubits so these are the
basic advantages we have taken when we went from digital to quantum so some of the very
simple examples of the quantum nature has been told in terms of very basics of interference
for example the two slit experiment where if it is a classical case then for a single
slit the bullets will only come from one of the two places where the holes are on the
other hand when both of them are simultaneously present then it produces interference for
example take a look at a wave for example the sound waves their behavior is something
which is very different from when only particles have being considered classical particles
so to appreciate this let me show this once more
so bullets are classical particles let us consider the case where we are going to have
two slits going on to a detector but for understanding this let us start with one slit so when we
have bullets passes through one here is the distribution on the other hand if we have
the bullet on the going through the other slit there is the distribution only one of
them are open if both of them are open then what will happen is will get a total distribution
which is of this kind so one two and this one is one plus two on the other hand when
we do sound waves let say then if we have the similar situation of one slit or the other
slit the initial idea of having one each is fine but when we have both the slits open
they dont simply show the addition that we just showed you for the bullets instead it
shows an oscillating pattern which is the superposition which is distinct from the individuals
that we talked about so that is the wave part or the interference nature of this so this
same thing extend to the electrons and just going to show this for completeness and so
we know that electrons essentially although they are particles may be a light wave but
when we are observing electrons then we do see them as bullets
so they be a waste particles so that is the dilemma with quantum mechanics which is what
we are working on when we go to fundamental particles which are quantum then they have
both the properties when we observe them that is when we make that classical then they behave
exactly like a particle analogues to the bullets that we talked about but many of their other
phenomena behave like wave like which is what when we talked about the sound wave so that
is all the principles of quantum mechanics just summarized here so in terms of quantum
computation we have been utilizing the concept of superposition both zero and one and the
qubit representation has been in terms of the number of wave functions that we are using
so the superposition of states for instance would essentially have a concept of amplitude
square of which leads to probability these are all the concepts that we have taken as
a result a summation of all the square of the amplitudes for the states would always
be equal to one in order to make the probability loss to be sustained so we have been using
these kinds of states entangled states superposition states and we have been representing them
either in vector term or in the matrix term and whenever we want to change them we talk
in terms of unitary transformations which are essentially unitary matrices whose conjugate
transpose is the inverse
essentially ensuring their harmitian nature of the system is preserved so we have shown
many a times hadamard transforms where we can go from a particular pure state to a mix
state for instance we also have talked about other simpler gates for example the c naught
gate the not gate c naught is the two qubit gate not gate can be single qubit gate and
so on and so forth there are visual representations which essentially tell us about the circuits
the wires the representation of the gates and how they interact the hadamard c naught
and so on and so forth in order to do something more interesting we would like to use one
of the algorithms which help us in getting forward with ideas of computation and one
of the major once as we have discussed is the grovers search algorithm which is in polynomial
time whereas the one in shors algorithm is in exponential time however the grovers algorithm
has the advantage of wider applicability because it is looking for research
so its analogy is always given with respect to searching in unsorted set of data for example
a phone book to find a specific number without rearranging so the idea always have been to
magnify the amplitude of the chosen number and always we use the concept that there is
an oracle which knows the solution so you flip the amplitudes of the selected items
and rotate all the amplitudes around the average and repeat this until the selected items probability
of being red is greater than half so that it can be observed so in terms of graphical
representation this is what we have done earlier at once we get a marked system basically can
go through the flip and then average them and then flip all the amplitudes around the
average to get the mark state amplified
the time complexity as i mentioned its in terms of square root of n whereas in terms
of a normal classical surge the minimum number on an average that you require is an n by
two so there is a large in hands men when we go to grovers algorithm now we would like
to actually extend this problem to the traveling salesmen problem thats because the principle
of a traveling salesmen problem is that they require going through the different paths
with different levels and the difficulty is that its not possible to go through the
search in this particular case in a simple polynomial structure as it is possible for
a classical computer so here is an example of a traveling salesman problem where the
a b c d e are the vertices or the points into which these traveling salesman is suppose
to go that individual can take different paths and thats roughly the basic idea behind this
problem to start with and they can have different weightage factors depending on how many times
a particular path is being traveled verses the other
so here is an example of a path which is being shown here where this particular path route
can be taken to go to all the five points that we have discussed so this is sort of
like a moving target traveling salesman that we just discussed that the target itself is
moving so that you can do a traveling salesman moving target point to be problem so we have
this origin from where it starts and we have the particles or the points move with respect
to the origin so these two are moving away whereas the other two are moving closer to
the origin and while this happens as you can see here we define this problem as the moving
target traveling salesman problem and depending on how they move we have this initial and
the different positions as we have defined here so this is the basic idea behind this
moving target traveling salesman problem so its a very difficult problem because it is
an intractable problem it is non determinate polynomial hard because the classical traveling
salesman problem which is generally without the moving target is a np complete problem
whereas the classical tsp can be reduced to a moving target traveling salesman problem
tsp under this regime where it is a np hard problems
so by giving some velocity to each of them we can get this so the non determinant polynomial
complete set means that it is contained in the in non determinant polynomial kind
of principles and the decision version is based on the tree path with time which is
less than the time that it takes non deterministically travel all the paths if one exists with time
less than our time t return true else return false so this is one option this is contained
in both of them are contained in our the non determinant polynomial version the other version
is the optimization version which is the what is the minimum time path minimum time path
that is taken where the upper bound up time with initial random path then binary search
the range by testing t by two t by four etcetera to find the optimal minimum time path so this
is a np complete problem n to which we are trying to see how the search is going to work
or not so in the classical sense it is a very difficult problem because whenever this
is necessary it needs to be able to visit each and every element of the path which means
that each of these would take that many time travel paths and thats why its a very a non
determinate polynomial kind of a complete path that is necessary to be taken classically
in the quantum computing case however it is possible to traverse every possible path why
using some tricks of quantum computing that will be shown and then once that is possible
then we can have a search through all the paths superposition to find the shortest route
so this key element of superposition which exist in the quantum computing way of looking
into this problem enables to take advantage of superposition of the different paths once
they are all possible to be traversed his was a problem which was initially out by
rudolph by utilization of superposition of cubic bipartite graph in linear time in
terms of cubic means the all the nodes have degree three bipartite means the the nodes
are partitioned into two groups each node is only adjacent to nodes in other group so
this is the advantage of making this particular approach where it was possible to come
up with a cubic bipartite graph in linear time by utilizing this principle so here is
an example of this problem we take this same condition of a bipartite cubic graph in which
we will be using the four qubits such that they are going to come in a set so that they
can interact with the first part and then can get superimposed into the two different
sets one set is between one end two and one end three and the other one would then be
put up with the other two sets and so the superposition grows as we have shown here
now the potential problem in these cases is that the extracting the hamiltonian path and
the second problem would be finding the cycle but not the path and the actual fact of these
kind of a graph theoretical approach is that only works for cubic graphs so in terms of
solution to the first problem of extracting the hamiltonian path only the paths containing
all ones in the first register is the question which we so in that case we can use the grovers
algorithm so the first part where we are only going to focus n only the ones in the first
register we can utilize the grovers algorithm for the second part we can use the black box
for hamiltonian paths to solve for hamiltonians cycles and that corresponds to the graph theoretic
approach of hamiltonian paths and finally for non cubic graphs we can make all nodes
have the same degree where in the degree must be a power of two and the algorithm when all
nodes have degree two to the power i so in step one we can give all nodes same degree
of two x the graph g has n nodes we find the nodes with the largest degree d and we find
a value x where the node degree lies in between the two possibilities so this is essentially
how it looks we have situation which is of this particular kind in this format where
in we are making the groups of x nodes of the path which can be then mapped into this
set and we can try to find out how these nodes can be contain within this set so we go through
the graph g node by node and go through the new nodes set by set and what we get is a
set where we can put them together in this kind of a path and link them by using this
particular principle
so the algorithm which requires this quantum transition for nodes with two to the power
x degree would be having of this format where we have the control bit coming if it is all
zeros then it essentially just as a mixing of two states whereas if goes through the
other sets then it will be going through this particular set of operations so the first
operation when the control bit comes it is going through a hadamard so thats how the
first hadamard works the next one essentially takes another hadamard of the two and then
we are putting in a control naught on top of that so the final one is another set of
the control naught and here we are then going back to the set where we start the other control
naught set and then finally we get to the sets that we are interested in so here is
the circuit that we get here it goes through that many elements that we are going by and
its in iterative a b c are the nodes adjacent to the input a is the register keeping track
of which nodes have been transversed and in this way all the nodes are being covered
once that is done the minimum is being found by measuring the lengths register m we create
a superposition again now we search for all paths such that its less than m on an average
we have to do this log of k times and k is the number of items in the superposition so
this is how it looks we go through iteration one then in the second time make the flip
and so the point about the average keeps on moving and then finally we are able to go
through this entire step so we can do this on an average log of k times so that we can
get the number of items in this super position so what we have understood here is the
same principle that we did at the very beginning where we said that we started off with the
idea of particles and electrons which have quantum system have the properties of wave
like the sound waves but when observed they behave like particles like the bullets thats
what we did so the algorithm works well for all graphs it may double number of nodes but
it takes order n steps when we search the first register for all ones and the added
nodes do not effect the solution so these are the key observations for this operation
now this can be extended to the overall traveling salesman problem where we need another register
large enough to hold the longest path and at each step add a edge weight into the register
all the paths of length n and their weights would run an algorithm for hamiltonian cycles
and we will looks for ones in the first register superposition of all the hamiltonian cycles
and then the grovers algorithm on some register finds the minimum so now after having seen
this how it works on regular tsp it can be then extended to the moving target tsp in
this moving target tsp each node has a velocity we find the minimum weight a round trip for
each of them so we add a time register track the total time elapsed so far for each of
these motions each step would calculate the time to reach the next node as the motion
occurs and the unknowns for us are the velocity along this direction vx vy and the time so
in order to determine the optimal path need to add time to reach the next node to the
total sum need to find the minimum which is similar to the tsp problem that we just did
before and we need we have an added time complexity is which is linear the added time complexity
in this case is linear because of the velocity component so in summary what we have shown
in this particular approach of rudolph is that the have extended the hamiltonian path
algorithm for cubic bi parted graphs for traveling salesman problem and for moving target traveling
salesman problem paths superposition can be obtained in linear time the grover search
algorithm works in square root of number of objects in superposition and there are two
to the power n different paths so the total time is order two to the power n over two
which is still in polynomial time and therefore this has a benefit over the way how algorithms
can be applied to non determinate polynomials and their principles
we will also look at another kind of problem in this context which is related to traveling
salesman problem in a slightly different way but generally at this point this idea the
fact that we can search an appropriate path for the different trajectories which are involved
in traveling salesman are very important for making progress in terms of algorithm
development as well as application of these algorithm developments to problems which
are quite difficult to be taken care in terms of classical computing so all the non determinate
polynomial problems have been targeted and attempted through quantum computing by using
these kinds of principles so may be if time actually do one more of this kind of problem
in the next class
thank you