  We consider a spectral analysis on the quantum walks on graph $G=(V,E)$ with
the local coin operators $\{C_u\}_{u\in V}$ and the flip flop shift. The
quantum coin operators have commonly two distinct eigenvalues $\kappa,\kappa'$
and $p=\dim(\ker(\kappa-C_u))$ for any $u\in V$ with $1\leq p\leq \delta(G)$,
where $\delta(G)$ is the minimum degrees of $G$. We show that this quantum walk
can be decomposed into a cellular automaton on $\ell^2(V;\mathbb{C}^p)$ whose
time evolution is described by a self adjoint operator $T$ and its remainder.
We obtain how the eigenvalues and its eigenspace of $T$ are lifted up to as
those of the original quantum walk. As an application, we express the
eigenpolynomial of the Grover walk on $\mathbb{Z}^d$ with the moving shift in
the Fourier space.
