Quantum Walk Search on Johnson Graphs

الأصل · EN

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ₙ, and J(n,2) is the strongly regular triangular graph Tₙ, 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.