Optimal Quantum Walk Search on Kronecker Graphs with Dominant or Fixed Regular Initiators. (arXiv:1809.01249v2 [quant-ph] UPDATED)

In network science, graphs obtained by taking the Kronecker or tensor power
of the adjacency matrix of an initiator graph are used to construct complex
networks. In this paper, we analytically prove sufficient conditions under
which such Kronecker graphs can be searched by a continuous-time quantum walk
in optimal $\Theta(\sqrt{N})$ time. First, if the initiator is regular and its
adjacency matrix has a dominant principal eigenvalue, meaning its unique
largest eigenvalue asymptotically dominates the other eigenvalues in magnitude,
then the Kronecker graphs generated by this initiator can be quantum searched
with probability 1 in $\pi\sqrt{N}/2$ time, asymptotically, and we give the
critical jumping rate of the walk that enables this. Second, for any fixed
initiator that is regular, non-bipartite, and connected, the Kronecker graphs
generated by it are quantum searched in $\Theta(\sqrt{N})$ time. This greatly
extends the number of Kronecker graphs on which quantum walks are known to
optimally search. If the fixed, regular, connected initiator is bipartite,
however, then search on its Kronecker powers is not optimal, but is still
better than classical computer's $O(N)$ runtime if the initiator has more than
two vertices.

Article web page: