Optimal Quantum Walk Search on Kronecker Graphs with Dominant or Fixed Regular Initiators

Abstract

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.

arXiv comment11 pages, 4 figures

References in corpus (16)

• Emergence of scaling in random networks
• Hierarchical organization of modularity in metabolic networks
• Strengths and Weaknesses of Quantum Computing
• A Quantum Random Walk Search Algorithm
• Universal computation by quantum walk
• Spatial search by quantum walk
• Kronecker Graphs: An Approach to Modeling Networks
• Spatial search by quantum walk is optimal for almost all graphs
• Global Symmetry is Unnecessary for Fast Quantum Search
• Systematic Dimensionality Reduction for Quantum Walks: Optimal Spatial Search and Transport on Non-Regular Graphs
• Connectivity is a Poor Indicator of Fast Quantum Search
• Laplacian versus Adjacency Matrix in Quantum Walk Search
• Hamiltonian Oracles
• Spatial Search by Continuous-Time Quantum Walk with Multiple Marked Vertices
• Vertices cannot be hidden from quantum spatial search for almost all random graphs
• Quantum Walk Search on Kronecker Graphs

Cited by in corpus (4)

• On the optimality of spatial search by continuous-time quantum walk
• Impact of global and local interaction on quantum spatial search on chimera graph
• Application of graph theory in quantum computer science
• No Infinite Tail Beats Optimal Spatial Search