Quantum walk search on Johnson graphs
Thomas G. Wong · Journal of Physics A Mathematical and Theoretical · 2016
The Johnson graph 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, is the complete graph K n , and 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 , 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 with fixed k .