Quantum walks on graphs embedded in orientable surfaces

A quantum walk model whose time evolution reflects the 2 -cell embedding on the orientable closed surface of a graph is introduced. We show that the scattering matrix is obtained by finding the faces on the underlying surface which have the overlap to the boundary, and the stationary state is obtained by counting two classes of the rooted spanning subgraphs of the dual graph on the underlying embedding.