Finding structural anomalies in star graphs by quantum walks: A general approach

We develop a general theory for a quantum-walk search on a star graph. A star graph has $N$ edges each of which is attached to a central vertex. A graph $G$ is attached to one of these edges, and we would like to find out to which edge it is attached. This is done by means of a quantum walk, a quantum version of a random walk. This walk contains $O(\sqrt{N})$ steps, which represents a speedup over a classical search, which would require $O(N)$ steps. The overall graph, star plus $G$, is divided into two parts, and we find that for a quantum speedup to occur, the eigenvalues associated with these two parts in the $N\rightarrow\infty$ limit must be the same. Our theory tells us how the initial state of the walk should be chosen, and how many steps the walk must make in order to find $G$.