Quantum Walk Search on Johnson Graphs

Abstract

The Johnson graph $J(n,k)$ is defined by $n$ symbols, where vertices are $k$-element subsets of the symbols, and vertices are adjacent if they differ in exactly one symbol. In particular, $J(n,1)$ is the complete graph $K_n$, and $J(n,2)$ is the strongly regular triangular graph $T_n$, both of which are known to support fast spatial search by continuous-time quantum walk. In this paper, we prove that $J(n,3)$, which is the $n$-tetrahedral graph, also supports fast search. In the process, we show that a change of basis is needed for degenerate perturbation theory to accurately describe the dynamics. This method can also be applied to general Johnson graphs $J(n,k)$ with fixed $k$.

17 pages, 9 figures

References in corpus (6)

• Spatial search by quantum walk
• Graph Isomorphism in Quasipolynomial Time
• Connectivity is a Poor Indicator of Fast Quantum Search
• Laplacian versus Adjacency Matrix in Quantum Walk Search
• Hamiltonian Oracles
• Diagrammatic Approach to Quantum Search

Cited by in corpus (14)

• On the optimality of spatial search by continuous-time quantum walk
• Equivalence of Szegedy's and Coined Quantum Walks
• Finding a marked node on any graph by continuous-time quantum walk
• Spatial Search on Johnson Graphs by Continuous-Time Quantum Walk
• Search on Vertex-Transitive Graphs by Lackadaisical Quantum Walk
• Analog quantum algorithms for the mixing of Markov chains
• Feedback-assisted quantum search by continuous-time quantum walks
• Deterministic spatial search using alternating quantum walks
• Quantum Walk Search on Kronecker Graphs
• Engineering the Success of Quantum Walk Search Using Weighted Graphs
• Role of symmetry in quantum search via continuous-time quantum walk
• A framework for optimal quantum spatial search using alternating phase-walks
• Multimarked Spatial Search by Continuous-Time Quantum Walk
• No Infinite Tail Beats Optimal Spatial Search