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

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.

No reviews yet.

No comments yet.