Quantum Walk Search on Kronecker Graphs

DOI10.1103/PHYSREVA.98.012338arXiv1804.10560MaRDI QIDQ6300907FDOQ6300907

Thomas G. Wong, Joshua Lockhart, Konstantin Wünscher, Simone Severini

Publication date: 27 April 2018

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(sqrtN)$ time. Numerical simulations indicate that higher-order Kronecker graphs with the complete initiator also support optimal quantum search.

This page was built for publication: Quantum Walk Search on Kronecker Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6300907)