Spatial Search on Johnson Graphs by Continuous-Time Quantum Walk

DOI10.1007/S11128-022-03417-9MaRDI QIDQ6374482arXivFDO

Authors Hajime Tanaka, Mohamed Sabri, R. Portugal

Publication date 4 August 2021

Published in arXiv

Full work available at URL https://doi.org/10.1007/S11128-022-03417-9

Mathematics Subject Classification ID

Random walks on graphs (05C81) Quantum computation (81P68) Quantum mechanics on special spaces: manifolds, fractals, graphs, lattices (81Q35)

arXiv classification

cs.CCmath.COquant-ph

Abstract: Spatial search on graphs is one of the most important algorithmic applications of quantum walks. To show that a quantum-walk-based search is more efficient than a random-walk-based search is a difficult problem, which has been addressed in several ways. Usually, graph symmetries aid in the calculation of the algorithm's computational complexity, and Johnson graphs are an interesting class regarding symmetries because they are regular, Hamilton-connected, vertex- and distance-transitive. In this work, we show that spatial search on Johnson graphs by continuous-time quantum walk achieves the Grover lower bound $pisqrtN/2$ with success probability $1$ asymptotically for every fixed diameter, where $N$ is the number of vertices. The proof is mathematically rigorous and can be used for other graph classes.

This page was built for publication: Spatial Search on Johnson Graphs by Continuous-Time Quantum Walk

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