Coined quantum walks lift the cospectrality of graphs and trees

In this paper we explore how a spectral technique suggested by coined quantum walks can be used to distinguish between graphs that are cospectral with respect to standard matrix representations. The algorithm runs in polynomial time and, moreover, can distinguish many graphs for which there is no subexponential time algorithm that is proven to be able to distinguish between them. In the paper, we give a description of the coined quantum walk from the field of quantum computing. The evolution of the walk is governed by a unitary matrix. We show how the spectrum of this matrix is related to the spectrum of the transition matrix of the classical random walk. However, despite this relationship the behaviour of the quantum walk is vastly different from the classical walk. This leads us to define a new matrix based on the amplitudes of paths of the walk whose spectrum we use to characterise graphs. We carry out three sets of experiments using this matrix representation. Firstly, we test the ability of the spectrum to distinguish between sets of graphs that are cospectral with respect to standard matrix representation. These include strongly regular graphs, and incidence graphs of balanced incomplete block designs (BIBDs). Secondly, we test our method on ALL regular graphs on up to 14 vertices and ALL trees on up to 24 vertices. This demonstrates that the problem of cospectrality is often encountered with conventional algorithms and tests the ability of our method to resolve this problem. Thirdly, we use distances obtained from the spectra of S+(U-3) to cluster graphs derived from real-world image data and these are qualitatively better than those obtained with the spectra of the adjacency matrix. Thus, we provide a spectral representation of graphs that can be used in place of standard spectral representations, far less prone to the problems of cospectrality. (C) 2008 Elsevier Ltd. All rights reserved.