  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 goes to
infinity 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.

Quantum Physics