Quantum walk search on Kronecker graphs
Thomas G. Wong, K. Wünscher, Joshua Lockhart, Simone Severini · Physical Review A · 2018
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. 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.