Finding structural anomalies in star graphs using quantum walks.
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→∞ 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.
Courant Institute of Mathematical Sciences, New York University, 251 Mercer Street, New York, New York 10012, USA.
Seth
S
Cottrell
Department of Physics, Hunter College of the City University of New York, 695 Park Avenue, New York, New York 10065, USA.
Mark
M
Hillery