1305.6849 (Ilnur Khuziev)

Quantum walk in symmetric Cayley graph over $\Z_2^n$    [PDF]

Ilnur Khuziev

We show that the hitting time of the discrete quantum walk on a symmetric Cayley graph over $\Z_2^n $ from a vertex to its antipodal is polynomial in degree of the graph. We prove that returning time of quantum walk on a symmetric Cayley graph over $\Z_2^n $ is polynomial and the probability to hit is almost one. To prove it, we give a new estimation of Kravchuk coefficients. We give an example of a probabilistic polynomial algorithm that finds an antipodal vertex in symmetric Cayley graphs.

View original: http://arxiv.org/abs/1305.6849