Discrete quantum walks on the symmetric group

Zlatko Dimcovic, Yevgeniy Kovchegov

Avah Banerjee

Heath Gerhardt, John Watrous

Wenjing Dai, Jiabin Yuan, Dan Li

Prithviraj Prabhu, Todd A. Brun

Classical random walks on finite graphs have an underrated property: a walk from any vertex can reach every other vertex in finite time, provided they are connected. Discrete-time quantum walks on finite connected graphs, however, can have infinite hitting times. This phenomenon is related to graph symmetry, as previously characterized by the group of direction-preserving graph automorphisms that trivially affect the coin Hilbert space. If a graph is symmetric enough (in a particular sense), then the associated quantum walk unitary will contain eigenvectors that do not overlap a set of target vertices for any coin-flip operator. These eigenvectors span the infinite-hitting-time (IHT) subspace. Quantum states in the IHT subspace never reach the target vertices, leading to infinite hitting times. However, this is not the whole story: the graph of the three-dimensional cube does not satisfy this symmetry constraint, yet quantum walks on this graph with certain symmetric coins can exhibit infinite hitting times. We study the effect of coin symmetry by analyzing the group of coin-permutation symmetries (CPSs): graph automorphisms that act nontrivially on the coin Hilbert space but leave the coin operator invariant. Unitaries using highly symmetric coins with large CPS groups, such as the permutation-invariant Grover coin, are associated with higher probabilities of never arriving, as a result of their larger IHT subspaces.

I. M. 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.