Abstract:
The quantum walk search algorithm on the hypercube has been an
important milestone in the study of quantum walks. The algorithm can
be used to find the marked vertex of the hypercube, and solves the
problem in time proportional to the square root of the size of the
search space. The efficiency of this algorithm is only a constant
factor less than that of the Grover's search. The first part of the
talk is focussed on the efficiency of the hypercube search algorithm
subject to errors typical for an optical implementation. A universal
law for the dependence of efficiency is also presented. In the second
part, modifications that establish an equivalence with the Grover's
algorithm in terms of complexity is presented.
