QC238 : Study of Quantum Walks search Algorithms
Thesis > Central Library of Shahrood University > Physics > MSc > 2014
Authors:
Abstarct: The issue of searching was always one of the most important problems in different
areas of science. searching an unstructured set of N items requires O(N) queries in
the worst case. In the quantum domain, however, Grover’s algorithm can perform
unstructured search by making only O(√N ) queries, a quadratic speedup over the
classical case .Quantum walk is quantum counterpart of classical Random walk
which has a different behavior due to the quantum phenomena such as quantum
interference, entanglement and superposition. One of the most important applica
tions of quantum walks is in quantum algorithms designs. we organize our thesis
as follows: first of all, we make a short review of classical and quantum walks.
We compare the probability distribution and standard deviation of CRW and QW
and show that standard deviation in QW is quadratic while classical one is linear
which is the most important difference of these two types of walk.. Following the
first chapter we express other differences between these two types of walks and
introduce an analytical approach to find quantum probability distribution. Also
we mentioned one dimensional quantum walk with generalized coin and quantum
walk of higher dimensions. In second chapter one can study a brief review on sev
eral quantum algorithms, Grover search algorithm in details and proving that how
the algorithm leads in quadratic speedup. In chapter three we deal with search
algorithm on a hypercube lattice using coined walk and introduce an approach
for optimizing the algorithm. In continue we introduce a new walk with discrete
evolution, namely scattering walk in which the quantum particle (walker) takes
place on the edges of a graph and the graph vertices act as scattering centers.
The evolution operator and state of system after certain number of steps for this
type of walk and a unitary equivalence between discrete models has been studied.
We show that by using an appropriate initial state and certain number of steps,
this type of walk can find a structural anomaly in a graph more efficiently than
a classical search can. Then we provide a general approach in star graphs which
have high symmetries and show that it is possible to find the target item within a
better time interval than classical mode through reducing Hilbert space.
Keywords: