Abstract
We propose a phenomenon of discrete-time quantum walks on graphs called the pulsation, which is a generalization of a phenomenon in the quantum searches. This phenomenon is discussed on a composite graph formed by two connected graphs G₁ and G₂. The pulsation means that the state periodically transfers between G₁ and G₂ with the initial state of the uniform superposition on G₁. In this paper, we focus on the case for the Grover walk where G₁ is the Johnson graph and G₂ is a star graph. Also, the composite graph is constructed by identifying an arbitrary vertex of the Johnson graph with the internal vertex of the star graph. In that case, we find the pulsation with O(√N^1+1/k) periodicity, where N is the number of vertices of the Johnson graph. The proof is based on Kato's perturbation theory in finite-dimensional vector spaces.