Quantum walk in symmetric Cayley graph over ${\mathbb{Z}}_2^n$

Abstract

We show that the hitting time of the discrete quantum walk on a symmetric Cayley graph over ${\mathbb{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 ${\mathbb{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.

References in corpus (2)

• Exponential algorithmic speedup by quantum walk
• Quantum Random Walks Hit Exponentially Faster