Quantum walk search on Johnson graphs
Thomas G. Wong
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 .
arXiv:1601.04212•Journal of Physics A Mathematical and Theoretical•Apr 12, 2016•23 citations