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.

arXiv comment12 pages

References in corpus (19)

• Quantum Computation and Decision Trees
• Exponential algorithmic speedup by quantum walk
• Spatial search by quantum walk
• Continuous-Time Quantum Walks: Models for Coherent Transport on Complex Networks
• Distance-regular graphs
• Spatial search by quantum walk is optimal for almost all graphs
• Limit Theorem for Continuous-Time Quantum Walk on the Line
• Quantum walk approach to search on fractal structures
• Global Symmetry is Unnecessary for Fast Quantum Search
• Systematic Dimensionality Reduction for Quantum Walks: Optimal Spatial Search and Transport on Non-Regular Graphs
• A Quantum Algorithm for the Hamiltonian NAND Tree
• Continuous-Time Quantum Search on Balanced Trees
• Experimental realization of a momentum-space quantum walk
• Continuous-time quantum walks on dynamical percolation graphs
• Equivalence between discrete quantum walk models in arbitrary topologies
• Quantum Walk Search on Johnson 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