Discrete-time quantum walk search on Johnson graphs

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, both J (n, 1), the complete graph K_n, and J (n, 2), the strongly regular triangular graph T_n, support fast quantum spatial search. Wong showed that continuous-time quantum walk search on J (n, 3) also supports fast search. The problem is reconsidered in the language of scattering quantum walk, a type of discrete-time quantum walk. Here the search space is confined to a low-dimensional subspace corresponding to the collapsed graph. Using matrix perturbation theory, we show that discrete-time quantum walk search on J (n, 3) also achieves full quantum speedup. The analytical method can also be applied to general Johnson graphs J (n, k) with fixed k.