Spectral mapping theorem of an abstract quantum walk

Abstract

Given two Hilbert spaces, $\mathcal {H}$ and $\mathcal {K}$, we introduce an abstract unitary operator U on $\mathcal {H}$ and its discriminant T on $\mathcal {K}$ induced by a coisometry from $\mathcal {H}$ to $\mathcal {K}$ and a unitary involution on $\mathcal {H}$. In a particular case, these operators U and T become the evolution operator of the Szegedy walk on a graph, possibly infinite, and the transition probability operator thereon. We show the spectral mapping theorem between U and T via the Joukowsky transform. Using this result, we have completely determined the spectrum of the Grover walk on the Sierpiński lattice, which is pure point and has a Cantor-like structure.

1 Introduction

Quantum walks, whose primitive form appeared in [7] and [12], attracted the attention of many researchers at the beginning of the century because of their efficiencies of the quantum speedup of search algorithm on some graphs (see [1] and its references.). Szegedy [28] introduced an inclusive class of quantum walks partially including previous quantum walk models [2, 3, 25]. One of the interesting aspects of this class is that the spectral analysis of a quantum walk is reduced to that of an underlying reversible random walk on the same graph by a spectral mapping theorem. This theorem is quite useful not only in estimating the efficiency of algorithms based on the quantum walk [11, 25, 28] but also in characterizing its stochastic long-time behavior [19, 21].

Recently, an extended version of the walk, the twisted Szegedy walk, was introduced in [14]. Let $G=(V,D)$ be a symmetric digraph with vertices V and arcs D, i.e., an arc $e \in D$ if and only if the inverse $\bar{e} \in D$. The time evolution $U^{(w,\theta )}$ of the twisted Szegedy walk on G is a unitary operator on $\ell ^2(D)$ defined by

$$\begin{aligned} U^{(w,\theta )} = S^{(\theta )}C^{(w)} \quad \text{ with }\ C^{(w)} = 2 d_A^{*} d_A - 1. \end{aligned}$$

Here $S^{(\theta )}$ is called a shift operator and is a unitary involution defined from a 1-form $\theta :D \rightarrow \mathbb {C}$. $C^{(w)}$ is a coin operator and $d_A:\ell ^2(D) \rightarrow \ell (V)$ is a boundary operator, which is a coisometry defined from a weight $w:D \rightarrow \mathbb {C}$. For a particular choice of $\theta$ and w, $U^{(w,\theta )}$ becomes the evolution $U_G$ of the Grover walk on G, which is one of the most intensively studied model of quantum walks on graphs (see [1, 13, 30] and the references therein). The discriminant $T^{(w, \theta )}= d_A S^{(\theta )} d_A^{*}$ is a self-adjoint operator on $\ell ^{2}(V)$. In the case of the Grover walk on G, the discriminant of $U_G$ is unitarily equivalent to the transition probability operator $P_G$ of the symmetric random walk on G, in which a walker on a vertex moves to a neighbor vertex with isotropic probability. In [14] the following spectral mapping theorem by the Joukowsky transform $\varphi (x)=(x+x^{-1})/2$ was obtained for finite graphs, i.e., $|V|, |D| < \infty$:

$$\begin{aligned} \sigma _\mathrm{p}(U^{(w,\theta )})= \varphi ^{-1}(\sigma _\mathrm{p}(T^{(w,\theta )})) \cup \{1 \}^{M_+} \cup \{-1\}^{M_-}, \end{aligned}$$

(1.1)

where $M_\pm = {\dim } \ker (d_A) \cap \ker (S^{(\theta )} \pm 1)$ and $\sigma _\mathrm{p}(\cdot )$ denotes the set of all eigenvalues. In the expression above, $\{\pm 1\}^{M_{\pm }}$ implies the set of eigenvalue $\pm \,1$ of multiplicity $M_{\pm }$, respectively; we assume $\{\pm 1\}^{M_\pm }=\emptyset$ if $M_{\pm }=0$. (1.1) is also applicable to the spectral analysis of the evolution of the Grover walk on a crystal lattice G, i.e., there exists a finitely generated abelian group $\Gamma$ of automorphisms acting freely on G such that $\Gamma \backslash G$ is a finite graph (see [14, Sec. 3.1] for the precise definition of the crystal lattice). We use $\sigma (\cdot )$ to denote the spectrum. In [14, Corollary 1], the following were obtained for the crystal lattice G:

$$\begin{aligned}&\sigma (U_G)= \varphi ^{-1}(\sigma (P_G)) \cup \{1\}^{M_+} \cup \{-1\}^{M_-}, \end{aligned}$$

(1.2)

$$\begin{aligned}&\sigma _\mathrm{p}(U_G)= \varphi ^{-1}(\sigma _\mathrm{p}(P_G)) \cup \{1\}^{M_+} \cup \{-1\}^{M_-}. \end{aligned}$$

(1.3)

In this paper, we extend the above spectral mappings (1.2), and (1.3) for crystal lattices to that for general infinite graphs. For the spectral measure $E_u$ on $[0,2\pi ]$ of a unitary operator u on a Hilbert space $\mathfrak {h}$ and $\psi \in \mathfrak {h}$, $\mu _\psi$ denotes a Borel measure $\Vert E_u(\cdot )\psi \Vert _{\mathfrak {h}}^2$ on $[0,2\pi ]$. Lebesgue’s decomposition theorem says that $\mu _\psi$ can be decomposed into $\mu _\psi = \mu _{\psi , \mathrm{p}} + \mu _{\psi , \mathrm{ac}} + \mu _{\psi , \mathrm{sc}}$, where $\mu _{\psi , \mathrm{p}}$ is pure point, $\mu _{\psi , \mathrm{ac}}$ is absolutely continuous with respect to Lebesgue measure, and $\mu _{\psi , \mathrm{sc}}$ is continuous and singular with respect to Lebesgue measure. Let $\mathcal {H}_{\sharp } = \{ \psi \in \mathfrak {h} \mid \mu _\psi = \mu _{\psi , {\sharp }} \}$ ($\sharp =$ ac, sc) and $\mathcal {H}_\mathrm{c} =\mathcal {H}_\mathrm{ac} \oplus \mathcal {H}_\mathrm{sc}$. The continuous, absolutely continuous, and singular continuous spectrum of u are defined as $\sigma _\mathrm{c}(u) = \sigma ( u \mid _{\mathcal {H}_\mathrm{c}})$, $\sigma _\mathrm{ac}(u) = \sigma ( u \mid _{\mathcal {H}_\mathrm{ac}})$, and $\sigma _\mathrm{sc}(u) = \sigma ( u \mid _{\mathcal {H}_\mathrm{sc}})$, respectively. It is well known that $\sigma (u) = \overline{\sigma _\mathrm{p}(u)} \cup \sigma _\mathrm{ac}(u) \cup \sigma _\mathrm{sc}(u)$. In a way similar to the above, we can define $\sigma _\sharp (a)$ ($\sharp =$ c, ac, sc) for a self-adjoint operator a.

Theorem 1.1

Let G be an infinite graph (connected and locally finite). Then

$$\begin{aligned}&\sigma (U_G)= \varphi ^{-1}(\sigma (P_G)) \cup \{1\}^{M_+} \cup \{-1\}^{M_-}, \\&\sigma _\mathrm{p}(U_G)= \varphi ^{-1}(\sigma _\mathrm{p}(P_G)) \cup \{1\}^{M_+} \cup \{-1\}^{M_-}, \\&\sigma _{\sharp }(U_G) = \varphi ^{-1}(\sigma _{\sharp }(P_G)) \quad \text{ for }\ \sharp = \mathrm{c}, \mathrm{ac}, \mathrm{sc}. \end{aligned}$$

To prove Theorem 1.1, once we discard the graph structure, consider two arbitrary Hilbert spaces $\mathcal {H}$ and $\mathcal {K}$, and define an abstractive unitary operator U on $\mathcal {H}$ as

$$\begin{aligned} U=S(2d_A^{*}d_A-1). \end{aligned}$$

(1.4)

We suppose that:

• (1) S is a unitary involution on $\mathcal {H}$;

• (2) $d_A$ is a coisometry from $\mathcal {H}$ to $\mathcal {K}$.

Then, we obtain the spectral mapping theorem between U and the discriminant $T=d_A S d_A^{*}$ of U, which is a self-adjoint contraction operator on $\mathcal {K}$. Let $M_\pm = \mathrm{dim}\ker (d_A) \cap \ker (S\pm 1)$.

Theorem 1.2

Let U and T be as above. Then,

$$\begin{aligned} \sigma (U)&= \varphi ^{-1}(\sigma (T)) \cup \{1\}^{M_+} \cup \{-1\}^{M_-}, \end{aligned}$$

(1.5)

$$\begin{aligned} \sigma _\mathrm{p}(U)&= \varphi ^{-1}(\sigma _\mathrm{p}(T)) \cup \{1\}^{M_+} \cup \{-1\}^{M_-}. \end{aligned}$$

(1.6)

Moreover, for all $\lambda \in \sigma _\mathrm{p}(U)$,

$$\begin{aligned} \mathrm{dim}\ker (U-\lambda ) = {\left\{ \begin{array}{ll} \mathrm{dim}\ker (T-\varphi (\lambda )), &{} \lambda \not = \pm 1 \\ \mathrm{dim}\ker (T \mp 1) + M_\pm , &{} \lambda = \pm 1. \end{array}\right. } \end{aligned}$$

In a companion paper [24], we construct the generator of U under the conditions (1) and (2). As a by-product [24, Theorem 4.1 and Corollary 4.3], the continuous part of U is unitarily equivalent to the continuous part of $\mathrm{exp}(i \arccos T) \oplus \mathrm{exp}(-i \arccos T)$. Combining this with Theorem 1.2 yields the following corollary.

Corollary 1.3

Let U and T be as above. Then

$$\begin{aligned} \sigma _\sharp (U) = \varphi ^{-1}(\sigma _\sharp (T)) \quad \text{ for }\ \sharp = \mathrm{c}, \mathrm{ac}, \mathrm{sc}. \end{aligned}$$

As long as the conditions (1) and (2) are satisfied, Theorem 1.2 and Corollary 1.3 ensure that the spectral mapping theorem holds not only for the Szegedy walks on finite graphs but also for that on general infinite graphs. In particular, Theorem 1.1 is proved. We emphasize that the spectral mapping theorem holds even for arbitrary unitary operators of the form (1.4). An example which is not directly concerned with a graph is given in Sect. 3.

In the rest of this section, we go back to the graph world and give some interesting examples of the Grover walks on infinite graphs G. As mentioned, the discriminant of the Grover evolution $U_G$ is unitarily equivalent to the transition probability operator $P_G$. See Example 3.1 for the details of the graph setting.

First we see that Theorem 1.2 recovers some result in [14] for a crystal lattice G such as the d-dimensional lattice $\mathbb {Z}^{d}$, the hexagonal, the triangular, and the Kagome ones. Detailed spectral structures, including the multiplicities of eigenvalues $\pm \,1$, are described in terms of geometric properties of graphs, which can be seen in [14]. The continuous spectrum of $U_G$ is obtained by Corollary 1.3. $P_G$ does not have any singular continuous spectrum on the crystal lattice ([10, 15]), then neither does $U_{G}$.

Example 1.1

[14] Let G be a crystal lattice. Then

$$\begin{aligned}&\sigma (U_G)= \varphi ^{-1}(\sigma (P_G)) \cup \{1\}^{M_+} \cup \{-1\}^{M_-}, \\&\sigma _\mathrm{p}(U_G)= \varphi ^{-1}(\sigma _\mathrm{p}(P_G)) \cup \{1\}^{M_+} \cup \{-1\}^{M_-}, \\&\sigma _\mathrm{ac}(U_G) = \varphi ^{-1}(\sigma _\mathrm{ac}(P_G)), \quad \sigma _\mathrm{sc}(U_G) = \emptyset , \end{aligned}$$

where $M_\pm = \infty$ if G has a cycle; 0 otherwise.

Next two examples may be typical ones for showing the advantage of Theorem 1.2. The results in [14] cannot be applied to them.

Let $\mathcal {T}_{d}$ be a d-regular tree $\mathcal {T}_{d}$ ($d\ge 2$), which is an infinite acyclic graph of constant degree d. See Fig. 1. The spectrum of the transition probability operator $P_{\mathcal {T}_{d}}$ on $\mathcal {T}_{d}$ is $\sigma (P_{\mathcal {T}_{d}})=[-2\sqrt{d-1}/d, 2\sqrt{d-1}/d]$. Refer to [8, 26], for instance. If $d\ge 3$, $\mathcal {T}_{d}$ is not a crystal lattice, but the spectral mapping still holds from Theorem 1.2. Detailed geometrical and analytical structure of the eigenvalues $\pm \,1$ are discussed in [17]. Moreover, we can find $\sigma (U_{\mathcal {T}_{d}})$ has no singular continuous spectrum by results in [8, 26] with Corollary 1.3.

Example 1.2

For the d-regular tree $\mathcal {T}_{d}$,

$$\begin{aligned}&\sigma (U_{\mathcal {T}_{d}}) = \sigma _\mathrm{ac}(U_{\mathcal {T}_{d}}) \cup \sigma _\mathrm{p}(U_{\mathcal {T}_{d}}), \quad \sigma _\mathrm{p}(U_{\mathcal {T}_{d}}) = \{1\}^{M_+} \cup \{-1\}^{M_-},\\&\sigma _\mathrm{ac}(U_{\mathcal {T}_{d}}) = \varphi ^{-1}([-2\sqrt{d-1}/d, 2\sqrt{d-1}/d]), \quad \sigma _\mathrm{sc}(U_{\mathcal {T}_{d}}) = \emptyset , \end{aligned}$$

where $M_\pm = \infty$ if $d\ge 3$; 0 if $d=2$.

Fig. 1

$\mathcal {T}_{d}$ ($d=3$)

Fig. 2

$\mathcal {S}_{d}$ ($d=2$)

Last example in this section is a graph which could be said to be a skeleton of the famous fractal figure. Here we call it the d-dimensional Sierpiński lattice $\mathcal {S}_{d}$, which can be found in [4, 18]. See Fig. 2.

To construct an infinite Sierpiński lattice $\mathcal {S}_{d}$, we define $f_{i} \ : \ \mathbb {R}^{d} \rightarrow \mathbb {R}^{d}$ by $f_{i}(x) = \frac{1}{2}(x+e_i) \ (0 \le i \le d)$. Here $\{e_i\}_{i=1}^{d}$ is the standard basis of $\mathbb {R}^d$ and $e_0$ be the 0 vector. Furthermore we define $V_n$ inductively as follows:

$$\begin{aligned} V_0 = \bigcup _{0 \le i < j \le d} \{(1-t)e_i + t e_j \in \mathbb {R}^d \ ; \ 0 \le t \le 1 \} \end{aligned}$$

and

$$\begin{aligned} V_n = f_0^{-1}\left( \bigcup _{i=0}^d f_i(V_{n-1})\right) , \quad n \ge 1. \end{aligned}$$

We regard $\widetilde{\mathcal {S}}_d = \cup _{n \ge 0} V_n$ as an infinite graph which is 2d-regular except at the origin and the degree of the origin is d. Here the set of vertices of $V_{0}$ is identified with $\{e_i\}_{i=0}^d$ and $V(\widetilde{\mathcal {S}}_d)$ with the set of all vertices defined repeatedly; similarly, the set of unoriented edges of $V_{0}$ is identified with $\{e_{i}e_{j}\}_{0\le i<j\le d}$ and $E(\widetilde{\mathcal {S}}_d)$ with the set of all vertices defined repeatedly. We prepare two copies of an infinite graph $\widetilde{\mathcal {S}}_d$ and identify the vertices (the origins) of degree d. We call the infinite 2d-regular graph constructed here the d-dimensional Sierpiński lattice and denote it by $\mathcal {S}_d$. For such a fractal graph, we fortunately know the spectrum of the transition probability operator $P_{\mathcal {S}_d}$ of the symmetric random walk on $\mathcal {S}_d$. Refer to [6, 18, 29] for instance. Remark that $\mathcal {S}_d$ is not a crystal lattice. By Theorem 1.2, we obtain the following.

Example 1.3

For the d-dimensional Sierpiński lattice $\mathcal {S}_d$ with $d \ge 2$,

$$\begin{aligned} \sigma (U_{\mathcal {S}_d})= & {} \varphi ^{-1}\left( \overline{\bigcup _{k=0}^{\infty } \left\{ \left\{ 1-\rho ^{-k}\left( \frac{d+1}{2d}\right) \right\} \cup \left\{ 1-\rho ^{-k} \left( \frac{d+3}{2d}\right) \right\} \right\} } \cup \left\{ \frac{-1}{d} \right\} \right) \\&\cup \{1\}^{M_+} \cup \{-1\}^{M_-}, \end{aligned}$$

where $\rho (x) =-2dx^2+(d+3)x$ and $M_\pm = \infty$.

In the above, the multiplicity $M_\pm$ of $\{\pm 1\}$ can be derived by the same argument as in [14] in terms of the distribution of cycles. We remark that the same results hold for a standard Sierpiński lattice $\widetilde{\mathcal {S}}_{2}$. See [29].

We close this section by mentioning a typical stochastic behavior named localization for the above three examples of the Grover walk on an infinite graph $G=(V,D)$. Let $\psi _n = U_G^n\psi _0$ be the state of a walker at time $n \in \mathbb {N}$ with the initial state $\psi _0$ ($\Vert \psi _0\Vert =1$). The distribution $\mu _n^{(\psi _0)}: V\rightarrow [0,1]$ of the walker at time n is defined by $\mu _n^{(\psi _0)}(u) =\sum _{e:t(e)=u}|\psi _n(e)|^2$. We say localization occurs if $\limsup _{n \rightarrow \infty }\mu _n^{(\psi _0)}(u) > 0$ with some $u \in V$. It follows from the result of Teplyaev [29] that the spectrum of $P_{\mathcal {S}_2}$ is pure point and hence, by Theorem 1.2 and Corollary 1.3, so is that of $U_{\mathcal {S}_2}$. In particular, $U_{\mathcal {S}_{2}}$ has a complete set of eigenvectors. By [24, Corollary 4.4], localization occurs for any initial state $\psi _0$. Thus, the time evolution behavior of the Grover walk on $\mathcal {S}_{2}$ consists of only “localization”. From Example 1.1, $\mathbb {Z}^d$ ($d \ge 2$) satisfies $\sigma _\mathrm{ac}(U_{\mathbb {Z}^d}) = \varphi ^{-1}([-1, 1]) = S^1$, $\sigma _\mathrm{sc}(U_{\mathbb {Z}^d}) = \emptyset$, and $\sigma _\mathrm{p}(U_{\mathbb {Z}^d}) = \{\pm 1\}$, because $\mathbb {Z}^d$ includes cycles. Example 1.2 also concludes that $S^1 \supsetneq \sigma _\mathrm{ac}(U_{\mathcal {T}_d}) \not = \emptyset$, $\sigma _\mathrm{sc}(U_{\mathcal {T}_d}) = \emptyset$, $\sigma _\mathrm{p}(U_{\mathcal {T}_d}) = \{\pm 1\}$ if $d \ge 3$. Hence, the time evolution behavior of the Grover walk on $\mathbb {Z}^d$ and $\mathcal {T}_d$ ($d \ge 2$) have a possibility to exhibit another stochastic behavior, for example, a linear spreading. Because $\mathcal {T}_2 = \mathbb {Z}$, it follows that $\sigma _\mathrm{ac}(U_\mathbb {Z}) = \varphi ^{-1}([-1,1]) = S^1$ and $\sigma _\mathrm{sc}(U_\mathbb {Z}) = \sigma _\mathrm{p}(U_\mathbb {Z}) = \emptyset$. Hence, localization never occurs for any initial states. Note that $\mathbb {Z}$ is also viewed as a crystal lattice without a cycle. Another example of a quantum walk on an acyclic crystal lattice, called a magnifier graph, is considered in [16] (see also [18, 27]). We summarize spectral and localization properties for the above three examples in the following table.

Graph G	$\sigma _\mathrm{ac}(U_G)$	$\sigma _\mathrm{sc}(U_G)$	$\sigma _\mathrm{p}(U_G)$	Localization
$\mathbb {Z}$	$S^1$	$\emptyset$	$\emptyset$	For $\not \exists \psi _0 \in \ell ^2(D)$
$\mathbb {Z}^d$ ($d \ge 2$)	$S^1$	$\emptyset$	$\{\pm \,1\}$	For $\exists \psi _0 \in \ell ^2(D)$
$\mathcal {T}_d$ ($d \ge 3$)	$\subsetneq S^1$	$\emptyset$	$\{\pm \,1\}$	For $\exists \psi _0 \in \ell ^2(D)$
$\mathcal {S}_{2}$	$\emptyset$	$\emptyset$	$\sigma (U_G)= \overline{\sigma _\mathrm{p}(U_G)}$	For $\forall \psi _0 \in \ell ^2(D)$

Remark 1.1

In the above examples, we consider the Grover walk [1, 30]. The behavior of quantum walks strongly depends on the definitions of shift and coin operators. Indeed, for other types of quantum walks on $\mathcal {S}_2$ and its Sierpiński pre-lattice, a numerical simulation suggests a diffusive spreading rate [22], and their recurrence relation obtained by a notion of renormalization group suggests that the spreading rate is close to ballistic [5].

This paper is organized as follows. We prepare notations and provide our setting in Sect. 2. Under the setting, we construct an abstractive unitary operator on $\mathcal {H}$ denoted by a unitary involution S and coisometry map $d_A$ and give two examples in Sect. 3. In Sect. 4, we introduce important invariant subspaces of our abstractive quantum walk induced by S and $d_A$. We give the proofs of Eqs. (1.6) and (1.5) of Theorem 1.2 in Sects. 5 and 6, respectively. The final section is the summary and discussion.

2 Preliminaries

Let $\mathcal {H}$ and $\mathcal {K}$ be complex Hilbert spaces and $d_A:\mathcal {H} \rightarrow \mathcal {K}$ a coisometry, i.e., $d_A$ is bounded and

$$\begin{aligned} d_A d_A^{*} = I_{\mathcal {K}}, \end{aligned}$$

(2.1)

where $I_{\mathcal {K}}$ is the identity operator on $\mathcal {K}$. Then, $d_A^{*}:\mathcal {K} \rightarrow \mathcal {H}$ is an isometry, because

$$\begin{aligned} \Vert d_A^{*} f\Vert _{\mathcal {H}}^2 = \langle f, d_A d_A^{*} f \rangle _{\mathcal {K}} = \Vert f\Vert _{\mathcal {K}}^2, \quad f \in \mathcal {K}. \end{aligned}$$

Because $(d_A^{*}d_A)^2=d_A^{*} d_A$ from (2.1), we know that $\Pi _\mathcal {A}:= d_A^{*}d_A$ is the projection onto $\mathcal {A}:=\mathrm{Ran} (d_A^{*} d_A)$. By (2.1) again, we have $f = d_A(d_A^{*}f) \in d_A\mathcal {H}$ for $f \in \mathcal {K}$. Hence we observe that $\mathcal {K} = d_A \mathcal {H}$ and

$$\begin{aligned} \mathcal {A} = d_A^{*} \mathcal {K} = \mathrm{Ran} (d_A^{*}) = \mathrm{Ran} \Pi _\mathcal {A}. \end{aligned}$$

Because $\ker (d_A) = \mathrm{Ran}(d_A^{*})^{\bot }$, we know that $d_A$ is a partial isometry and

$$\begin{aligned} \Vert d_A \psi \Vert _{{\mathcal {K}}}^2 = \langle \psi , \Pi _\mathcal {A} \psi \rangle _{{\mathcal {H}}} = \Vert \psi \Vert _{{\mathcal {H}}}^2, \quad \psi \in \mathcal {A} = \ker (d_A)^{\perp }. \end{aligned}$$

We call the self-adjoint operator $C := 2 d_A^{*} d_A - 1$ on $\mathcal {H}$ a coin operator, because we observe, from Lemma 2.1, that C is decomposed into

$$\begin{aligned} C = I \oplus (-I) \quad \text{ on }\ \mathcal {H} =\mathcal {A} \oplus \mathcal {A}^{\perp }. \end{aligned}$$

Lemma 2.1

Let $d_A$ and C be as above. Then, we have the following:

• (1) $\sigma (C) = \{\pm 1\}$.

• (2) $\mathcal {A} = \ker (C -1)$ and $\mathcal {A}^{\perp } = \ker (C+1)$

• (3) $\displaystyle P_{\pm } = \frac{1 \pm C}{2}$ is the projection onto $\ker (C \mp 1)$ and

  $$\begin{aligned} P_+ = \Pi _\mathcal {A}, \quad P_- = \Pi _{\mathcal {A}^{\perp }}. \end{aligned}$$

• (4) $\mathcal {H}$ is decomposed into

  $$\begin{aligned} \mathcal {H}&= \mathrm{Ran} (d_A^{*}) \oplus \ker (d_A) = \mathcal {A} \oplus \mathcal {A}^{\perp } = \mathrm{Ran} P_+ \oplus \mathrm{Ran} P_-. \end{aligned}$$

In particular, we have

$$\begin{aligned} C d_A^{*} = d_A^{*}, \quad d_A C = d_A. \end{aligned}$$

Proof

(1) is proved by the self-adjointness of C and the fact

$$\begin{aligned} C^2 = (2 d_A^{*} d_A - 1)^2 = 1. \end{aligned}$$

By direct calculation, we have $C \Pi _\mathcal {A} = \Pi _\mathcal {A}$ and $C \Pi _{\mathcal {A}^{\perp }} = -\Pi _{\mathcal {A}^{\perp }}$. Hence, (2) is proved. To show (3), it suffices, from (2), to show that $P_+ = \Pi _\mathcal {A}$ and $P_- = \Pi _{\mathcal {A}^{\perp }}$, which is proved through an easy calculation. The above argument and (3) immediately lead to (4). $\square$

From Lemma 2.1 and its proof, we know that the coin operator is a unitary involution, i.e., C is unitary and self-adjoint and that $C^2=1$.

Let S be a unitary involution on $\mathcal {H}$ and set

$$\begin{aligned} d_B = d_A S. \end{aligned}$$

Observe that $d_B$ is also a coisometry. Similarly to $d_A$, we observe that the projection onto the closed subspace $\mathcal {B} :=\mathrm{Ran}(d_B^{*} d_B)$ is given by $\Pi _\mathcal {B} := d_B^{*} d_B$ and

$$\begin{aligned} \mathcal {B}=d_B^{*}\mathcal {K} = \mathrm{Ran}(d^{*}_B) = \mathrm{Ran} \Pi _\mathcal {B}. \end{aligned}$$

We summarize the relation between these two coisometries $d_A$ and $d_B$ in the following:

Lemma 2.2

Let $d_A$ and $d_B$ be as above. Then, we have the following:

• (1) $d_A S = d_B$, $S d_A^{*} = d_B^{*}$.

• (2) $d_A d_A^{*} = d_B d_B^{*} = I_\mathcal {K}$.

• (3) $\Pi _\mathcal {A} S = S \Pi _\mathcal {B}$.

• (4) $d_A^{*}$, $d_B^{*}$ are isometry operators and

  $$\begin{aligned} \Vert d_A^{*} f\Vert _\mathcal {H} = \Vert d_B^{*} f\Vert _\mathcal {H} = \Vert f\Vert _\mathcal {K} \quad \text{ for } \text{ all }\ f \in \mathcal {K}. \end{aligned}$$

We omit the proof because it is straightforward.

3 Abstract quantum walks and two examples

Given a coisometry $d_A:\mathcal {H} \rightarrow \mathcal {K}$ and a unitary involution S on $\mathcal {H}$, we can define the coin operator $C = 2d_A^{*} d_A -1$ and the coisometry $d_B = d_A S$ as in the previous section. Throughout this section, we fix $d_A$ and S and call them a boundary operator and a shift operator, respectively. In analogy with the twisted Szegedy walk (see Example 3.1), we define an abstract time evolution U and its discriminant T as follows:

Definition 3.1

Let $d_A$, $d_B$, C, and S be as above. Then,

• (1) The evolution associated with the boundary operator $d_A$ and the shift operator S is defined by

  $$\begin{aligned} U = S C. \end{aligned}$$

• (2) The discriminant of U is defined by

  $$\begin{aligned} T = d_A d_B^{*}. \end{aligned}$$

S and C are unitary operators on $\mathcal {H}$, so is the evolution U. By definition, the discriminant T is a self-adjoint operator on $\mathcal {K}$.

We present the two examples. The first one is the extended version of the Szegedy walk on a graph; the second one is not directly concerned with any graph.

Example 3.1

(Twisted Szegedy walk [14]) Let $G =(V, E)$ be a (possibly infinite) graph with the sets V of vertices and E of unoriented edges. (E can include multiple edges and self-loops.) We use D to denote the set of symmetric arcs induced by E. For an arc $e\in D$, the origin and the terminus of e are denoted by o(e) and t(e), respectively. The inverse edge of e is denoted by $\bar{e}$. Let $\mathcal {H} = \ell ^2(D)$ and $\mathcal {K} = \ell ^2(V)$. A boundary operator $d_A:\mathcal {H} \rightarrow \mathcal {K}$ is defined as

$$\begin{aligned} (d_A\psi )(v) = \sum _{e:o(e)=v} \psi (e) \overline{w(e)}, \quad v \in V \end{aligned}$$

for all $\psi \in \mathcal {H}$. Here $w:D \rightarrow \mathbb {C}$ is a weight, satisfying

$$\begin{aligned} \sum _{e:o(e) = v} |w(e)|^2 = 1 \quad \text{ for } \text{ all }\ v \in V. \end{aligned}$$

The adjoint $d_A^{*}:\mathcal {K} \rightarrow \mathcal {H}$ of $d_A$ is called a coboundary operator and given by

$$\begin{aligned} (d_A^{*} f)(e) = w(e) f(o(e)), \quad e \in D \end{aligned}$$

for all $f \in \mathcal {K}$. We observe that $d_A d_A^{*} = I_\mathcal {K}$, because

$$\begin{aligned} (d_Ad_A^{*}f)(v) = \sum _{e:o(e)=v} (d_A^{*}f)(e) \overline{w(e)} = \sum _{e:o(e)=v} |w(e)|^2 f(o(e)) = f(v). \end{aligned}$$

Hence, the boundary operator $d_A$ is a coisometry.

We call a map $\theta :D \rightarrow \mathbb {C}$ a 1-form if it satisfies

$$\begin{aligned} \theta (\bar{e}) = - \theta (e) \quad \text{ for } \text{ all }\ e \in D. \end{aligned}$$

In [14], the twisted Szegedy walk associated with the weight w and the 1-form $\theta$ is defined as follows:

• (1) The total state space is $\mathcal {H}$;

• (2) The time evolution is

  $$\begin{aligned} U^{(w,\theta )} = S^{(\theta )} C^{(w)}, \end{aligned}$$

  where the coin operator $C^{(w)}$ is given by

  $$\begin{aligned} C^{(w)} = 2 d_A^{*} d_A - 1 \end{aligned}$$

  and the twisted shift operator $S^{(\theta )}$ by

  $$\begin{aligned} (S^{(\theta )}\psi )(e) = e^{-i\theta (e)}\psi (\bar{e}), \quad e \in D \end{aligned}$$

  for all $\psi \in \mathcal {H}$;

• (3) The finding probability $\nu _n(u)$ of the twisted Szegedy walk at time n at vertex u is defined by

  $$\begin{aligned} \nu _n(u) = \sum _{e:o(e)=u}|\Psi _n(e)|^2, \end{aligned}$$

  where $\Psi _n\in \mathcal {H}$ is the nth ($n \in \mathbb {N}$) iteration of the quantum walk with the initial state $\Psi _0 \in \mathcal {H}$ ($\Vert \Psi _0\Vert ^2 = 1$), i.e., $\Psi _n=(U^{(w,\theta )})^n \Psi _0$.

Because $\theta$ is a 1-form, we know that $S^{(\theta )}$ is self-adjoint. It is easy to check $(S^{(\theta )})^2 = 1$ by definition. Thus, we know that $S^{(\theta )}$ is a unitary involution.

We observe that the boundary operator $d_A$, coin operator $C^{(w)}$, and twisted shift operator $S^{(\theta )}$ of the twisted Szegedy walk are examples of the abstract coisometry $d_A$, coin operator C, and unitary involution S, respectively.

Because $S^{(\theta )}$ is a unitary involution, we know that $d_B = d_A S^{(\theta )}$, also known as a boundary operator, is a coisometry. The discriminant operator on $\ell ^2(V)$

$$\begin{aligned} T^{(w,\theta )} = d_A d_B^{*} \end{aligned}$$

is expressed by

$$\begin{aligned} (T^{(w,\theta )}f)(u)=\sum _{e: t(e)=u} e^{i\theta (e)} w(e) \overline{w(\bar{e})} f(o(e)), \end{aligned}$$

which means that $\langle \delta _v, T^{(w,\theta )}\delta _u\rangle =0$ if and only if $(u,v),(v,u)\notin D$. This twisted version of Szegedy walk can be used effectively for a crystal lattice. See [14].

Let us set $\theta (\cdot )=0$ and $w(e)=1/\sqrt{\deg (o(e))}$, where $\deg (x)$ is the degree of a vertex x, that is, the number of oriented edges e such that $o(e)=x$. Then we have

$$\begin{aligned} (T_Gf)(u) := (T^{(w,\theta )})f(u) =\sum _{e: t(e)=u}(1/\sqrt{\deg (o(e))\deg (t(e))})f(o(e)), \end{aligned}$$

(3.1)

which is unitarily equivalent to $P_G$ on $\ell ^{2}(V,\deg )$, where $f\in \ell ^{2}(V,\deg )$ and $\Vert f\Vert ^{2} = \sum _{x\in V } |f(x)|^{2}\deg (x) <\infty$. Here $P_G$ is the transition probability operator of the symmetric random walk on G. We remark that $P_G=T_G$ if G is d-regular, that is, $\deg (x) =d$ for any $x\in V$. For $w(e)=1/\sqrt{\deg (o(e))}$ and $\theta (\cdot )=0$, $U_G :=U^{(w,\theta )}$ is said to be the evolution operator of the Grover walk:

$$\begin{aligned} (U_G\psi )(e) =\sum _{f: o(e)=t(f)}(2/\deg (o(e)) -\delta _{\bar{e},f})\psi (f). \end{aligned}$$

(3.2)

for $\psi \in \ell ^{2}(D)$.

We give an example which is not apparently related to a graph.

Example 3.2

Let $\mathcal {H} = L^2(\mathbb {R}) \oplus L^2(\mathbb {R})$ and $\mathcal {K} = L^2(\mathbb {R})$. We prepare two $C^{\infty }$ functions $\chi _0$ and $\chi _\infty$ satisfying $\chi ^2_0(x) +\chi ^2_\infty (x)=1$ for every $x\in \mathbb {R}$. As the boundary operator, we choose for $(f, g)\in \mathcal {H}$,

$$\begin{aligned} d_A(f,g)=\chi _0f+\chi _\infty g. \end{aligned}$$

It is easily seen that $d_A$ is a coisometry and for $f \in \mathcal {K}$,

$$\begin{aligned} d_A^{*} f= (\chi _0f, \chi _\infty f). \end{aligned}$$

In scattering theory, functions $\chi _0$ and $\chi _\infty$ are taken, for instance, to be $\chi _0(x) = 1$ if $|x| \le R$; $0 \le \chi _0(x) \le 1$ if $R < |x| \le 2R$; $\chi _0(x) = 0$ if $|x| >2R$ with $\chi _\infty (x) = \sqrt{1-\chi _0^2(x)}$ and $R>0$. Then $d_A^{*}$ decomposes a function f into the part $\chi _0 f$ near the origin and the part $\chi _\infty f$ at infinity.

Now, we choose S as $S(f, g)= (g, f)$. Then, the unitary operator $U = S(2d_A^{*}d_A-1)$ is expressed by

$$\begin{aligned} U(f, g)=\left( 2\chi _0\chi _\infty f + (2\chi _{\infty }^2-1)g, (2\chi _0^2-1)f + 2\chi _0\chi _\infty g \right) , \end{aligned}$$

which implies that U is isomorphic to

$$\begin{aligned} U\cong \begin{bmatrix} 2\chi _0\chi _\infty&\quad 2\chi _\infty ^2-1 \\ 2\chi _0^2-1&\quad 2\chi _0\chi _\infty \end{bmatrix}. \end{aligned}$$

The discriminant T is equivalent to $2\chi _0\chi _\infty$.

This can be extended to more general situation. Let $\mathfrak {H} =\bigoplus _{j=1}^{2N} \mathfrak {K}$ be the direct sum of N copies of a Hilbert space $\mathfrak {K}$ and $\{P_j\}_{j=1}^{2N}$ be bounded operators satisfying $P_1 P_1^{*} + \cdots + P_{2N} P_{2N}^{*} =1$. Define $d_A:\mathfrak {H} \rightarrow \mathfrak {K}$ as

$$\begin{aligned} d_A (f_1, \ldots , f_{2N}) = \sum _{j_=1}^{2N} P_j f_j, \quad (f_1, \ldots , f_{2N}) \in \bigoplus _{j=1}^{2N} \mathfrak {K}. \end{aligned}$$

Taking N unitary involutions $s_j$ on $\mathfrak {K} \oplus \mathfrak {K}$, we define S on $\mathfrak {H} \simeq \bigoplus _{j=1}^N (\mathfrak {K} \oplus \mathfrak {K})$ as $S=\bigoplus _{j=1}^N s_j$. Similarly to above, we can prove that $d_A$ is coisometry and S is a unitary involution. Hence, Theorem 1.2 is applicable to $U=S(2d_A^{*}d_A-1)$ with S and $d_A$ defined as above.

Remark 3.1

Example 3.2 suggests that the spectral mapping theorem can be applied to a wider class of unitary operators that are not apparently related to the Szegedy walk on a graph. If $\mathfrak {K} = \ell ^2(V)$ with V a countable set, then $\mathfrak {H} = \bigoplus _{j=1}^{2N} \mathfrak {K}$ can be identified with $\ell ^2(V; \mathbb {C}^{2N})$. Then the question naturally arises when the abstract evolution U becomes the Szegedy walk on a graph G with vertices V. We treat this problem in a forthcoming paper [23].

In the case where $V = \mathbb {Z}^d$ and $d=N$, taking a family of normalized vectors $\{ \chi (x) \}_{x \in \mathbb {Z}} \subset \mathbb {C}^{2d}$, we define $P_j$ as the multiplication operator by jth component $\chi _j(x)$ of $\chi (x)$: $(P_j f)(x) = \chi _j(x) f(x)$ ($f \in \mathfrak {K}$). Because $P_j P_j^{*}$ is the multiplication operator by $|\chi _j(x)|^2$ and $\chi (x)$ is a normalized vector, $P_1 P_1^{*} + \cdots P_{2N} P_{2N}^{*}=1$. Identifying $\mathfrak {K} \oplus \mathfrak {K}$ with $\ell ^2(V;\mathbb {C}^2)$, we define a unitary involution $s_j$ as $(s_j (f,g))(x) = ( p_j f(x) - q_j g(x+1), p_j g(x) + \overline{q_j} f(x-1))$ ($(f,g) \in \mathfrak {K} \oplus \mathfrak {K}$) with $p_j^2 + |q_j|^2 =1$ ($p_j \in \mathbb {R}$, $q_j \in \mathbb {C}$). Then, $U=S(2d_A^{*}d_A-1)$ becomes a d-dimensional generalization of Kitagawa’s quantum walk [20]. In [9], we analyze the spectrum of such an evolution U using the spectral mapping theorem.

4 Invariant subspaces of U

In this section, we introduce important invariant subspaces of abstract evolution U in Definition 3.1 to describe the spectrum. We list important properties of $d_A$ and T in the following lemmas.

Lemma 4.1

The following hold:

• (1) $C d_A^{*} = d_A^{*}, \quad d_A C = d_A$.

• (2) $C d_B^{*} = 2 d_A^{*} T -d_B^{*}, \quad d_B C = 2T d_A - d_B$.

• (3) $U d_A^{*} = d_B^{*}, \quad Ud_B^{*} = 2 d_B^{*} T - d_A^{*}$.

• (4) $d_A U d_A^{*} = d_B U d_B^{*} = T, \quad d_B U d_A^{*} = I_{\ell ^2(V)}$

• (5) $T = d_A S d_A^{*} = d_A d_B^{*} = d_B d_A^{*}$.

• (6) $d_A^{*} T d_A = \Pi _\mathcal {A} U \Pi _\mathcal {A}, \quad d_B^{*} T d_B = \Pi _\mathcal {B} U \Pi _\mathcal {B}$

Proof

The proof is an easy exercise and is omitted. $\square$

Lemma 4.2

$\Vert T\Vert \le 1$.

Proof

The assertion follows from the following calculation:

$$\begin{aligned} \Vert T f \Vert ^2 = \langle f, d_A S d_A^{*} f \rangle = \langle d_A^{*} f, S d_A^{*} f \rangle \le \Vert d_A^{*} f \Vert ^2 = \Vert f \Vert ^2, \quad f \in \mathcal {K}. \end{aligned}$$

$\square$

Because S is a unitary involution, the following lemma is proved similarly to Lemma 2.1.

Lemma 4.3

• (1) $\sigma (S) = \{ \pm 1\}$.

• (2) The projection $Q_\pm$ onto $\mathcal {H}^S_\pm :=\ker (S \mp 1)$ is given by

  $$\begin{aligned} Q_{\pm } = \frac{1 \pm S}{2}. \end{aligned}$$

We now define three subspaces $\mathcal {L}$, $\mathcal {L}_1$, and $\mathcal {L}_0 \subset \mathcal {H}$ as follows:

$$\begin{aligned}&\mathcal {L} = \mathcal {A} + \mathcal {B}\\&\mathcal {L}_1 = d_A^{*} \ker (T^2-1)^{\perp } + d_B^{*}\ker (T^2-1)^{\perp } \\&\mathcal {L}_0 = d_A^{*} \ker (T^2-1). \end{aligned}$$

$\mathcal {L}_0 = \{0\}$ if and only if $\sigma _\mathrm{p}(T) \cap \{+1,-1\} = \emptyset$. In this case, $\mathcal {L} = \mathcal {L}_1$ and thus the problem becomes simple. We need to treat the case $\mathcal {L}_0 \not =\{0\}$ with care.

Example 4.1

• (1) Let us consider what the subspaces $\mathcal {L}$, $\mathcal {L}_1$, and $\mathcal {L}_0$ are for the evolution $U_G$ of the Grover walk on a graph $G=(V,D)$ defined in Example 3.1 (see also Example 1.1). In this case, $d_A^{*}f$ and $d_B^{*}f$ ($f \in \ell ^2(V)$) are represented as

  $$\begin{aligned} (d_A^{*}f)(e) = f(o(e)) /\sqrt{\deg (o(e))}, \quad (d_B^{*}f)(e) = f(t(e)) /\sqrt{\deg (t(e))}, \quad e \in D. \end{aligned}$$

  Hence, $d_A^{*} \delta _v =\sum _{e \in D:o(e)=v} \delta _e/ \sqrt{\deg v}\in \ell ^2(D)$ is supported on the set of arcs with the same origin $v \in V$ and $\{d_A^{*} \delta _v \}_{v \in V}$ is a CONS of $\mathcal {A}$. Similarly, $d_B^{*} \delta _v \in \ell ^2(D)$ is supported on the set of arcs with the same terminus v and $\{d_B^{*} \delta _v \}_{v \in V}$ is a CONS of $\mathcal {B}$. In the case where $G=\mathcal {T}_d$ (Example 1.2) and $G=\mathbb {Z}^d$, $T_G$ has no eigenvalues. Hence, $\mathcal {L}_0 = \{0\}$ and $\mathcal {L} =\mathcal {L}_1$.

• (2) Let $\chi _0$, $\chi _\infty$ satisfy $\chi _0^2 + \chi _\infty ^2\equiv 1$ and $\chi _0(x) = \chi _\infty (x) = 1/\sqrt{2}$ on some open interval $I \subset \mathbb {R}$. Let U and T be defined as in Example 3.2. Then $1 \in \sigma _\mathrm{p}(T)$, because $2\chi _0 \chi _\infty \equiv 1$ on I. Hence, $\mathcal {L}_0 \not =\{0\}$ and $\mathcal {L} \not = \mathcal {L}_1$.

Because $\ker (T^2-1) = \ker (T-1) \oplus \ker (T+1)$, $\mathcal {L}_0$ is decomposed into

$$\begin{aligned} \mathcal {L}_0 = \mathcal {L}_0^+ \oplus \mathcal {L}_0^- , \end{aligned}$$

where $\mathcal {L}_0^{\pm } = d_A^{*}\ker (T\mp 1)$.

Lemma 4.4

• (1) $\mathcal {L}_0 = \mathcal {A} \cap \mathcal {B} = d_B^{*} \ker (T^2-1)$.

• (2) For all $d_A^{*}f^{\pm } \in \mathcal {L}_0^{\pm }$, $d_A^{*} f^{\pm } = \pm d_B^{*} f^{\pm }$ holds.

• (3) $\mathcal {L}_0^{\pm } \subset \mathcal {H}_\pm ^S$ and $S (d_A^{*} f^{\pm }) = \pm d_A^{*} f^{\pm }$.

Proof

We first prove $\mathcal {L}_0 \subset \mathcal {A} \cap \mathcal {B}$. To this end, let $d_A^{*} f \in \mathcal {L}_0$ ($f \in \ker (T^2-1)$) and $f = f^+ + f^-$ ($f^{\pm } \in \ker (T\mp 1)$. Then we observe, from Lemma 2.2, that

$$\begin{aligned} \langle d_A^{*} f^{\pm }, S d_A^{*}f^{\pm } \rangle = \langle f^{\pm }, Tf^{\pm } \rangle = \pm \Vert f^{\pm }\Vert ^2 = \pm \Vert d_A^{*} f^{\pm }\Vert ^2. \end{aligned}$$

Hence, $\langle d_A^{*}f^{\pm }, (S \mp 1) d_A^{*} f^{\pm } \rangle = 0$. By Lemma 4.3, $\Vert Q_\mp d_A^{*}f^{\pm } \Vert = 0$. Noting that $Q_\mp = 1- Q_\pm$, we obtain $d_A^{*} f^{\pm } = Q_\pm d_A^{*} f^{\pm }$. Hence, by Lemma 2.2,

$$\begin{aligned} d_B^{*} f^{\pm } = S d_A^{*} f^{\pm } = S Q_\pm d_A^{*} f^{\pm } = \pm d_A^{*} f^{\pm }. \end{aligned}$$

(4.1)

Thus, we have

$$\begin{aligned} d_A^{*} f = d_A^{*} (f^+ + f^-) = d_B^{*} ( f^+ - f^-) \in \mathcal {A} \cap \mathcal {B}. \end{aligned}$$

(4.2)

We prove the converse statement. To this end, let $\psi \in \mathcal {A} \cap \mathcal {B}$. This can be represented in two ways:

$$\begin{aligned} \psi = d_A^{*} f = d_B^{*} g, \quad f, g \in \mathcal {K}. \end{aligned}$$

By Lemmas 2.2 and 4.1, we have $f = T g$ and $g = T f$, which imply $f = T^2 f$ and $g = T^2 g$. Thus, we know that $f, g \in \ker (T^2-1)$. In particular, we have $\psi \in \mathcal {L}_0$, and the converse statement $\mathcal {A} \cap \mathcal {B} \subset \mathcal {L}_0$ is proved. Hence, we have $\mathcal {L}_0 = \mathcal {A} \cap \mathcal {B}$. Moreover, from (4.2), we also have $\mathcal {L}_0 \subset d_B^{*} \ker (T^2-1)$. In a way similar to the above, we can show $d_B^{*}\ker (T^2-1) \subset \mathcal {A} \cap \mathcal {B}$. Thus, (1) is proved.

(4.1) implies (2) and (3). $\square$

Lemma 4.5

$$\begin{aligned} \mathcal {L} = \mathcal {L}_1 \oplus \mathcal {L}_0. \end{aligned}$$

Moreover, for all $\psi \in \mathcal {L}$, there exist unique $f, g \in \ker (T^2 -1)^{\perp }$ and $h_0 \in \ker (T^2-1)$ such that

$$\begin{aligned} \psi = d_A^{*} f + d_B^{*} g + d_A^{*} h_0. \end{aligned}$$

(4.3)

Proof

We first prove that $\mathcal {L}_1 \perp \mathcal {L}_0$. To this end, let $\psi _1 \in \mathcal {L}_1$ and $\psi _0 \in \mathcal {L}_0$. Then $\psi _0$ and $\psi _1$ can be represented as

$$\begin{aligned}&\psi _1 = d_A^{*} f + d_B^{*} g, \quad f,g \in \ker (T^2-1)^{\perp }, \\&\psi _0 = d_A^{*} h_0, \quad h_0 \in \ker (T^2-1) \end{aligned}$$

By the decomposition $h_0 = h_0^+ + h_0^-$ ($h_0^{\pm } \in \ker (T\mp 1)$) and Lemma 4.4, we have

$$\begin{aligned} \langle \psi _1, d_A^{*} h_0^{\pm } \rangle&= \langle d_A^{*} f + d_B^{*} g, d_A^{*} h_0^{\pm } \rangle = \langle d_A^{*} f, d_A^{*} h_0^{\pm } \rangle \pm \langle d_B^{*} g, d_B^{*} h_0^{\pm } \rangle , \\&= \langle f \pm g, h_0^{\pm } \rangle = 0. \end{aligned}$$

Because $\psi _0 = d_A^{*} h_0^+ + d_A^{*} h_0^-$, we obtain $\langle \psi _1, \psi _0 \rangle = 0$. Hence, we have the desired result.

To prove (4.3), let $\psi \in \mathcal {L}$. Then there exist $\tilde{f}, \tilde{g} \in \mathcal {K}$ such that

$$\begin{aligned} \psi = d_A^{*} \tilde{f} + d_B^{*} \tilde{g}. \end{aligned}$$

Decomposing $\tilde{f}$ and $\tilde{g}$ as $\tilde{f} = f + f_0$, $\tilde{g} = g + g_0$ ($f,g \in \ker (T^2-1)^{\perp }$, $f_0, g_0 \in \ker (T^2-1)$), we have $\psi = d_A^{*} f + d_B^{*} g + d_A^{*} f_0 + d_B^{*} g_0$. Because $d_B^{*} g_0 \in \mathcal {L}_0$, decomposing $g_0$ as $g_0 = g_0^+ + g_0^-$ ($g_0^{\pm } \in \ker (T\mp 1)$), and using Lemma 4.4, we obtain $d_B^{*} g_0 = d_A^{*} (g_0^+ - g_0^-)$. Letting $h_0 = f_0 + g_0^+ - g_0^-$, we have the decomposition (4.3), which implies $\mathcal {L} \subset \mathcal {L}_1 \oplus \mathcal {L}_0$. Since the converse inclusion is clear, we obtain $\mathcal {L} = \mathcal {L}_1 \oplus \mathcal {L}_0$.

We prove the uniqueness of the decomposition (4.3). We assume that $\psi \in \mathcal {L}$ can be represented in two ways:

$$\begin{aligned} \psi&= d_A^{*} f + d_B^{*} g + d_A^{*} h_0 \\&=d_A^{*} f^{\prime } + d_B^{*} g^{\prime } + d_A^{*} h_0^{\prime }, \end{aligned}$$

where $f,f^{\prime }, g, g^{\prime } \in \ker (T^2 -1)^{\perp }$ and $h_0, h_0^{\prime } \in \ker (T^2-1)$. Then we have

$$\begin{aligned} d_A^{*}(f -f^{\prime } + h_0 - h_0^{\prime }) = d_B^{*} (g^{\prime }-g) \in \mathcal {A} \cap \mathcal {B}. \end{aligned}$$

This implies $g^{\prime }-g \in \ker (T^2-1) \cap \ker (T^2-1)^{\perp }$ and hence $g^{\prime }=g$. Moreover, we then know that $d_A^{*}(f -f^{\prime } +h_0 - h_0^{\prime })=0$ and hence that $f- f^{\prime } = h_0^{\prime }-h_0 \in \ker (T^2-1)^{\perp } \cap \ker (T^2-1)$. Thus we have $f^{\prime }=f$, $h_0^{\prime } = h_0$. Hence, uniqueness is proved. $\square$

Lemma 4.6

$$\begin{aligned} \mathcal {L}^{\perp } = \ker (d_A) \cap \ker (d_B). \end{aligned}$$

Proof

We first prove that $\mathcal {L}^{\perp } \subset \ker (d_A) \cap \ker (d_B)$. Let $\psi \in \mathcal {L}^{\perp }$. Then we have $\langle \psi , d_A^{*} f \rangle = - \langle \psi , d_B^{*} g \rangle$ for all $d_A^{*} f + d_B^{*} g \in \mathcal {L}$ ($f, g \in \mathcal {K}$). Let $g=0$ (resp. $f=0$). We have $\langle d_A\psi , f \rangle = 0$ for all $f \in \mathcal {K}$ (resp. $\langle d_B\psi , g\rangle = 0$ for all $g \in \mathcal {K}$). Hence, we obtain $\psi \in \ker (d_A) \cap \ker (d_B)$.

Conversely, let $\psi \in \ker (d_A) \cap \ker (d_B)$. We have $\langle \psi , d_A^{*} f + d_B^{*} g \rangle = 0$ for $f, g \in \mathcal {K}$. Hence, we obtain $\psi \in \mathcal {L}^{\perp }$ and $\ker (d_A) \cap \ker (d_B) \subset \mathcal {L}^{\perp }$ is proved. $\square$

Example 4.2

Let $U_G =S(2d_A^{*}d_A-1)$ and $T_G = d_A S d_A^{*}$ be the evolution of the Grover walk on $G=(V,D)$ and its discriminant defined in Example 3.1. Then $d_A \delta _e =\delta _{o(e)} /\sqrt{\deg (o(e))}$ and $d_B \delta _e =\delta _{t(e)} /\sqrt{\deg (t(e))}$ ($e \in D$). Let G have a cycle whose edges are $\{e_1, e_2, \ldots , e_n\}$ with $x_1:= t(e_1) = o(e_2)$, $x_2:=t(e_2) = o(e_3), \ldots , x_n:=t(e_n) = o(e_1)$. Then $\sum _{j=1}^n (\delta _{e_j} - \delta _{\bar{e}_j}) \in \ker (d_A) \cap \ker (d_B)$, because $d_A(\delta _{e_j}-\delta _{\bar{e}_{j-1}})=0$ and $d_B(\delta _{e_j} - \delta _{\bar{e}_{j+1}})=0$. Hence, $\mathcal {L}^{\perp }\not =\{0\}$. See [14] for more details.

Proposition 4.7

$\overline{\mathcal {L}_1}$, $\mathcal {L}_0$ and $\mathcal {L}^{\perp }$ are invariant subspaces of U, i.e.,

$$\begin{aligned} U \mathcal {V} \subset \mathcal {V} \end{aligned}$$

for $\mathcal {V} = \overline{\mathcal {L}_1}, \ \mathcal {L}_0$ and $\mathcal {L}^{\perp }$.

Proof

We first prove that $U \overline{\mathcal {L}_1} \subset \overline{\mathcal {L}_1}$. It suffices to show that $U \mathcal {L}_1 \subset \mathcal {L}_1$. To this end, let $\psi \in \mathcal {L}_1$ and write

$$\begin{aligned} \psi = d_A^{*} f + d_B^{*} g, \quad f \in \ker (T^2-1)^{\perp }, \ g \in \ker (T^2-1)^{\perp }. \end{aligned}$$

By Lemma 4.1, $U \psi = Ud_A^{*} f + Ud_B^{*} g = d_B^{*} (f + 2Tg) -d_A^{*}g$. Because $f + 2Tg \in \ker (T^2-1)^{\perp }$, we have $U\psi \in \mathcal {L}_1$. Hence U leaves $\overline{\mathcal {L}_1}$ invariant.

We next prove that $U \mathcal {L}_0 \subset \mathcal {L}_0$. Let $\psi = d_A^{*} (h_0^+ + h_0^-) \in \mathcal {L}_0$ ($h_0^{\pm } \in \ker (T\mp 1)$). Then, by Lemma 4.4, $U\psi = d_B^{*} h_0^+ + d_B^{*} h_0^- = d_A^{*}(h_0^+ - h_0^-) \in \mathcal {L}_0$. Hence, we obtain the desired result.

We prove that $U \mathcal {L}^{\perp } \subset \mathcal {L}^{\perp }$. Combining Lemma 4.6 with $d_B = d_A S$, we know that

$$\begin{aligned} \mathcal {L}^{\perp } = \{ \psi \in {\mathcal {H}} \mid d_A \psi = 0, \ d_A (S \psi ) = 0 \}. \end{aligned}$$

(4.4)

Since, by Lemma 2.1, we have $\mathcal {L}^{\perp } \subset \ker (d_A) = \mathrm{Ran} P_-$, we know that $C\psi = - \psi$ holds for all $\psi \in \mathcal {L}^{\perp }$. Hence we have

$$\begin{aligned} U \psi = - S\psi , \quad \text{ for } \text{ all }\ \psi \in \mathcal {L}^{\perp }. \end{aligned}$$

(4.5)

We observe from (4.4), that $U\psi \in \mathcal {L}^{\perp }$. This completes the proof. $\square$

Proposition 4.7 implies that U is reduced by the subspaces $\overline{\mathcal {L}_1}, \ \mathcal {L}_0$ and $\mathcal {L}^{\perp }$ and is decomposed into $U=U_{\overline{\mathcal {L}_1}} \oplus U_{\mathcal {L}_0} \oplus U_{\mathcal {L}^{\perp }}$, where we have used $U_\mathcal {V}$ to denote the restriction of U to a subspace $\mathcal {V}$. Then we have

$$\begin{aligned}&\sigma (U) = \sigma ( U_{\overline{\mathcal {L}_1}} ) \cup \sigma (U_{\mathcal {L}_0} ) \cup \sigma (U_{\mathcal {L}^{\perp }}), \end{aligned}$$

(4.6)

$$\begin{aligned}&\sigma _\mathrm{p} (U) = \sigma _\mathrm{p}( U_{\overline{\mathcal {L}_1}} ) \cup \sigma _\mathrm{p}(U_{\mathcal {L}_0} ) \cup \sigma _\mathrm{p}(U_{\mathcal {L}^{\perp }}). \end{aligned}$$

(4.7)

5 Eigenvalues of U

5.1 Eigenspaces and invariant subspaces

In this subsection, we prove the following proposition:

Proposition 5.1

The following hold:

• (1) $\sigma _\mathrm{p}(U)\cap \{ \pm 1\} \subset \sigma _\mathrm{p}(U_{{\mathcal {L}_0}}) \cup \sigma _\mathrm{p}(U_{\mathcal {L}^{\perp }})$.

• (2) $\sigma _\mathrm{p}(U) {\setminus } \{\pm 1\} = \sigma _\mathrm{p}(U_{\overline{\mathcal {L}_1}}) \subset \{ e^{i\xi } \mid \cos \xi \in \sigma _\mathrm{p}(T), \ \xi \in (0,\pi ) \cup (\pi , 2\pi ) \}$.

Let $\lambda \in \mathbb {C}$ be an eigenvalue of U and $\psi \in \mathcal {H}$ its eigenvector:

$$\begin{aligned} U \psi = \lambda \psi , \quad \psi \not =0. \end{aligned}$$

(5.1)

Because U is unitary, $|\lambda | = 1$. Using the decomposition (4) of Lemma 2.1, we can write

$$\begin{aligned} \psi = d_A^{*} f + \psi _0, \quad f \in \mathcal {K}, \ \psi _0 \in \ker (d_A). \end{aligned}$$

(5.2)

Lemma 5.2

Let $f, \psi _0$ and $\lambda$ be as above. Then,

$$\begin{aligned}&(T-\lambda )f = d_B \psi _0, \end{aligned}$$

(5.3)

$$\begin{aligned}&(\bar{\lambda }- T)f = d_B\psi _0. \end{aligned}$$

(5.4)

Proof

Because $\ker (d_A) = \mathrm{Ran} P_-$ from Lemma 2.1, we have $C\psi _0 = - \psi _0$. Substituting (5.2) into (5.1), we have

$$\begin{aligned} U\psi = U(d_A^{*}f + \psi _0) = d_B^{*}f - S\psi _0. \end{aligned}$$

(5.5)

Hence, it holds, from (5.1), that

$$\begin{aligned} (d_B^{*}- \lambda d_A^{*}) f = (S + \lambda ) \psi _0. \end{aligned}$$

(5.6)

Letting $d_A$ and $d_B$ act on (5.6), we obtain

$$\begin{aligned}&(T-\lambda )f = d_A (S + \lambda ) \psi _0 = d_B \psi _0, \\&(1 - \lambda T)f = d_B(S + \lambda ) \psi _0 = \lambda d_B\psi _0. \end{aligned}$$

Noting that $\bar{\lambda } = \lambda ^{-1}$ holds from $|\lambda |=1$, we have the desired result. $\square$

Proof of Proposition 5.1

Let $\lambda$ and $\psi$ be as in (5.1) and f and $\psi _0$ as in (5.2). Combining (5.3) with (5.4), we have $(T- \mathrm{Re}\lambda ) f = 0$, and hence

$$\begin{aligned} \psi = d_A^{*} f + \psi _0, \quad f \in \ker (T -\mathrm{Re}\lambda ), \ \psi _0 \in \ker (d_A). \end{aligned}$$

We first consider the case in which $\lambda = \pm 1$. Then $f \in \ker (T \mp 1)$. Hence, by (5.3), we obtain $d_B \psi _0 = 0$ and $\psi _0 \in \ker (d_A) \cap \ker (d_B) = \mathcal {L}^{\perp }$. Because $\ker (T \mp 1) \subset \ker (T^2-1)$,

$$\begin{aligned} \psi = d_A^{*} f + \psi _0 \in \mathcal {L}_0 \oplus \mathcal {L}^{\perp } = \mathcal {L}_1^{\perp }. \end{aligned}$$

(5.7)

If $f\not =0$, then $d_A^{*} f \in \mathcal {L}_0^{\pm } {\setminus } \{0\}$. By Lemmas 4.1 and 4.4, $U(d_A^{*} f) =d_B^{*} f = \pm d_A^{*} f$. Hence, $\{\pm 1 \} \subset \sigma _\mathrm{p}(U_{\mathcal {L}_0})$. If $f=0$, then $\psi _0 = \psi \not =0$. By (5.6), we have $S\psi _0 = -\lambda \psi _0$: therefore, we observe from (5.5) that $U\psi _0 = \lambda \psi _0$. Hence, $\{\pm 1\} \subset \sigma ( U_{\mathcal {L}^{\perp }})$. Thus, $\sigma _\mathrm{p}(U)\cap \{ \pm 1\} \subset \sigma _\mathrm{p}(U_{\mathcal {L}_0}) \cup \sigma _\mathrm{p}(U_{\mathcal {L}^{\perp }})$. (1) is proved.

We next consider the case where $\lambda = e^{i\xi }$ ($\xi \in (0,\pi ) \cup (\pi , 2\pi )$). Similarly to above,

$$\begin{aligned} f \in \ker (T-\cos \xi ) \subset \ker (T^2-1)^{\perp }. \end{aligned}$$

(5.8)

Since $\lambda \not = \pm 1$, we observe that $S+\lambda$ has a bounded inverse with

$$\begin{aligned} (S + \lambda )^{-1} = \frac{S-\lambda }{1-\lambda ^2}. \end{aligned}$$

(5.9)

By (5.6), we have $\psi _0 = (S+\lambda )^{-1}(d_B^{*} -\lambda d_A^{*}) f = \frac{1}{1-\lambda ^2} \left( (1+\lambda ^2) d_A^{*} -2\lambda d_B^{*} \right) f$. Hence,

$$\begin{aligned} \psi = d_A^{*} f + \psi _0 = \frac{2}{1-\lambda ^2} \left( d_A^{*} -\lambda d_B^{*} \right) f \in \mathcal {L}_1, \end{aligned}$$

(5.10)

which implies $\sigma _\mathrm{p}(U) {\setminus } \{\pm 1\} \subset \sigma _\mathrm{p}(U_{\overline{\mathcal {L}_1}})$. Observe from (5.7) that $\sigma _\mathrm{p} (U_{\overline{\mathcal {L}_1}}) \cap \{\pm 1\} = \emptyset$. Because $\sigma _\mathrm{p} (U_{\overline{\mathcal {L}_1}}) \subset \sigma _\mathrm{p}(U)$, we have the first equality of (2): $\sigma _\mathrm{p}(U) {\setminus } \{\pm 1\} =\sigma _\mathrm{p}(U_{\overline{\mathcal {L}_1}})$. Combining (5.10) with $\psi \not =0$ yields $f\not =0$. Hence, by (5.8), $\cos \xi \in \sigma _\mathrm{p}(T)$. Therefore, $\sigma _\mathrm{p} (U) {\setminus } \{\pm 1\} \subset \{ e^{i\xi } \mid \cos \xi \in \sigma _\mathrm{p}(T), \ \xi \in (0,\pi ) \cup (\pi , 2\pi ) \}$. Thus (2) is proved. $\square$

5.2 Eigenvalues of $U_{\mathcal {L}_0}$

Let $m_{\pm } = \mathrm{dim}\ker (T \mp 1)$. We use $\{ \pm 1\}^{m_\pm }$ to denote multiplicity if $m_\pm > 0$ and use the convention that $\{ \pm 1\}^{m_\pm }= \emptyset$ if $m_\pm = 0$. Our purpose in this subsection is to prove

Proposition 5.3

The following hold:

• (1) $U_{\mathcal {L}_0} = I_{\mathcal {L}_0^+} \oplus (- I_{\mathcal {L}_0^-})$.

• (2) $\sigma (U_{\mathcal {L}_0}) = \sigma _\mathrm{p} (U_{\mathcal {L}_0}) = \{1\}^{m_+} \cup \{-1\}^{m_{-}}$.

We need the following lemma.

Lemma 5.4

$d_A^{*}\mid _{\ker (T \mp 1)}$ is a bijection with the inverse

$$\begin{aligned} (d_A^{*}\mid _{\ker (T \mp 1)})^{-1} = d_A\mid _{\mathcal {L}_0^{\pm }}. \end{aligned}$$

Proof

It suffices to show that

$$\begin{aligned} d_A^{*}\mid _{\ker (T \mp 1)}d_A\mid _{\mathcal {L}_0^{\pm }} = I_{\mathcal {L}_0^{\pm }}, \quad d_A\mid _{\mathcal {L}_0^{\pm }} d_A^{*}\mid _{\ker (T \mp 1)} = I_{\ker (T \mp 1)}. \end{aligned}$$

Let $d_A^{*} h_0^{\pm } \in \mathcal {L}_0^{\pm }$. Then, we have $d_A (d_A^{*} h_0^{\pm }) = h_0^{\pm } \in \ker (T \mp 1)$ and $d_A^{*}(d_A (d_A^{*} h_0^{\pm }) )$ $= d_A^{*} h_0^{\pm }$, which implies the former equation.

Conversely, for all $h_0^{\pm } \in \ker (T \mp 1)$, we have $d_A^{*} h_0^{\pm } \in \mathcal {L}_0^{\pm }$ and $d_A(d_A^{*} h_0^{\pm }) = h_0^{\pm }$, which implies the latter equation. $\square$

Proof of Proposition 5.3

Using Lemmas 4.1 and 4.4, we obtain the following: for $d_A^{*} h_0^{\pm } \in \mathcal {L}_0^{\pm }$,

$$\begin{aligned} U (d_A^{*} h_0^{\pm }) = S (d_A^{*} h_0^{\pm }) = \pm d_A^{*} h_0^{\pm }, \end{aligned}$$

(5.11)

which implies that $U_{\mathcal {L}_0}$ leaves $\mathcal {L}_0^{\pm }$ invariant and (1) holds. By Lemma 5.4, we have $\mathrm{dim} \ker (T \mp 1) = \mathrm{dim} \mathcal {L}_0^{\pm }$; therefore, (1) leads to (2). This completes the proof. $\square$

5.3 Eigenvalues of $U_{\mathcal {L}^{\perp }}$

Let $\mathcal {L}^{\perp }_\pm = \mathcal {L}^{\perp } \cap \mathcal {H}^S_\mp$ and $M_{\pm } = \mathrm{dim } \mathcal {L}^{\perp }_\pm$. We prove the following:

Proposition 5.5

The following hold:

• (1) $U_{\mathcal {L}^{\perp }} = I_{\mathcal {L}^{\perp }_+} \oplus (- I_{\mathcal {L}^{\perp }_-})$.

• (2) $\sigma (U_{\mathcal {L}^{\perp }}) = \sigma _\mathrm{p} (U_{\mathcal {L}^{\perp }}) = \{1 \}^{M_+} \cup \{-1\}^{M_{-}}$.

Proof

We first prove that $\mathcal {L}^{\perp }$ can be decomposed into $\mathcal {L}^{\perp } = \mathcal {L}^{\perp }_+ \oplus \mathcal {L}^{\perp }_-$. To this end, let us write $\psi \in \mathcal {L}^{\perp }$ as

$$\begin{aligned} \psi = \psi _+ + \psi _-, \quad \psi _\pm := Q_\mp \psi . \end{aligned}$$

Because, by (4.4), we have $d_A \psi = 0$ and $d_A(S\psi )=0$, we know that

$$\begin{aligned} d_A \psi _\pm = d_A \left( \frac{1\mp S}{2} \psi \right) = 0, \quad d_A (S\psi _\pm ) = d_A \left( \frac{ S\mp 1}{2} \psi \right) = 0. \end{aligned}$$

Hence, by (4.4) again, we have $\psi _\pm \in \mathcal {L}^{\perp }_\pm$. Because, by definition, $\mathcal {L}^{\perp }_+ \perp \mathcal {L}^{\perp }_-$, we know that $\mathcal {L}^{\perp } = \mathcal {L}^{\perp }_+ \oplus \mathcal {L}^{\perp }_-$.

We next prove that $\mathcal {L}^{\perp }_\pm$ is an invariant subspace of U. To this end, let $\psi _\pm \in \mathcal {L}^{\perp }_\pm$. By (4.5), we know that $U \psi _\pm = - S \psi _\pm = \pm \psi _\pm$, where we have used $\psi _\pm \in \mathcal {H}_\mp ^S$ in the last equality. The above equation implies that $U\mathcal {L}^{\perp }_\pm \subset \mathcal {L}^{\perp }_\pm$ and (1). (2) immediately follows from (1). $\square$

5.4 Eigenvalue of $U_{\overline{\mathcal {L}_1}}$

In this section, we prove:

Proposition 5.6

• (1) $\sigma _\mathrm{p}(U_{\overline{\mathcal {L}_1}}) = \{ e^{i\xi } \mid \cos \xi \in \sigma _\mathrm{p}(T), \xi \in (0,\pi ) \cup (\pi , 2\pi ) \}$.

• (2) For all $\xi \in (0,\pi ) \cup (\pi , 2\pi )$, it holds that

  $$\begin{aligned} \mathrm{dim} \ker (U - e^{i\xi }) = \mathrm{dim} \ker (T -\cos \xi ). \end{aligned}$$

Summarizing Propositions 5.1, 5.3, 5.5 and 5.6, we obtain the following:

Theorem 5.1

The set of eigenvalues of U is given by

$$\begin{aligned} \sigma _\mathrm{p}(U) = \{ e^{i\xi } \mid \cos \xi \in \sigma _\mathrm{p}(T), \ \xi \in [0,2\pi ) \} \cup \{+1\}^{M_+} \cup \{-1\}^{M_-} \end{aligned}$$

and the multiplicity is given by

$$\begin{aligned} \mathrm{dim} \ker (U - e^{i\xi })= {\left\{ \begin{array}{ll} \mathrm{dim} \ker (T - \cos \xi ), &{} \xi \in (0, \pi ) \cup (\pi , 2\pi ), \\ M_+ + m_+, &{} \xi = 0, \\ M_- + m_-, &{} \xi = \pi , \end{array}\right. } \end{aligned}$$

where

$$\begin{aligned} M_{\pm } = \mathrm{dim}\mathcal {L}^{\perp }_\pm \mathrm {\;\;and\;\;} m_\pm = \mathrm{dim}\ker (T\mp 1). \end{aligned}$$

(5.12)

The following corollary is immediately obtained from Theorem 5.1.

Corollary 5.2

Let $M_\pm$ and $m_\pm$ be as above. Then:

• (1) $\sigma _\mathrm{p}(U) {\setminus } \{\pm 1\} = \{ e^{i\xi } \mid \cos \xi \in \sigma _\mathrm{p}(T) {\setminus } \{\pm 1\}, \ \xi \in [0,2\pi ) \}$;

• (2) $\sigma _\mathrm{p}(U) \cap \{\pm 1\} = \{+1 \}^{M_+ + m_+} \cup \{-1\}^{M_-+m_-}$.

Proof of Proposition 5.6

We first prove (1). Because we have already proved in Proposition 5.1 that $\sigma _\mathrm{p} (U_{\overline{\mathcal {L}_1}}) \subset \{ e^{i\xi } \mid \cos \xi \in \sigma _\mathrm{p}(T), \xi \in (0,\pi ) \cup (\pi , 2\pi ) \}$, we need only to prove the converse statement. To this end, it suffices to show $e^{i \xi } \in \sigma _\mathrm{p}(U_{\overline{\mathcal {L}_1}})$ for $\cos \xi \in \sigma _\mathrm{p}(T) {\setminus } \{\pm 1\}$. Let $f \in \ker (T-\cos \xi ) {\setminus }\{0\}$ be an eigenvector of T with eigenvalue $\lambda = e^{i\xi }$ and set

$$\begin{aligned} \psi = \left( d_A^{*} -\lambda d_B^{*} \right) f, \end{aligned}$$

(5.13)

which is clearly in $\mathcal {L}_1$. We observe that $\psi \not =0$, because we know that $\psi = (1-\lambda S) d_A^{*} f$ and, from (5.9), that $(1-\lambda S)^{-1} = -\bar{\lambda }(S+\bar{\lambda })^{-1}$ is bounded. Because $Tf = \cos \xi f$, we have $U \psi = d_B^{*} (1- 2\lambda T )f + \lambda d_A^{*} f = \lambda \psi$. Hence we have the desired result and (1) is proved.

To prove (2), we consider the multiplicity of $e^{i\xi }$ ($\cos \xi \in \sigma _\mathrm{p}(T) {\setminus } \{\pm 1\}$). Let $\lambda = e^{i\xi } \in \sigma _\mathrm{p}(U_{\overline{\mathcal {L}_1}})$ and $\psi$ be its eigenvector. Then, from the argument in the proof of Proposition 5.1, we know that $\psi$ is of the form (5.13) up to a constant factor. As is shown in the proof of (1), we know that, if $\psi$ is of the form (5.13), then $\psi \in \ker (U-\lambda )$. Therefore we have

$$\begin{aligned} \ker (U-\lambda ) = \{ \psi = (d_A^{*} -\lambda d_B^{*}) f \mid f \in \ker (T-\cos \xi ) \}. \end{aligned}$$

Let us now define a map $K_\lambda : \ker (T-\cos \xi ) \rightarrow \ker (U-e^{i\xi })$ by

$$\begin{aligned} K_\lambda = d_A^{*} - \lambda d_B^{*} = (1-\lambda S)d_A^{*}. \end{aligned}$$

Then, $K_\lambda$ is a surjection, because $\ker (U-\lambda ) =K_\lambda \ker (T-\cos \xi )$. We also observe that an operator

$$\begin{aligned} M_\lambda = \frac{\lambda }{1-\lambda ^2} d_A (S + \bar{\lambda }) \end{aligned}$$

satisfies $M_\lambda K_\lambda = 1$. Thus, we know that $K_\lambda$ is a bijection and obtain the desired result. $\square$

Remark 5.1

From the above proof, we know that, for $\lambda = e^{i\xi } \not =\pm 1$,

• (1) $\ker (U-\lambda ) = K_\lambda \ker (T-\cos \xi )$,

• (2) $\ker (T-\cos \xi ) = M_\lambda \ker (U-\lambda )$.

6 Spectra of U

In this section, we characterize the spectrum $\sigma (U)$.

Proposition 6.1

Let $K = \{+1, -1\} \cap \sigma _\mathrm{p}(T)$. Then,

$$\begin{aligned} \sigma (U_{\overline{\mathcal {L}_1}}) {\setminus } K = \{ e^{i\xi } \mid \cos \xi \in \sigma (T), \ \xi \in [0,2\pi ) \} {\setminus } K. \end{aligned}$$

In particular, if $K = \emptyset$, then

$$\begin{aligned} \sigma (U_{\overline{\mathcal {L}_1}}) = \{ e^{i\xi } \mid \cos \xi \in \sigma (T), \ \xi \in [0,2\pi ) \}. \end{aligned}$$

Before proving this proposition, we first state the following:

Theorem 6.1

$\sigma (U) = \{ e^{i\xi } \mid \cos \xi \in \sigma (T), \ \xi \in [0,2\pi ) \} \cup \{1\}^{M_+} \cup \{-1\}^{M_-}$.

Proof

Combining (4.6) with Propositions 5.3 and 5.5, we have

$$\begin{aligned} \sigma (U)&= \sigma (U_{\overline{\mathcal {L}_1}}) \cup \sigma (U_{\mathcal {L}_0}) \cup \sigma (U_{\mathcal {L}^{\perp }}) \\&= \sigma (U_{\overline{\mathcal {L}_1}}) \cup \sigma _\mathrm{p}(U_{\mathcal {L}_0}) \cup \sigma _\mathrm{p}(U_{\mathcal {L}^{\perp }}). \end{aligned}$$

Noting that $\sigma _\mathrm{p}(U_{\mathcal {L}_0}) = K$, we observe from Proposition 6.1 that

$$\begin{aligned} \sigma (U_{\overline{\mathcal {L}_1}}) \cup \sigma _\mathrm{p}(U_{\mathcal {L}_0}) = \{ e^{i\xi } \mid \cos \xi \in \sigma (T), \ \xi \in [0,2\pi ) \}. \end{aligned}$$

Since $\sigma _\mathrm{p}(U_{\mathcal {L}^{\perp }}) = \{+1\}^{M_+} \cup \{-1\}^{M_-}$, the theorem is proved. $\square$

Proposition 6.1 is immediately proved by the following lemma:

Lemma 6.2

The following hold:

• (1) $\sigma (U_{\overline{\mathcal {L}_1}}) \subset \{ e^{i\xi } \mid \cos \xi \in \sigma (T), \ \xi \in [0,2\pi ) \}$;

• (2) $\{ e^{i\xi } \mid \cos \xi \in \sigma (T), \ \xi \in [0, 2\pi ) \} {\setminus } K \subset \sigma (U_{\overline{\mathcal {L}_1}})$.

Proof of Lemma 6.2

To prove (1), suppose that $e^{i\xi } \in \sigma (U_{\overline{\mathcal {L}_1}})$. Because $U_{\overline{\mathcal {L}_1}}$ is unitary, there exists a sequence $\{\psi _n\}$ of normalized vectors such that $\lim _{n\rightarrow \infty }\Vert (U_{\overline{\mathcal {L}_1}}-e^{i\xi })\psi _n\Vert =0$. Let $f_n = d_A \psi _n$. Assume that $\lim _{n \rightarrow \infty }f_n = 0$, which implies $\lim _{n \rightarrow \infty } d_A^{*}d_A \psi _n = \lim _{n \rightarrow \infty } d_A^{*} f_n = 0$ and hence

$$\begin{aligned} \langle U\psi _n, e^{i\xi } \psi _n \rangle = e^{i\xi } \langle S(2d_A^{*}d_A - 1) \psi _n, \psi _n \rangle = -e^{i\xi } \langle S \psi _n, \psi _n \rangle + o(1). \end{aligned}$$

By the definition of $\psi _n$, we have

$$\begin{aligned} \langle U\psi _n, e^{i\xi } \psi _n \rangle = \langle U\psi _n, U\psi _n \rangle + \langle U\psi _n, (e^{i\xi } - U) \psi _n \rangle = 1 + o(1). \end{aligned}$$

Combining the above two equations, we obtain

$$\begin{aligned} \lim _{n \rightarrow \infty } \langle S \psi _n, \psi _n \rangle = - e^{-i\xi }. \end{aligned}$$

(6.1)

Because S is self-adjoint, (6.1) is allowed only when $\xi = 0, \pi$.

Let us first consider the case in which $\xi \in (0, \pi ) \cup (\pi , 2\pi )$. Then, $f_n$ does not converge to zero, because, from the above argument, (6.1) contradicts $\lim _{n \rightarrow \infty }f_n = 0$. Hence, there exists a subsequence $\{f_{n_k}\}$ such that $\inf _k \Vert f_{n_k}\Vert = :c >0$ holds. We write $f_{n_k} =d_A \psi _{n_k}$ simply as $f_k = d_A \psi _k$. Then, we observe that

$$\begin{aligned} T f_k&= d_B (d_A^{*} d_A) \psi _k = d_A S \left( \frac{C + 1}{2}\right) \psi _k = d_A \left( \frac{U + S}{2}\right) \psi _k \nonumber \\&= \frac{1}{2} d_A ( e^{i\xi } + S )\psi _k + o(1). \end{aligned}$$

(6.2)

We also observe that

$$\begin{aligned} S\psi _k&= e^{-i\xi } S(e^{i\xi }\psi _k) = e^{-i\xi } S(U\psi _k) + o(1) \nonumber \\&= e^{-i\xi } C\psi _k + o(1). \end{aligned}$$

(6.3)

Combining (6.3) with (6.2), and using the fact that $d_A C = d_A$, we obtain

$$\begin{aligned} T f_k = \frac{1}{2} d_A ( e^{i\xi } + e^{-i\xi } C )\psi _k + o(1) = (\cos \xi ) f_k + o(1). \end{aligned}$$

Let $\tilde{f}_k := f_k/\Vert f_k\Vert$. Then, we know that $\Vert \tilde{f}_k\Vert =1$, and that

$$\begin{aligned} \Vert (T - \cos \xi )\tilde{f}_k\Vert \le \frac{1}{c} \Vert (T - \cos \xi ) f_k\Vert = o(1), \end{aligned}$$

where $c=\inf _k\Vert f_k\Vert >0$. Thus, we obtain

$$\begin{aligned} \sigma (U_{\overline{\mathcal {L}_1}}) {\setminus } \{-1, 1\} \subset \{ e^{i\xi } \mid \cos \xi \in \sigma (T), \ \xi \in (0,\pi ) \cup (\pi ,2\pi ) \}. \end{aligned}$$

This implies (1), because

$$\begin{aligned} \sigma (U_{\overline{\mathcal {L}_1}})&= \left( \sigma (U_{\overline{\mathcal {L}_1}}) {\setminus } \{-1, 1\} \right) \cup \left( \sigma (U_{\overline{\mathcal {L}_1}}) \cap \{-1, 1\} \right) \\&\subset \{ e^{i\xi } \mid \cos \xi \in \sigma (T), \ \xi \in (0,\pi ) \cup (\pi ,2\pi ) \} \cup \{-1,1\}. \end{aligned}$$

To prove (2), we write $\{ e^{i\xi } \mid \cos \xi \in \sigma (T), \ \xi \in [0, 2\pi ) \} {\setminus } K = I_1 \cup I_2$, where $I_1 :=\{ e^{i\xi } \mid \cos \xi \in \sigma (T), \ \xi \in (0, \pi ) \cup (\pi , 2\pi ) \}$ and $I_2 := \Sigma _T \cap \{+1,-1\}$ with $\Sigma _T =\sigma (T) {\setminus } \sigma _\mathrm{p}(T)$. Therefore, it suffices to show that $I_i \subset \sigma (U_{\overline{\mathcal {L}_1}})$ ($i=1,2$).

Assume that $e^{i\xi } \in I_1$. Then we know that $\cos \xi \in \sigma (T) \cap (-1,1)$ and that there exists a sequence $\{ f_n \} \subset \mathcal {K}$ such that $\Vert f_n\Vert =1$ and $\lim _{n \rightarrow \infty }\Vert (T-\cos \xi )f_n\Vert = 0$. We observe that $\psi _n:=(1-e^{i\xi }S) d_A^{*} f_n \in \mathcal {L}_1$ and that

$$\begin{aligned} \Vert \psi _n\Vert ^2&= 2\Vert d_A^{*} f_n\Vert ^2 -2\mathrm{Re}(e^{i\xi } \langle d_A^{*} f_n, Sd_A^{*}f_n \rangle ) \\&= 2 - 2 \cos \xi \langle f_n, Tf_n \rangle = 2(1-\cos ^2 \xi ) + o(1). \end{aligned}$$

Because $\lim \inf _{n\rightarrow \infty } \Vert \psi _n\Vert ^2 = 2(1-\cos ^2 \xi ) > 0$, $\psi _n$ does not converge to zero. Hence, taking a subsequence if needed, we can assume that $\inf _n \Vert \psi _n\Vert =: c > 0$. Then we have

$$\begin{aligned} U \psi _n&= U(1-e^{i\xi }S) d_A^{*} f_n = d_B^{*} f_n - e^{i\xi }(2d_B^{*} T -d_A^{*})f_n \\&= (1 - 2e^{i\xi } \cos \xi )d_B^{*} f_n + e^{i\xi }d_A^{*}f_n + o(1) \\&= (- e^{2i\xi } S + e^{i\xi })d_A^{*}f_n + o(1) = e^{i\xi } \psi _n + o(1). \end{aligned}$$

Let $\tilde{\psi }_n : = \psi _n/\Vert \psi _n\Vert$. Then, from an argument similar to the above, we obtain $e^{i\xi } \in \sigma (U_{\overline{\mathcal {L}_1}})$. Thus $I_1 \subset \sigma (U_{\overline{\mathcal {L}_1}})$ is proved.

Let $\pm \,1 \in I_2$. Then $\pm \,1 \in \Sigma _T$ and hence $\pm \,1$ can not be an isolated point of $\sigma (T)$. Hence there exists a sequence $\{ \cos \xi _n \} \subset \sigma (T) \cap (-1, 1)$ such that $\lim _{n \rightarrow \infty } \cos \xi _n = \pm 1$. Because $\lim _{n \rightarrow \infty } e^{i\xi _n} = \pm 1$ and $e^{i\xi _n} \in I_1$, from the above result, we know that $e^{i\xi _n} \in \sigma (U_{\overline{\mathcal {L}_1}})$. Because $\sigma (U_{\overline{\mathcal {L}_1}})$ is a closed set, we have $\pm \, 1\in \sigma (U_{\overline{\mathcal {L}_1}})$. Thus $I_2 \subset \sigma (U_{\overline{\mathcal {L}_1}})$ is proved. $\square$

7 Concluding remark

In this paper, we clarified that the involutivity of the shift operator and coisometricity of the boundary map cause the reduction of the spectral analysis of the unitary operator to one of the underlying self-adjoint operator. This result implies that the spectral mapping theorem can be applied to general infinite graphs. As is seen in Introduction, if the underlying symmetric random walk on an infinite graph has only the point spectrum, e.g., the Sierpiński lattice, then the induced Grover walk also has only the point spectrum (without continuous spectrum). This concludes that the induced Grover walk exhibits localization for any initial state. In a companion paper [24], we clarify a relationship between the spectrum and stochastic behavior of our abstractive quantum walk.