Pulsation of quantum walk on finite graph

Abstract

We study discrete-time quantum walks on weighted graphs, where every edge in an edge cut set is assigned a small weight $\epsilon>0$. The parameter $\epsilon$ represents the strength of the connections through the cut edges: as $\epsilon \to 0$, these connections vanish, and the graph decomposes into the connected components obtained by removing the cut edges. We refer to these weighted cut edges as {\it weak edges}. We show that, for sufficiently small $\epsilon$ and on the time scale $t=\Theta(\epsilon^{-1/2})$, the finding probabilities between the connected components are asymptotically described by a continuous-time wave equation on a reduced graph, whose vertices represent the connected components and whose edges represent the weak edges connecting them. The wave equation is governed by a symmetric weighted Laplacian determined by the reduced graph and the number of arcs contained in the components. Consequently, finding probabilities of leading-term are independent of the detailed internal structures of the components. We further show that this wave equation has the same form as Newton's equation of motion for a classical spring-mass system on the reduced graph.