Spatial Search on Johnson Graphs by Continuous-Time Quantum Walk

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 $\pi \sqrt{N}/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.

12 pages

References in corpus (7)

• Exponential algorithmic speedup by quantum walk
• Spatial search by quantum walk
• A Quantum Algorithm for the Hamiltonian NAND Tree
• Continuous-time quantum walks on dynamical percolation graphs
• Continuous-time quantum walk spatial search on the Bollobás scale-free network
• Transport efficiency of continuous-time quantum walks on graphs
• Quantum search with a continuous-time quantum walk in momentum space

Cited by in corpus (8)

• Spatial Search on Johnson Graphs by Discrete-Time Quantum Walk
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids
• Walking on Vertices and Edges by Continuous-Time Quantum Walk
• Unifying quantum spatial search, state transfer and uniform sampling on graphs: simple and exact
• Multimarked Spatial Search by Continuous-Time Quantum Walk
• Scoring Anomalous Vertices Through Quantum Walks
• Quantum search by continuous-time quantum walk on t-designs
• No Infinite Tail Beats Optimal Spatial Search