Quantum walk-based search and symmetries in graphs
Anuradha Mahasinghe, Jingbo B. Wang, J.K. Wijerathna · Journal of Physics A Mathematical and Theoretical · 2014
© 2014 IOP Publishing Ltd. In this paper we present a lemma, which helps us to establish a link between the distribution of success probabilities from quantum walk based search and the symmetries of the underlying graphs. With the aid of the lemma, we identified certain graph structures of which the quantum walk based search provides high success probabilities at the marked vertices. We also observed that many graph structures and their vertices can be classified according to their structural equivalence using the search probabilities provided by quantum walks, although this method cannot resolve all non-equivalent vertices for strongly regular graphs.