Quantum Walk Search on Kronecker Graphs

Abstract

Kronecker graphs, obtained by repeatedly performing the Kronecker product of the adjacency matrix of an "initiator" graph with itself, have risen in popularity in network science due to their ability to generate complex networks with real-world properties. In this paper, we explore spatial search by continuous-time quantum walk on Kronecker graphs. Specifically, we give analytical proofs for quantum search on first-, second-, and third-order Kronecker graphs with the complete graph as the initiator, showing that search takes Grover's $O(\sqrt{N})$ time. Numerical simulations indicate that higher-order Kronecker graphs with the complete initiator also support optimal quantum search.

arXiv comment10 pages, 8 figures

References in corpus (12)

• Emergence of scaling in random networks
• Quantum random walks - an introductory overview
• Spatial search by quantum walk
• Kronecker Graphs: An Approach to Modeling Networks
• From quantum cellular automata to quantum lattice gases
• Spatial search by quantum walk is optimal for almost all graphs
• On the absence of homogeneous scalar unitary cellular automata
• Grover Search with Lackadaisical Quantum Walks
• Global Symmetry is Unnecessary for Fast Quantum Search
• Connectivity is a Poor Indicator of Fast Quantum Search
• Quantum Walk Search on Johnson Graphs
• Diagrammatic Approach to Quantum Search

Cited by in corpus (8)

• Quadratic speedup for spatial search by continuous-time quantum walk
• On the optimality of spatial search by continuous-time quantum walk
• Feedback-assisted quantum search by continuous-time quantum walks
• Ion Trap Long-Range XY Model for Quantum State Transfer and Optimal Spatial Search
• Spatial search by continuous-time quantum walks on renormalized Internet networks
• Optimal Quantum Walk Search on Kronecker Graphs with Dominant or Fixed Regular Initiators
• Optimal spatial searches with long-range tunneling
• Optimal quantum spatial search with one-dimensional long-range interactions