#  A comfortable graph structure for Grover walk

Yusuke Higuchi Department of Mathematics, Gakushuin University, Tokyo
171-8588, Japan  Mohamed Sabri and Etsuo Segawa Graduate School of Information
Sciences, Tohoku University, Aoba, Sendai 980-8579, Japan Graduate School of
Environment and Information Sciences, Yokohama National University, Hodogaya,
Yokohama 240-8501, Japan

Abstract. We consider a Grover walk model on a finite internal graph, which is
connected with a finite number of semi-infinite length paths and receives the
alternative inflows along these paths at each time step. After the long time
scale, we know that the behavior of such a Grover walk should be stable, that
is, this model has a stationary state. In this paper our objectives are to
give some characterization upon the scattering of the stationary state on the
surface of the internal graph and upon the energy of this state in the
interior. For the scattering, we concretely give a scattering matrix, whose
form is changed depending on whether the internal graph is bipartite or not.
On the other hand, we introduce a comfortability function of a graph for the
quantum walk, which shows how many quantum walkers can stay in the interior,
and we succeed in showing the comfortability of the walker in terms of
combinatorial properties of the internal graph.

Keywords: Quantum walk, (pseudo-)Kirchhoff’s laws, (signless-)Laplacian,
Comfortability

##  1 Introduction

As discrete-time quantum walks on graphs are being studied, many interesting
behaviors of quantum walks, which cannot be observed in the classical random
walk setting, have become apparent: the accomplishment of quantum speed up in
quantum algorithm, linear spreading, localization, periodicity, pseudo-perfect
state transfer and so on (see [18, 20, 22] and references therein). Among them
it is revealed that behaviors of quantum walks are closely related to
geometric features of graphs; for examples, cycle geometry of graphs gives the
localization [14, 16], a three-edge-coloring induces an eigenfunction of some
quantum walks [21], and the rotation systems and 1-factorizations of graphs
are reflected on the mixing time of quantum walks [12]. For a family of graphs
with fractal structure, the spectral analysis reflects on its property for the
hopping matrix [7] and the continuous-time quantum walk [3] are studied. In
[9], the scattering for a tree with two semi-infinite lines appended is
discussed under the time evolution of continuous-time quantum walk to
investigate the quantum exponentially speed up of the hitting time to the
marked vertex. In this paper, we observe what property of general graphs are
extracted from the structure of the stationary state of discrete-time quantum
walks. The stationary state, which is a kind of the long time behavior of
quantum walk, has been discussed in [10, 11, 17].

Let us explain our setting. For a connected and locally finite graph
$G=(V,E)$, which may be infinite, let us define the set of symmetric arcs $A$
induced by $E$ as follows: for any undirected edge $e\in E$ with end vertices
$u,v\in V$, the induced arcs are $a$ and $\overline{a}$, which are arcs from
$u$ to $v$ and $v$ to $u$ along the edge $e\in E$, respectively. The terminus
and origin vertices of $a\in A$ are denoted by $t(a),\,o(a)\in V$,
respectively. The total space of quantum walk treated here is denoted by
$\mathbb{C}^{A}$, which is a vector space whose standard basis are labeled by
$A$. In other words, $\mathbb{C}^{A}\cong\\{\psi:A\to\mathbb{C}\\}$ is spanned
by $\left\\{\delta_{a}:a\in A\right\\}$, where $\delta_{a}(\cdot)$ is the
delta function such that

$\delta_{a}(a^{\prime})=\begin{cases}1&\text{if }a=a^{\prime},\\\
0&\text{otherwise}.\end{cases}$

The time evolution operator of a quantum walk
$U:\mathbb{C}^{A}\to\mathbb{C}^{A}$ is defined by

$U=SC.$

Here $S\delta_{a}=\delta_{\overline{a}}$ and $C=\bigoplus_{v\in V}C_{v}$,
where $C_{v}$ is a local coin operator assigned at vertex $v$ which is a
$\text{deg}(v)$-dimensional unitary matrix on
$\text{span}\left\\{\delta_{a}:t(a)=v\right\\}$. Note that since the time
evolution operator $U$ is unitary in the sense that $UU^{*}=I$, then for any
$\psi\in\mathbb{C}^{A}$, the $l^{2}$ norm is preserved, that is,
$||U\psi||^{2}=||\psi||^{2}=\sum_{a\in A}|\psi(a)|^{2}$ for the standard inner
product. Let $\psi_{n}$ be the $n$-th iteration of $U$ with the initial state
$\psi_{0}$; that is, $\psi_{n+1}=U\psi_{n}$. We call
$\psi_{\infty}(a):=\lim_{n\to\infty}\psi_{n}(a)$ for any $a\in A$, if it
exists, the stationary state. Another type of stationarity of quantum walks,
the stationary measure, is discussed in [19], whose form is as follows:
$\mu(\psi_{n+1})(u):=\sum_{t(a)=u}|\psi_{n+1}(a)|^{2}=\sum_{t(a)=u}|\psi_{n}(a)|^{2}$
for any time step $n=0,1,2,\dots$ and vertex $u\in V$.

We are interested in how the state converges to the stationary state as a
fixed point of a dynamical system. In general, the state of the walker in a
quantum walk on a finite graph $G_{0}=(V_{0},A_{0})$ does not necessarily
converge because the time evolution operator is unitary and hence the absolute
values of the eigenvalues of the operator are equal to $1$. Then we connect
semi-infinite paths, say tails, to a subset of vertices of $\delta V\subset
V_{0}$ in the finite graph $G_{0}$, which is called the surface. Moreover the
$l^{\infty}$-initial state $\Phi_{0}$ is set so that a quantum walker along
the tails come into the internal and a quantum walker goes out from that at
every time step. See (1) for the detailed definition of the initial state and
also Fig. 1. It is expected that the outflow balances the inflow in the long
time limit and this quantum walk on this graph goes to a steady state. Indeed
the convergence of states, in this sense, is shown in [10, 11, 17]. In this
setup, the state space of the walk is described by $l^{\infty}$-space. This
quantum walk always converges to a stationary state whenever we choose
vertices of the internal, to which the tails are connected.

In [15, 17], the Grover walk whose quantum coins are expressed by the Grover
matrices $\left\\{\mathrm{Gr}(\text{deg}(u)\right\\}_{u\in V}$ was applied
with the constant inflow. Then the scattering on the surface $\delta V$, which
is a set of vertices connected to tails, in the long time limit recovers the
local scattering at each vertex; that is, the scattering matrix is
$\mathrm{Gr}(r)$, where $r$ is the number of tails. This implies that we can
obtain the global scattering by only some information on the surface,
especially the number $r$, whereas this also implies that we cannot obtain any
information on the structure of the internal graph $G_{0}$.

Our motivation is to investigate how the geometrical structure of the internal
graph affects the behavior of quantum walkers in terms of their stationary
states. For this purpose, we must change something in our setting; for
example, we replace a constant flow, which was studied in [15, 17], with some
oscillated one. In this study, as a first trial, we focus on the simplest
oscillation of the inflow with alternating signs which is a coarse graining of
alternating current input. Our interest is to find a graph geometry from the
scattering on the surface and also the energy in the interior in the long time
limit. See Figure 1.

Figure 1: The time evolution of the quantum walk with the alternative inflow:
The surface of the internal graph is the set of vertices in $K_{3}$ connected
to the tails. At time $n=0$, we set the initial state $\Phi_{0}$ with
alternating signs on the tails represented by
$\bm{\alpha}=[\alpha_{1},\alpha_{2}]^{\top}=[9,9]^{\top}$. The time evolution
is determined by the Grover matrices assigned at each vertex: for each vertex
$u$ and each time step, the transmitting weight is $2/\deg(u)$ while the
reflection weight is $2/\deg(u)-1$. Then on the tails, the dynamics is free
because $\deg(u)=2$ while in the internal graph, the time evolution is not
trivial. For example, see the middle of the figure, at time $n=1$ and at the
vertex connecting to the left tail, say $u_{*}$, a quantum walker who came
from the tail with the amplitude “$9$” at the previous time is transmitted to
the internal graph with the amplitude $9\times 2/\deg(u_{*})=9\times 2/3=6$,
while reflected to the tails with the amplitude $9\times(2/\deg(u_{*})-1)=-3$.
Because of the setting of the initial state and free dynamics on the tails,
the internal graph receives the inflow from the tails and also radiates the
outflow to the tails at every time step.

The scattering on the surface gives how the inflows map to the outflows on the
surface. This answer is given in following.

######  Theorem 1.

Let $\bm{\alpha}$ and $\bm{\beta}$ represent the inflow and outflow of the
stationary state on the surface $\delta V$. Their details can be seen in
Definition 1. Then we have

$\bm{\beta}=\sigma\bm{\alpha},$

where the scattering matrix $\sigma$ is unitary and described by

$\sigma=\begin{cases}I&\text{: $G_{0}$ is non-bipartite,}\\\ \tau&\text{:
$G_{0}$ is bipartite.}\end{cases}$

Here $I$ is the identity matrix and $\tau$ is described as in Section 3.

From this theorem, if the interior is non-bipartite, the scattering is the
perfect reflection, while if the interior is bipartite, the scattering is
described by the Grover matrix. Then in contrast with results in [15, 17], we
succeed in extracting a structure of the internal graph from the scattering on
the surface; that is, the bipartiteness.

Next it is natural to ask what happens to the interior. To answer this
question, we introduce the idea of comfortability. The comfortability is the
function of the interior, and gives how quantum walkers accumulate in the
internal graph in the long time limit, which is the energy stored the
interior. The notion of the comfortability for quantum walk is an analogy of
the energy in the electric circuit [8]. The detailed definition of the
comfortability $\mathcal{E}_{QW}(G_{0})$ is described in Definition 2. We
obtain that when only two tails are connected, the comfortability of the graph
can be expressed in terms of the geometric information of the graph as
follows.

######  Theorem 2.

Assume the number of tails is $2$, and the inflow
$\bm{\alpha}=[\alpha_{1},\alpha_{2}]^{\top}=[1,0]^{\top}$. Then the
comfortability $\mbox{\Large$\varepsilon$}_{QW}(G_{0})$ of the quantum walk is
given by

$\mbox{\Large$\varepsilon$}_{QW}(G_{0})=\begin{cases}\left(\chi_{2}(G_{0})/\chi_{1}(G_{0})+|E_{0}|\right)/4&\text{
: }G_{0}\text{ is bipartite,}\\\ \iota_{2}(G_{0})/\iota_{1}(G_{0})&\text{ :
}G_{0}\text{ is non-bipartite.}\end{cases}$

Here $|E_{0}|$ is the number of edges of $G_{0}$, $\chi_{1}(G_{0})$ is the
number of the spanning trees of $G_{0}$ and $\chi_{2}(G_{0})$ is the number of
the spanning forests of $G_{0}$ with two components in which one contains
$u_{1}$ and the other contains $u_{n}$. The geometric quantities of
$\iota_{1}(G_{0})$ and $\iota_{2}(G_{0})$ are defined in Section 3.

Under the condition where the outflow balances the inflow whose amplitude is
constant, we can control the amount of energy stored in the interior by tuning
the oscillation of the inflow according to the geometric structure. We
illustrate the ranking of the comfortability among all of the graphs with four
vertices in Section 4. To show the above theorem, we first define a
(pseudo-)current function [15, 17] on a (non-)bipartite graph and we show that
these functions satisfy the (pseudo-)Kirchhoff laws in Theorems 5 and 6,
respectively. Secondly, we obtain a potential function with respect to these
(pseudo-)current functions, in terms of (signless-)Laplacian matrix in [2, 4]
and Theorem 8, respectively. Thirdly, using these expressions of the potential
functions, we obtain expressions for the comfortability in terms of the
(non-)oriented incident matrix and the (signless-)Laplacian matrix, when the
graph is (non-)bipartite in Propositions 1 and 2. Finally, using the
speciality of the setting, we obtain the expression of the comfortability
using the graph factors induced quantum walks defined by Definition 3.

We arrange the rest of this paper in the following way. In section 2, we
introduce the setting, notations and some previously known results in our
model. Moreover, we define the scattering matrix of the walk and a
comfortability function of the graph. In section 3, we introduce our main
results of the paper: Theorems 1 and 2 which tells information on the
scattering matrix and the comfortability function, respectively. These
theorems depends on the bipartiteness of graphs. Furthermore, we note that the
theorem on the comfortability gives a method to compute the comfortability of
the graph in terms of the geometric information of the graph. In section 4, we
give an example to illustrate the comfortability of the graphs with 4 vertices
and we show the comparison of the comfortabilities. In section 5, we give the
proofs of our main theorems, Theorems 1 and 2.

##  2 Setting

Let $G_{0}=(V_{0},E_{0})$ be a finite connected graph and $A_{0}$ be the
symmetric arc set induced by $E_{0}$. We choose the boundary(surface) of
$G_{0}$, $\emptyset\neq\delta V\subset V_{0}$ with $\delta
V=\\{v_{1}^{(0)},...,v_{r}^{(0)}\\}$, where $v_{i}^{(0)}\neq v_{j}^{(0)}$ if
and only if $i\neq j$. Let $\left\\{\mathbb{P}_{j}:j=1,...,r\right\\}$ be the
set of semi-infinite length paths called the tails each end vertex of which is
denoted by $v_{j}^{(0)}$, and each of which is connected to the finite graph
$G_{0}$ such that $V(\mathbb{P}_{j})=\left\\{v_{j}^{(0)}\sim v_{j}^{(1)}\sim
v_{j}^{(2)}\sim...\right\\}$. Here $u\sim v$ means that the vertices $u$ and
$v$ are adjacent. We denote the constructed graph by
$\tilde{G}=(\tilde{V},\tilde{E})$. We also denote the arc set induced by
$E_{0}$ and $\tilde{E}$ by $A_{0}$ and $\tilde{A}$ respectively. For any arc
$a=(u,v)\in\tilde{A}$, we write $\overline{a}=(v,u)$, $o(a)=u$ and $t(a)=v$.
Remark that $o(\overline{a})=t(a)$ and $t(\overline{a})=o(a)$.

For a discrete set $\Omega$, let us define $\mathbb{C}^{\Omega}$ by the vector
space whose basis are labeled by each element of $\Omega$. The total state
space associated with the quantum walk treated here is
$\mathbb{C}^{\tilde{A}}$. We define the time evolution operator $W$ on
$\mathbb{C}^{\tilde{A}}$ in the matrix form by

$(W)_{a,b}=\begin{cases}\left(\dfrac{2}{\text{deg}(o(a))}-\delta_{a\overline{b}}\right)&\text{
if }\,o(a)=t(b),\\\ 0&\text{otherwise},\end{cases}$

which is so called the Grover walk. Note that the walk becomes “free” on the
tails; that is,

$(W)_{a,b}=\begin{cases}1&\text{: $o(a)=t(b)$, $a\neq\overline{b}$,}\\\
0&\text{: otherwise}\end{cases}$

for any $o(a)\notin V_{0}$. We set the $l^{\infty}$-initial state by using a
complex value $z$ with $|z|=1$:

$\Phi_{0}(a)=\begin{cases}z^{-\text{dist}(v_{j}^{(0)},\;t(a))}\alpha_{j}&\text{if
}o(a)=v_{j}^{(s+1)},\,t(a)=v_{j}^{(s)},\,s=0,1,2,...,\,j=1,2,...,r,\\\ \\\
0&\text{otherwise}.\end{cases}$ (1)

Here $\alpha_{j}\in\mathbb{C}$ $(j=1,\dots,r)$ and $\mathrm{dist}(u,v)$ is the
shortest length of paths in $\tilde{G}$ between vertices $u$ and $v$. Then
quantum walkers inflows into the internal graph $G_{0}$ at every time step $n$
from the tails. On the other hand, a quantum walker outflows towards the tails
from the internal graph.

Let $\Phi_{n}\in\mathbb{C}^{\tilde{A}}$ be the $n$-th iteration of the quantum
walk such that $\Phi_{n+1}=W\Phi_{n}$. Since the inflow oscillates with
respect to the time step, the total state does not converge in the long time
limit. We put $\Phi_{n}^{\prime}:=z^{n}\Phi_{n}$, which satisfies
$\Phi_{n+1}^{\prime}=zW\Phi_{n}^{\prime}$. The convergence of
$\Phi_{n}^{\prime}$ is ensured by [17] as follows.

######  Theorem 3 ([17]).

$\Phi_{\infty}^{\prime}:=\lim\limits_{n\rightarrow\infty}\Phi_{n}^{\prime}$
exists; that is, $W\Phi_{\infty}^{\prime}=z^{-1}\Phi_{\infty}^{\prime}$.

Let us focus on the dynamics restricted to the internal graph. To this end, we
define the boundary operator of $A_{0}$,
$\chi:\mathbb{C}^{\tilde{A}}\rightarrow\mathbb{C}^{A_{0}}$ by,

$(\chi\tilde{f})(a)=\tilde{f}(a),a\in A_{0}$

for any $\tilde{f}\in\mathbb{C}^{\tilde{A}}$. The adjoint
$\chi^{*}:\mathbb{C}^{A_{0}}\rightarrow\mathbb{C}^{\tilde{A}}$ is described by

$(\chi^{*}f)(a)=\begin{cases}f(a)&\text{if}\,a\in A_{0},\\\
0&\text{otherwise}\end{cases}$

for any $f\in\mathbb{C}^{A_{0}}$. Remark that
$\chi\chi^{*}:\mathbb{C}^{A_{0}}\rightarrow\mathbb{C}^{A_{0}}$ is the identity
operator on $\mathbb{C}^{A_{0}}$ and
$\chi^{*}\chi:\mathbb{C}^{\tilde{A}}\rightarrow\mathbb{C}^{\tilde{A}}$ is the
projection operator on $\mathbb{C}^{\tilde{A}}$ with respect to $A_{0}$.
Putting $\chi\Phi_{n}^{\prime}=:\phi_{n}^{\prime}$ and $\chi W\chi^{*}=:E$, we
have

$\phi_{n+1}^{\prime}=zE\phi_{n}^{\prime}+\rho,\;\phi_{0}^{\prime}=0,$ (2)

where $\rho=\chi W\Phi_{0}$. The dynamical system given by (2) can be also
accomplished by the restriction to the internal graph of the following
alternating quantum walk for $z=-1$ case: the time evolution operator of the
alternating quantum walk
$U:\mathbb{C}^{\tilde{A}}\rightarrow\mathbb{C}^{\tilde{A}}$ is defined in the
matrix form by

$(U)_{a,b}=\begin{cases}(-1)^{\mathbbm{1}_{V_{0}}(o(a))}\left(\dfrac{2}{\text{deg}(o(a))}-\delta_{a\overline{b}}\right)&\text{
if }\,o(a)=t(b),\\\ 0&\text{otherwise},\end{cases}$ (3)

where $\mathbbm{1}_{V_{0}}$ is the characteristic function of $V_{0}$. The
quantum coin assigned at every vertex in the internal graph is the “signed”
Grover matrix. The initial state of the walker is

$\Psi_{0}(a)=\begin{cases}\alpha_{j}&\text{if}\,o(a)=v_{j}^{(s+1)},\,t(a)=v_{j}^{(s)},\,s=0,1,2,...,\,j=1,...,r,\\\
\\\ 0&\text{otherwise}.\end{cases}$ (4)

In this paper, we consider $\Psi_{n+1}=U\Psi_{n}$ instead of $\Phi_{n}$. Since
$\Psi_{\infty}:=\lim_{n\to\infty}\Psi_{n}$ exists and
$U\Psi_{\infty}=\Psi_{\infty}$ holds according to [17], we compute its
stationary state. In particular, we focus on the following quantities.

######  Definition 1.

Scattering matrix: Let
$\bm{\alpha}:=\left[\alpha_{1},\alpha_{2},...,\alpha_{r}\right]^{T},\,\bm{\beta}:=\left[\beta_{1},\beta_{1},...,\beta_{r}\right]^{T}$,
where $\beta_{j}=\Psi_{\infty}(a)$ with $o(a)=v_{j}^{(0)},\,t(a)=v_{j}^{(1)}$.
The scattering matrix $\sigma$, which is a $r$-dimensional unitary matrix, is
defined by

$\bm{\beta}=\sigma\bm{\alpha}.$

The existence of such a unitary matrix is ensured by [10, 11]. If $z=1$, the
scattering matrix gives us only the information of the number of tails because
the scattering matrix for $z=1$ is expressed by $\mathrm{Gr}(r)$ [15]. In this
paper, if $z=-1$, we obtain the information on the internal graph in Theorem
1. We are also interested in the stationary state in the internal graph,
especially how many quantum walkers exist; that is, how quantum walkers feel
comfortable to the graph.

######  Definition 2.

The comfortability of $G_{0}$ with $\bm{\alpha}$ with $\delta V$ for quantum
walker :

$\mathcal{E}_{QW}(G_{0};\bm{\alpha},\delta V)=\frac{1}{2}\sum_{a\in
A_{0}}|\Psi_{\infty}(a)|^{2}.$

We extract some geometric graph structures from these quantities which derive
from some quantum effects in Theorem 2.

##  3 Main Results

Now we state a main theorem concerning the scattering on the surface, which
gives a quantum walk method to characterize bipartite graphs. For example, let
us consider a graph with two tails and we set the inflow one of them.
According to the following theorem, we can determine the bipartiteness of the
graph from the scattering way: if the scattering is the perfect reflecting,
then the graph is non-bipartite, while the scattering is the perfect
transmitting, then the graph is bipartite.

######  Theorem 1.

(Scattering on the surface) Assume the time evolution operator is described by
(3). For the stationary state $\Psi_{\infty}$, let
$\bm{\alpha}:=\left[\alpha_{1},\alpha_{2},...,\alpha_{r}\right]^{T}$ and
$\bm{\beta}:=\left[\beta_{1},\beta_{1},...,\beta_{r}\right]^{T}$, where
$\alpha_{j}$ is the inflow described by (4) and $\beta_{j}$ is the outflow
described by $\beta_{j}=\Psi_{\infty}(a)$ with
$o(a)=v_{j}^{(0)},\,t(a)=v_{j}^{(1)}$. Then the scattering matrix, which is an
$r$-dimensional unitary matrix; $\bm{\beta}=\sigma\bm{\alpha}$, is expressed
as follows.

$\sigma=\begin{cases}I&\text{: $G_{0}$ is non-bipartite,}\\\ \tau&\text{:
$G_{0}$ is bipartite.}\end{cases}$

Here $I$ is the identity matrix and $\tau$ is described as follows:

$\tau=-\begin{bmatrix}I_{k}&0\\\
0&-I_{r-k}\end{bmatrix}\mathrm{Gr}(r)\begin{bmatrix}I_{k}&0\\\
0&-I_{r-k}\end{bmatrix}$

with the computational basis labeled by
$\left\\{v_{1}^{(0)},...,v_{k}^{(0)},v_{k+1}^{(0)},...,v_{r}^{(0)}\right\\}$,
where $v_{1}^{(0)},...,v_{k}^{(0)}\in X\cap\delta V$ and
$v_{k+1}^{(0)},...,v_{r}^{(0)}\in Y\cap\delta V$.

######  Remark 1.

If we set the inflow to a bipartite graph with the partite sets $X$ and $Y$ so
that total inflow to the partite set $X$ coincides with that to the partite
set $Y$, the perfect reflecting happens. This means that we can not detect the
bipartiteness of graph with such an initial state. These inputs vectors are
described by eigenvectors of the scattering matrix $\tau$ with the eigenvalue
$1$.

We express the total energy in the interior, comfortability, in terms of the
combinatorial geometry of finite graphs. To state our claim, we prepare some
notations and settings. The odd unicyclic graph is the graph which contains
only one cycle whose length is odd. Now let us consider the case where two
tails are connected to $G_{0}$ at $u_{1}$ and $u_{n}$ $(u_{1}\neq u_{n})$, and
set the inflow to $u_{1}$ and $u_{n}$ by
$\bm{\alpha}=(\alpha_{1},\alpha_{2})=(1,0)$. Here $n$ is the number of
vertices of $G_{0}$. In this case, the comfortability is described by
$\mathcal{E}_{QW}(G_{0};\bm{\alpha},\delta
V)=:\mathcal{E}_{QW}(G_{0};u_{1},u_{n})$.

######  Definition 3.

(Important graph factors) Let $\chi_{1}(G_{0})$ be the number of spanning
trees of $G_{0}$ and $\chi_{2}(G_{0};u_{1},u_{n})$ be the number of spanning
forests of $G_{0}$ with exactly two components, one containing $u_{1}$ and the
other containing $u_{n}$. Here the isolate vertex is regarded as a tree.
Define the set of odd unicyclic spanning subgraphs of $G_{0}$ by

$\mathcal{C}_{o}=\cup_{r\geq 1}\;\\{\\{C_{1},...,C_{r}\\}\;|\;C_{i}\text{'s
are odd unicyclic graphs}\\}$

and the set of spanning subgraphs of $G_{0}$ whose one component is a tree $T$
which contains $u_{1}$ and the remaining components are odd unicyclic graphs
by

$\mathcal{T}\mathcal{C}_{o}=\cup_{k\geq
0}\;\\{\\{T,C_{1},...,C_{k}\\}\;|\;u_{1}\in T\text{ where }T\text{ is a tree
and }C_{i}\text{'s are odd unicyclic graphs}\\}.$

Here the situation $k=0$ is the set of spanning trees of $G_{0}$. See Figure
2. Now define the functions $\iota_{1}$ and $\iota_{2}$ by

$\iota_{1}(G_{0})=\sum\limits_{H\in\mathcal{C}_{o}}4^{\omega(H)}$

and

$\iota_{2}(G_{0};u_{1})=\sum\limits_{H\in\mathcal{T}\mathcal{C}_{o}}4^{\omega(H)-1},$

where $\omega(H)$ is the number of components in $H$.

Then with the above notations, we have another main theorem of our paper as
follows.

######  Theorem 2.

(Comfortability in the interior) Assume the number of tails is $2$, and the
inflow $\bm{\alpha}=(\alpha_{1},\alpha_{2})=(1,0)$ at $u_{1}$ and $u_{n}$,
respectively. Then the comfortability of the quantum walk (3) is given by

$\mbox{\Large$\varepsilon$}_{QW}(G_{0};u_{1},u_{n})=\begin{cases}\dfrac{1}{4}\left(\dfrac{\chi_{2}(G_{0};u_{1},u_{n})}{\chi_{1}(G_{0})}+|E_{0}|\right)&\text{
if }G_{0}\text{ is bipartite,}\\\ \\\
\dfrac{\iota_{2}(G_{0};u_{1})}{\iota_{1}(G_{0})}&\text{ if }G_{0}\text{ is
non-bipartite.}\end{cases}$

Then we can determine how much quantum walker feels comfortable to the given
graph by listing up the spanning subgraphs in Definition 3 of this graph. We
will demonstrate it for the graphs with four vertices in the next section.

######  Theorem 4.

Assume the number of tails is $2$, and the inflow
$\bm{\alpha}=(\alpha_{1},\alpha_{2})=(1,0)$ at $u_{1}$ and $u_{n}$,
respectively. Then the comfortability of the quantum walk discussed in [17],
that is, $z=1$ in (2), is given by

$\mbox{\Large$\varepsilon$}_{QW}(G_{0};u_{1},u_{n})=\dfrac{1}{4}\left(\dfrac{\chi_{2}(G_{0};u_{1},u_{n})}{\chi_{1}(G_{0})}+|E_{0}|\right).$

The proof of Theorem 4 is essentially same as in the proof of Theorem 2 for
the bipartite graph case.

Figure 2: $\mathcal{C}_{o}$-factor and $\mathcal{T}\mathcal{C}_{o}$-factor of
$K_{4}$: The white colored vertex in the complete graph $K_{4}$ corresponds to
$u_{1}$. The left figure depicts the list of the family of odd unicyclic
factor of $K_{4}$ and the right figure depicts the list of the
$\mathcal{T}\mathcal{C}_{o}$-factor of $K_{4}$. Note that the isolated vertex
is regards as a tree and the family of the spanning tree is included in
$\mathcal{T}\mathcal{C}_{o}$.

##  4 Example

As an example to our result in Theorem Theorem 2, we consider the connected
graphs with $4$ vertices labeled by
$\left\\{u_{1},u_{2},u_{3},u_{4}\right\\}$. The setting is the same as in
Theorem Theorem 2 and we choose the inflow $\bm{\alpha}=(1,0)$ at the vertices
$u_{1}$ and $u_{4}$, respectively. We classify these graphs into $10$ classes
based on the number of edges, bipartiteness and the configuration of $u_{1}$
and $u_{4}$ and the numbers of important factors state in Definition 3. Note
that the comfortability for the non-bipartite case depends only on $u_{1}$. We
conclude that every graph with $4$ vertices belongs to exactly one of the
following classes (see Fig 3):

$\mathcal{G}_{1}=\left\\{K_{4}\right\\},$
$\mathcal{G}_{2}=\left\\{K_{4}-u_{1}u_{j}:j=2,3,4\right\\},$
$\mathcal{G}_{3}=\left\\{K_{4}-u_{i}u_{j}:i,j=2,3,4\right\\},$
$\mathcal{G}_{4}=\left\\{C_{4}:u_{1}\sim u_{4}\right\\},$
$\mathcal{G}_{5}=\left\\{C_{4}:u_{1}\nsim u_{4}\right\\},$
$\mathcal{G}_{6}=\left\\{G:G\text{ is constructed by joining }u_{1}\text{ to
exactly one vertex in the cycle }u_{2},u_{3},u_{4}\right\\},$
$\mathcal{G}_{7}=\left\\{G:G\text{ is constructed by joining
}u_{i}(i=2,3,4)\text{ to exactly one vertex in the cycle
}u_{1},u_{k},u_{l}(k,l\neq 1,i)\right\\},$ $\mathcal{G}_{8}=\left\\{T:T\text{
is a tree with }\text{dist}(u_{1},u_{4})=1\right\\},$
$\mathcal{G}_{9}=\left\\{T:T\text{ is a tree with
}\text{dist}(u_{1},u_{4})=2\right\\},$ $\mathcal{G}_{10}=\left\\{T:T\text{ is
a tree with }\text{dist}(u_{1},u_{4})=3\right\\}.$

Here $K_{4}-u_{i}u_{j}$ is the graph obtained by removing the edge
$u_{i}u_{j}$ from $K_{4}$. Now for $G_{i}\in\mathcal{G}_{i}(i=1,...,10)$, we
compute $\mbox{\Large$\varepsilon$}_{QW}$ as follows. When $G_{0}=K_{4}$ for
example, since $K_{4}$ is non-bipartite, we have

$\mbox{\Large$\varepsilon$}_{QW}(K_{4})=\dfrac{\iota_{2}(K_{4};u_{1})}{\iota_{1}(K_{4})}.$

To compute $\iota_{1}(K_{4})$, we need to find the number of odd unicyclic
subgraphs which span $K_{4}$. The only such possible subgraph is a $3$-cycle
with an additional edge. It is clear that there are $4$ ways to choose a
$3$-cycle and for a chosen $3$-cycle, there are $3$ ways to choose an edge
which connects the remaining vertex to the cycle. Hence, altogether there are
$12$ such subgraphs, which are shown as $\mathcal{C}_{o}$ in the figure 2.
Observe that each subgraph has only one component and hence we have

$\iota_{1}(K_{4})=48.$

Now to compute $\iota_{2}(K_{4};u_{1})$, we have to find the spanning
subgraphs which contains a tree with $u_{1}$ and the remaining are odd cycles,
which are possibly empty. There are two types of such subgraphs, as shown as
$\mathcal{T}\mathcal{C}_{o}$ in the figure 2 one being the spanning trees and
the other being the cycle $u_{2},u_{3},u_{4}$ along with the single vertex
$u_{1}$. In the first case the number of spanning trees is the tree number, or
the complexity, of $K_{4}$, given by $4^{4-2}=4^{2}$ (e.g., [2]) while in the
second case there is only one such subgraph which has two components. So it
follows that

$\iota_{2}(K_{4};u_{1})=20$

and hence

$\mbox{\Large$\varepsilon$}_{QW}(K_{4})=\dfrac{20}{48}=\dfrac{5}{12}.$

Now consider $G_{4}\in\mathcal{G}_{4}$. This graph is a $4$-cycle with
$u_{1}\sim u_{4}$. This graph is bipartite and hence

$\mbox{\Large$\varepsilon$}_{QW}(G_{4})=\dfrac{1}{4}\left(\dfrac{\chi_{2}(G_{4};u_{1},u_{4})}{\chi_{1}(G_{4})}+|E_{0}|\right).$

Since $\chi_{1}(G_{4})$ is the tree number of $G_{4}$ and by removing an edge
from $G_{4}$ we can get a spanning tree, we have

$\chi_{1}(G_{4})=4.$

To compute $\chi_{2}(G_{4};u_{1},u_{4})$, we have to find the number of
forests with exactly two components, one containing $u_{1}$ and the other
containing $u_{4}$. To find such a forest, the edge
$\left\\{u_{1},u_{4}\right\\}$ has to be removed, and other than that, one of
the remaining edges has to be removed. So we have

$\chi_{2}(G_{4};u_{1},u_{4})=3$

and hence

$\mbox{\Large$\varepsilon$}_{QW}(G_{4})=\dfrac{1}{4}(\dfrac{3}{4}+4)=\dfrac{19}{16}.$

Similarly, we compute the comfortability on the remaining classes of graphs
and we tabulate these values as shown in Table 1.

$\mathcal{G}_{i}$ | $\mathcal{G}_{1}$ | $\mathcal{G}_{2}$ | $\mathcal{G}_{3}$ | $\mathcal{G}_{4}$ | $\mathcal{G}_{5}$ | $\mathcal{G}_{6}$ | $\mathcal{G}_{7}$ | $\mathcal{G}_{8}$ | $\mathcal{G}_{9}$ | $\mathcal{G}_{10}$
---|---|---|---|---|---|---|---|---|---|---
$\mbox{\Large$\varepsilon$}_{QW}(\mathcal{G}_{i})$ | $5/12$ | $3/4$ | $1/2$ | $19/16$ | $5/4$ | $7/4$ | $3/4$ | $1$ | $5/4$ | $3/2$
Scattering | R | R | R | T | T | R | R | T | T | T
Bipartiteness | - | - | - | $\circ$ | $\circ$ | - | - | $\circ$ | $\circ$ | $\circ$
$|E|$ | $6$ | $5$ | $5$ | $4$ | $4$ | $4$ | $4$ | $3$ | $3$ | $3$
Table 1: The comfortability of quantum walker to graphs with four vertices:
The comfortability to each graph class is described by $\mathcal{E}_{QW}$. The
symbols of “R” and “T” mean the perfectly reflection and transmitting,
respectively. The best graph with four vertices of the comfortability is the
$\mathcal{G}_{6}$ and the worst graph is the complete graph.

Based on $\mbox{\Large$\varepsilon$}_{QW}$, we have the following ordering of
graphs:

$G_{6}\succ_{QW}G_{10}\succ_{QW}G_{5},G_{9}\succ_{QW}G_{4}\succ_{QW}G_{8}\succ_{QW}G_{2},G_{7}\succ_{QW}G_{3}\succ_{QW}G_{1}.$

Figure 3: The Hasse diagram of comfortability of graphs: The most comfortable
graph for this quantum walker is $\mathcal{G}_{6}$ which is a non-bipartite
graph, while the most uncomfortable graph is $\mathcal{G}_{1}$ (the complete
graph). Here the entrance vertex $u_{1}$ is indicated by the white vertex, and
the exit vertex $u_{N}$ is indicated by the black vertex for the bipartite
case. Note that in the non-bipartite case, the comfortability for this quantum
walker is independent of the position of the exit vertex (see Theorem 2).

Furthermore, we remark that for a tree $T$ in general, with $n$ vertices, the
comfortability of the quantum walker is given by

$\mbox{\Large$\varepsilon$}_{QW}(T)=\dfrac{1}{4}\left(\text{dist}(u_{1},u_{n})+(n-1)\right).$

Finally we also consider the comparison between the comfortability for $z=1$
and $z=-1$ cases. Any graph of four vertices is isomorphic to one of the
following graphs $\Gamma_{1}$,$\Gamma_{2}$,…, $\Gamma_{6}$ as in Figure 4:

$\Gamma_{1}$$\Gamma_{2}$$\Gamma_{3}$$\Gamma_{4}$$\Gamma_{5}$$\Gamma_{6}$
Figure 4: Non-isomorphic graphs $\Gamma_{j}$’s for four vertices

We set

$\mathrm{Comf}(G)=\max_{u_{1},u_{n}\in
V(G)}\mathcal{E}_{QW}(G;\bm{\alpha},u_{1},u_{n})$

for $\bm{\alpha}=(1,0)$ at $u_{1}$ and $u_{n}$. Then we have the
comfortabilities for each graph and $z=\pm 1$ as in Table 2.

| $\Gamma_{1}$ | $\Gamma_{2}$ | $\Gamma_{3}$ | $\Gamma_{4}$ | $\Gamma_{5}$ | $\Gamma_{6}$
---|---|---|---|---|---|---
$z=-1$ | $5/4$ | $3/2$ | $5/4$ | $7/4$ | $3/4$ | $5/12$
$z=1$ | $5/4$ | $3/2$ | $5/4$ | $17/12$ | $3/2$ | $13/8$
Table 2: $\mathrm{Comf}(\Gamma_{j})$ for $z=\pm 1$

Thus we have, for $z=-1$,

$\mathrm{Comf}(\Gamma_{6})<\mathrm{Comf}(\Gamma_{5})<\mathrm{Comf}(\Gamma_{1})=\mathrm{Comf}(\Gamma_{3})<\mathrm{Comf}(\Gamma_{2})<\mathrm{Comf}(\Gamma_{4}),$

and for $z=1$,

$\mathrm{Comf}(\Gamma_{1})=\mathrm{Comf}(\Gamma_{3})<\mathrm{Comf}(\Gamma_{4})<\mathrm{Comf}(\Gamma_{2})=\mathrm{Comf}(\Gamma_{5})<\mathrm{Comf}(\Gamma_{6}).$

##  5 Proof of main theorems

###  5.1 Proof of Theorem 1

To prove this theorem we use the following lemma.

######  Lemma 1.

For a given $u\in V_{0}$, $\Psi_{\infty}(a)-\Psi_{\infty}(\overline{a})$ is
constant for all $a\in\tilde{A}$ with $o(a)=u$.

###### Proof.

It follows from the dynamics of the walk that, in the stationary state, for
$a\in\tilde{A}$ such that $o(a)\in V_{0}$,

$\Psi_{\infty}(a)=-\sum\limits_{b:t(b)=o(a)}\dfrac{2}{\text{deg}(o(a))}\Psi_{\infty}(b)+\Psi_{\infty}(\overline{a}).$

It follows that

$\Psi_{\infty}(a)-\Psi_{\infty}(\overline{a})=-\dfrac{2}{\text{deg}(u)}\sum\limits_{b:t(b)=u}\Psi_{\infty}(b),\;o(a)=u.$

Observe that for a given $u\in V_{0}$, the right hand side of the equation is
a constant. ∎

Now we give the proof of Theorem 1 as follows. By Lemma 1, the measure
$\Psi_{\infty}(a)-\Psi_{\infty}(\overline{a})$ is a measure on $u\in V_{0}$
such that $o(a)=u$. We denote this measure by $\rho(u)$. That is,
$\Psi_{\infty}(a)-\Psi_{\infty}(\overline{a})=\rho(u),o(a)=u$. It follows that
if $u\sim v$ then $\rho(u)=-\rho(v)$.

Suppose $G_{0}$ is non-bipartite. Then there is an odd cycle
$C=(u_{1},...,u_{2l-1}),u_{i}\in V_{0}$ in $G_{0}$. Then we have
$\rho(u_{1})=-\rho(u_{2})=\rho(u_{3})=...=\rho(u_{2l-1})=-\rho(u_{1})$ which
implies $\rho(u_{1})=0$. Since $G_{0}$ is connected, $\rho(u)=0$ for any $u\in
V_{0}$. Thus $\Psi_{\infty}(a)-\Psi_{\infty}(\overline{a})=0$ for any $a\in
A_{0}$ such that $o(a)\in V_{0}$. In particular $\beta_{i}=\alpha_{i}$ for any
$i$. Hence $\bm{\beta}=\bm{\alpha}$.

Now suppose $G_{0}$ is bipartite with $V_{0}=X\sqcup Y$. Observe that

$s:=\rho_{V_{0}}(v)$ (5)

is constant for all $v\in X$. Then

$\rho_{V_{0}}(v)=-s$ (6)

for all $v\in Y$. Define

$\displaystyle A^{X}_{in}$
$\displaystyle=\left\\{a\in\tilde{A}:o(a)\in\tilde{V}\setminus V_{0},t(a)\in
X\right\\},$ $\displaystyle A^{X}_{out}$
$\displaystyle=\left\\{a\in\tilde{A}:\overline{a}\in A^{X}_{in}\right\\},$
$\displaystyle A^{Y}_{in}$
$\displaystyle=\left\\{a\in\tilde{A}:o(a)\in\tilde{V}\setminus V_{0},t(a)\in
Y\right\\},$ $\displaystyle A^{Y}_{out}$
$\displaystyle=\left\\{a\in\tilde{A}:\overline{a}\in A^{Y}_{in}\right\\}.$

Then by applying the time evolution operator once, we get

$U\left(\Psi_{\infty}|_{A^{X}_{in}}+\Psi_{\infty}|_{A^{Y}_{in}}+\Psi_{\infty}|_{A_{0}}\right)=\Psi_{\infty}|_{A^{X}_{out}}+\Psi_{\infty}|_{A^{Y}_{out}}+\Psi_{\infty}|_{A_{0}}.$

By taking the squared norm, we get

$\left\lVert\Psi_{\infty}|_{A^{X}_{in}}\right\rVert^{2}+\left\lVert\Psi_{\infty}|_{A^{Y}_{in}}\right\rVert^{2}+\left\lVert\Psi_{\infty}|_{A_{0}}\right\rVert^{2}=\left\lVert\Psi_{\infty}|_{A^{X}_{out}}\right\rVert^{2}+\left\lVert\Psi_{\infty}|_{A^{Y}_{out}}\right\rVert^{2}+\left\lVert\Psi_{\infty}|_{A_{0}}\right\rVert^{2}.$

It follows from (5) and (6) that

$\displaystyle\left\lVert\Psi_{\infty}|_{A^{X}_{in}}\right\rVert^{2}+\left\lVert\Psi_{\infty}|_{A^{Y}_{in}}\right\rVert^{2}$
$\displaystyle=\left\lVert
s\mathbbm{1}_{A^{X}_{in}}+S\Psi_{\infty}|_{A^{X}_{in}}\right\rVert^{2}+\left\lVert-s\mathbbm{1}_{A^{Y}_{in}}+S\Psi_{\infty}|_{A^{Y}_{in}}\right\rVert^{2}$
$\displaystyle=s^{2}|X\cap\delta V|+2s\sum\limits_{a\in
A^{X}_{in}}\Psi_{\infty}(a)+\left\lVert\Psi_{\infty}|_{A^{X}_{in}}\right\rVert^{2}$
$\displaystyle\qquad\qquad+s^{2}|Y\cap\delta V|-2s\sum\limits_{a\in
A^{Y}_{in}}\Psi_{\infty}(a)+\left\lVert\Psi_{\infty}|_{A^{Y}_{in}}\right\rVert^{2}.$

Here $S$ is the shift operator: $S\delta_{a}=\delta_{\bar{a}}$ for any
$a\in\tilde{A}$. Hence if $s\neq 0$,

$s=-\dfrac{2}{|\delta V|}\left(\sum\limits_{a\in
A^{X}_{in}}\Psi_{\infty}(a)-\sum\limits_{a\in
A^{Y}_{in}}\Psi_{\infty}(a)\right).$ (7)

Then it follows that

$\beta_{i}=\alpha_{i}-\dfrac{2}{|\delta V|}\left(\sum\limits_{a\in
A^{X}_{in}}\Psi_{\infty}(a)-\sum\limits_{a\in
A^{Y}_{in}}\Psi_{\infty}(a)\right),$

where $\beta_{i}=\Psi_{\infty}(a)$ for some $a\in A^{X}_{out}$ and

$\beta_{i}=\alpha_{i}-\dfrac{2}{|\delta V|}\left(\sum\limits_{a\in
A^{Y}_{in}}\Psi_{\infty}(a)-\sum\limits_{a\in
A^{X}_{in}}\Psi_{\infty}(a)\right),$

where $\beta_{i}=\Psi_{\infty}(a)$ for some $a\in A^{Y}_{out}$. Hence
$\bm{\beta}=\tau\bm{\alpha}$ where

$\tau=\left(\begin{array}[]{@{}c|c@{}}\begin{matrix}-\dfrac{2}{|\delta
V|}+1&-\dfrac{2}{|\delta V|}&...\\\ -\dfrac{2}{|\delta V|}&-\dfrac{2}{|\delta
V|}+1&...\\\ .&&\\\ .&&\\\ .&&\\\ \end{matrix}&\mbox{\Large$\dfrac{2}{|\delta
V|}$}\\\ \hline\cr\mbox{\Large$\dfrac{2}{|\delta
V|}$}&\begin{matrix}-\dfrac{2}{|\delta V|}+1&-\dfrac{2}{|\delta V|}&...\\\
-\dfrac{2}{|\delta V|}&-\dfrac{2}{|\delta V|}+1&...\\\ .&&\\\ .&&\\\ .&&\\\
\end{matrix}\end{array}\right).$

It is clear that, to satisfy the condition $s\neq 0$, we must have $\sum_{a\in
A^{Y}_{in}}\Psi_{\infty}(a)\neq\sum_{a\in A^{X}_{in}}\Psi_{\infty}(a)$. Now
let us see that $s=0$ if and only if $\kappa_{X}=\kappa_{Y}$, where
$\kappa_{X}=\sum_{a\in A^{X}_{in}}\Psi_{\infty}(a)$ and $\kappa_{Y}=\sum_{a\in
A^{Y}_{in}}\Psi_{\infty}(a)$.

By Lemma 1 we have, $s=0$ if and only if

$\Psi_{\infty}(a)=\Psi_{\infty}(\overline{a}),\;a\in A_{0}\text{ with }o(a)\in
V_{0}$

and

$\sum\limits_{b:t(b)=u}\Psi_{\infty}(b)=0,\;u\in V_{0}.$

Thus we have

$\displaystyle 0$ $\displaystyle=\sum\limits_{a:t(a)\in Y}\Psi_{\infty}(a)$
$\displaystyle=\sum_{a:\;t(a)\in Y,\;o(a)\in X}\Psi_{\infty}(a)+\kappa_{Y}$
$\displaystyle=\sum_{a:\in o(a)\in X,\;t(a)\in Y}\Psi_{\infty}(a)+\kappa_{Y}$
$\displaystyle=\sum\limits_{a:o(a)\in
X}\Psi_{\infty}(a)-\kappa_{X}+\kappa_{Y}$
$\displaystyle=-\kappa_{X}+\kappa_{Y},$

which implies $\kappa_{X}=\kappa_{Y}$ if $s=0$.

If $\bm{\alpha}$ satisfies $\kappa_{X}=\kappa_{Y}$, then $s=0$ and the same
argument as in the case where $G_{0}$ is non-bipartite is valid;
$\bm{\beta}=\bm{\alpha}$ holds. It is easy to check that
$\bm{\beta}=\tau\bm{\alpha}$ holds for $\tau$ defined above. $\hfill\square$

$1$ Figure 5: Example of the inflow of $s\neq 0$.

###  5.2 Proof of Theorem 2

The proof of Theorem 2 is divided into three parts with bipartite and non-
bipartite cases as follows. First, we will show that the stationary state is
expressed by a (pseudo-)current function. Secondly, we will determine the
potential functions with respect to the (pseudo-)current function which
satisfies the Poisson equation in terms of the (signless-)Laplacian. Finally,
we will express the comfortability in terms of geometries of the graph using
the above.

####  5.2.1 Kirchhoff and pseudo-Kirchhoff laws

In this subsection we will see that the stationary state can represent a kind
of current function [15, 17] on the underlying bipartite and non-bipartite
graphs.

Bipartite case
First, we will introduce a current function induced by the stationary state
$\Psi_{\infty}$ on a bipartite graph. Let $G_{0}$ be a bipartite graph with
$V_{0}=X\sqcup Y$. Define the function $f(\cdot)$ such that

$f(a)=\begin{cases}0&\text{if }\,t(a)\in X,\\\ \\\ 1&\text{if }\,t(a)\in
Y.\end{cases}$

Then by Lemma 1, it follows that the measure
$\dfrac{1}{2}\left((-1)^{f(a)}\Psi_{\infty}(a)+(-1)^{f(\overline{a})}\Psi_{\infty}(\overline{a})\right)$
is a constant for any $a\in A_{0}$. We denote this constant by $\rho$. Then
the following theorem holds.

######  Theorem 5.

Let the setting be the same as the above and define
$j(a)=(-1)^{f(a)}\Psi_{\infty}(a)-\rho$. Then $j(\cdot)$ satisfies the
Kirchhoff’s current and voltage laws:

  1. 1.

(Kirchhoff current law) For any $u\in\tilde{V}$ and $a\in\tilde{A}$,

$\sum\limits_{b\in\tilde{A}:t(b)=u}j(b)=0,\,j(a)+j(\overline{a})=0.$

  2. 2.

(Kirchhoff voltage law) For any cycle $c=(a_{1},...,a_{s})$ with
$t(a_{1})=o(a_{2}),...,t(a_{s-1})=o(a_{s}),t(a_{s})=o(a_{1})$ in $G_{0}$, it
holds

$\sum\limits_{k=1}^{s}j(a_{k})=0.$

###### Proof.

We can rewrite the expression in Lemma 1 as

$\dfrac{1}{2}\left((-1)^{f(a)}\Psi_{\infty}(a)+(-1)^{f(\overline{a})}\Psi_{\infty}(\overline{a})\right)=\dfrac{1}{\text{deg}(u)}\sum\limits_{b:t(b)=u}(-1)^{f(b)}\Psi_{\infty}(b),\,o(a)=u,$

in which the right hand side is a measure on the vertex $u$, denoted by
$\rho(u)$. Then it follows that if $u\sim v$ then $\rho(u)=\rho(v)$. Since
$G_{0}$ is connected, it follows that $\rho(u)$ is a constant for all $u\in
V_{0}$, which is denoted by $\rho$. Summarizing the above, we have

$\dfrac{1}{\text{deg}(u)}\sum\limits_{b:t(b)=u}(-1)^{f(b)}\Psi_{\infty}(b)=\rho,u\in
V_{0}.$ (8)

Then from (7) we can express

$\rho=\dfrac{1}{|\delta V|}\left(\sum\limits_{a\in
A^{X}_{in}}\Psi_{\infty}(a)-\sum\limits_{a\in
A^{Y}_{in}}\Psi_{\infty}(a)\right).$

Equation (8) implies

$\sum\limits_{a:t(a)=u}j(a)=\sum\limits_{a:t(a)=u}(-1)^{f(a)}\Psi_{\infty}(a)-\rho\text{deg}(u)=0,\;u\in
V_{0}.$

Also we have

$j(a)+j(\overline{a})=(-1)^{f(a)}\Psi_{\infty}(a)+(-1)^{f(\overline{a})}\Psi_{\infty}(\overline{a})-2\rho=0,\;a\in
A_{0}.$

Now suppose $C=(a_{1},...,a_{2l}),a_{i}\in A_{0}$ is an even cycle in $G_{0}$.
Assume that $o(a_{1})\in X$. Define $\varphi$ such that

$\varphi(a)=\begin{cases}1&\text{if }a=a_{2k+1}\text{ or
}\overline{a}_{2k+1},\\\ -1&\text{if }a=a_{2k}\text{ or }\overline{a}_{2k},\\\
0&\text{otherwise.}\end{cases}$

Let $\psi_{\infty}:=\chi^{*}\Psi_{\infty}$. Since $\varphi$ is a centered
eigenvector of $\chi U\chi^{*}$ whose eigenvalue is $-1$, by [17, Lemmas 3.4
and 3.5] we have $\psi_{\infty}\perp\varphi$ and it follows that

$\displaystyle 0$
$\displaystyle=\left\langle\psi_{\infty}|\varphi\right\rangle$
$\displaystyle=\sum\limits_{a\in A_{0}}\psi_{\infty}(a)\varphi(a)$
$\displaystyle=\sum\limits_{k=1}^{l}\left[\left[\psi_{\infty}(a_{2k-1})+\psi_{\infty}(\overline{a}_{2k-1})\right]-\left[\psi_{\infty}(a_{2k-1})+\psi_{\infty}(\overline{a}_{2k-1})\right]\right]$
$\displaystyle=\sum\limits_{k=1}^{l}\left[(-1)^{f(a_{2k-1})}\left(j(a_{2k-1})-j(\overline{a}_{2k-1})\right)-(-1)^{f(a_{2k})}\left(j(a_{2k})-j(\overline{a}_{2k})\right)\right]$
$\displaystyle=\sum\limits_{k=1}^{2l}\left[j(a_{k})-j(\overline{a}_{k})\right].$

Since $j(a)+j(\overline{a})=0$, it follows that

$\sum\limits_{k=1}^{s}j(a_{k})=0.$

∎

Non-bipartite case
Next let us investigate the property of $\psi_{\infty}$ in the case non-
bipartite case. We can see that the stationary state itself has similar
properties to the electrical current flow as follows.

######  Theorem 6.

Let $\Psi_{\infty}\in\tilde{A}$ be the stationary state on the non-bipartite
graph. Then $\Psi_{\infty}$ satisfies the following properties:

  1. 1.

(Pseudo-Kirchhoff current law) For each $u\in V_{0}$ and $a\in\tilde{A_{0}}$,

$\sum_{b:t(a)=u}\Psi_{\infty}(a)=0,\;\Psi_{\infty}(a)=\Psi_{\infty}(\bar{a}).$

  2. 2.

(Pseudo-Kirchhoff voltage law) For any even closed walk $(e_{1},\dots,e_{2s})$
such that
$t(e_{1})=o(e_{2}),\dots,t(e_{2s-1})=o(e_{2s})$ and $t(e_{2s})=o(e_{1})$,

$\sum_{k=1}^{2s}(-1)^{k}\Psi_{\infty}(e_{k})=0.$

###### Proof.

The proof of the first part is obtained from the proof of Theorem 1. The
second part shows $\langle\psi_{\infty},\phi\rangle=0$ for any $\phi$ which is
an eigenfunction of the eigenvalue $-1$ in the birth part. For details, refer
to [14, Definition 4 and Theorem 1]. Moreover it has been shown by [17] that
the stationary state is orthogonal to the birth part. Then we have the desired
conclusion. ∎

####  5.2.2 Laplacian and signless Laplacian

We have seen that the stationary state has the properties of current function
or pseudo-current function in $\mathbb{C}^{\tilde{A}}$. Then it is natural to
determine the potential function in $\mathbb{C}^{V_{0}}$ with respect to the
current. In this subsection, we characterize the potential function using the
Laplacian and the signless Laplacian for the cases of bipartite and non-
bipartite graphs, respectively.

Bipartite case
Let $M$ be the adjacency matrix and $D$ be the degree matrix of $G_{0}$. The
Laplacian matrix of $G_{0}$ is denoted by $L=M-D$. Using the Laplacian matrix
with the Poisson equation, we can characterise the current function $j(\cdot)$
on $A_{0}$ in terms of a potential function on $V_{0}$ ([2] and [4]) in which
exists under the Kirchhoff current and voltage laws.

######  Theorem 7 (see e.g., [2, 4]).

Let the setting be the same as in Theorem 5. Let $G_{0}$ be a bipartite graph
and $L$ be the Laplacian matrix of $G_{0}$. Then there exists a potential
function $\phi\in\mathbb{C}^{V_{0}}$ such that $j(a)=\phi(o(a))-\phi(t(a))$.
Here $\phi$ satisfies the following equation.

$L\phi=-q,$

where $q(u)=\sum\limits_{a\in\tilde{A}\setminus A_{0}:t(a)=u}j(a),\;u\in
V_{0}.$

Here we should remark that $q\in(\text{ker}(L))^{\perp}$: actually we have

$0=\sum_{a\in A:t(a)\in V_{0}}j(a)\equiv\sum_{a\in A\setminus A_{0}:t(a)\in
V_{0}}j(a)=\sum_{v\in V_{0}}q(v)\bm{1}(v),$

where $\bm{1}(\cdot)$ is the constant function whose value is $1$ and
$\text{ker}(L)=\left\\{c\bm{1}:c\in\mathbb{C}\right\\}$.

Non-bipartite case
When the underlying graph is non-bipartite, the following two properties hold
for the stationary sate $\Psi_{\infty}$ by Theorem 6:

$\displaystyle\Psi_{\infty}(a)$
$\displaystyle=\Psi_{\infty}(\overline{a}),\;\text{for
any}\;a\in\tilde{A},o(a)\in V_{0};$ (9)
$\displaystyle\sum\limits_{a\in\tilde{A}:t(a)=u}\Psi_{\infty}(a)$
$\displaystyle=0,\;\text{for any}\;u\in V_{0}.$ (10)

As an analogy to the current function in the bipartite case, we represent
these properties in term of the non-oriented incidence matrix and the signless
Laplacian matrix in the following theorem. Here the sighless Laplacian matrix
of $G_{0}$ is denoted by $Q=M+D$.

######  Theorem 8.

Let $\Psi_{\infty}$ be the stationary state of quantum walk such that
$\Psi_{\infty}(a)=\lim_{n\to\infty}(U^{n}\Psi_{0})(a)$ for any
$a\in\tilde{A}$. Let $G_{0}$ be a non-bipartite graph and $Q$ be the signless
Laplacian matrix of $G_{0}$. Then there uniquely exists
$\phi\in\mathbb{C}^{V_{0}}$ such that $\Psi_{\infty}(a)=\phi(o(a))+\phi(t(a))$
for any $a\in A_{0}$. Here $\phi$ satisfies the following equation.

$Q\phi=-q$

where $q(u)=\sum\limits_{a\in\tilde{A}\setminus
A_{0}:t(a)=u}\Psi_{\infty}(a),\;u\in V_{0}.$

###### Proof.

Denote the non-oriented incidence matrix on the set of arcs by
$\tilde{C}:\mathbb{C}^{A_{0}}\rightarrow\mathbb{C}^{V_{0}}$ which satisfies

$(\tilde{C}\psi)(v_{i})=\sum\limits_{j=1}^{m}c_{ij}\psi(a_{j}),\;1\leq i\leq
n,$

where $m=|A_{0}|$ and

$c_{ij}=\begin{cases}1&\text{if }\,t(a_{j})=v_{i}\text{ or }o(a_{j})=v_{i},\\\
0&\text{otherwise. }\end{cases}$

Then we have

$(\tilde{C}\psi)(v)=\sum\limits_{a\in A_{0}:t(a)=v}\psi(a)+\sum\limits_{a\in
A_{0}:o(a)=v}\psi(a),\;v\in V_{0}.$

The adjoint operator
$\tilde{C}^{*}:\mathbb{C}^{V_{0}}\rightarrow\mathbb{C}^{A_{0}}$ is given by

$(\tilde{C}^{*}f)(a)=f(t(a))+f(o(a)).$

Then we have $\tilde{C}\tilde{C}^{*}$ in terms of the signless Laplacian
matrix $Q$

$\tilde{C}\tilde{C}^{*}=2(D+M)=2Q.$

Let $\psi_{\infty}=\chi^{*}\Psi_{\infty}$. Now let us see that if there exists
a potential function $\phi\in\mathbb{C}^{V_{0}}$ such that
$\psi_{\infty}(a)=(\tilde{C}^{*}\phi)(a)$ for any $a\in A_{0}$, then $\phi$
must satisfy

$Q\phi=-q.$

Remark that for any $a\in A_{0}$

$\psi_{\infty}(a)=(\tilde{C}^{*}\phi)(a)=\phi(t(a))+\phi(o(a))=\phi(t(\overline{a}))+\phi(o(\overline{a}))=(\tilde{C}^{*}\phi)(\overline{a})=\psi_{\infty}(\overline{a})$

and hence the first property of (9) can be easily confirmed. We have, by the
property (9),

$\displaystyle\sum\limits_{a\in\tilde{A}:o(a)=u}\Psi_{\infty}(a)$
$\displaystyle=\sum\limits_{a\in\tilde{A}:o(a)=u}\Psi_{\infty}(\overline{a})$
$\displaystyle=\sum\limits_{a\in\tilde{A}:t(a)=u}\Psi_{\infty}(a),$

and by the property (10),

$\sum\limits_{a\in\tilde{A}:t(a)=u}\Psi_{\infty}(a)+\sum\limits_{a\in\tilde{A}:o(a)=u}\Psi_{\infty}(a)=0,\;u\in
V_{0}.$

Let us divide the summation in the above equation by

$\sum\limits_{a\in
A_{0}:t(a)=u}\Psi_{\infty}(a)+\sum\limits_{a\in\tilde{A}\setminus
A_{0}:t(a)=u}\Psi_{\infty}(a)+\sum\limits_{a\in
A_{0}:o(a)=u}\Psi_{\infty}(a)+\sum\limits_{a\in\tilde{A}\setminus
A_{0}:o(a)=u}\Psi_{\infty}(a)=0.$

Then it follows that

$(\tilde{C}\psi_{\infty})(u)=-2\sum\limits_{a\in\tilde{A}\setminus
A_{0}:t(a)=u}\Psi_{\infty}(a).$

which implies

$Q\phi=\dfrac{1}{2}\tilde{C}\tilde{C}^{*}\phi=-q,$

where $q(u)=\sum_{a\in\tilde{A}\setminus A_{0}:t(a)=u}\Psi_{\infty}(a),u\in
V_{0}.$ Although the existence of the potential function $\phi$ is ensured by
the pseudo-Kirchhoff voltage law in Theorem 6, we prove here directly as
follows. To show the existence of $\phi$, it is enough to show that

$\psi_{\infty}\in\text{Range}(\tilde{C}^{*})=\text{ker}(\tilde{C})^{\perp}.$

Let us see that

$\text{ker}(\tilde{C})=(\text{ker}(d)\cap\mathcal{H}_{+})\oplus\mathcal{H}_{-},$
(11)

where
$\mathcal{H}_{+}=\left\\{\psi\in\mathbb{C}^{A_{0}}:\psi(a)=\psi(\overline{a})\text{
for any }a\in A_{0}\right\\}$,
$\mathcal{H}_{-}=\left\\{\psi\in\mathbb{C}^{A_{0}}:\psi(a)=-\psi(\overline{a})\text{
for any }a\in A_{0}\right\\}$ and

$(d\varphi)(u)=\dfrac{1}{\sqrt{\deg_{G_{0}}(u)}}\sum\limits_{a\in
A_{0}:t(a)=u}\varphi(a).$

Note that $\mathcal{H}_{+}\oplus\mathcal{H}_{-}=\mathbb{C}^{A_{0}}$ and
$\mathcal{H}_{+}=\ker(1-S_{0})$, $\mathcal{H}_{-}=\ker(1+S_{0})$, where
$S_{0}$ is the shift operator on $\mathbb{C}^{A_{0}}$ such that
$S_{0}\delta_{a}=\delta_{\bar{a}}$ for any $a\in A_{0}$. The operator
$\tilde{C}$ can be rewritten by

$(\tilde{C}\psi)(u)=\sqrt{\deg_{G_{0}}(u)}\left((d\psi)(u)+(dS_{0}\psi)(u)\right).$

Then we have

$\ker\tilde{C}=\ker(d(1+S_{0})),$

which implies (11). By [17] it follows that

$\psi_{\infty}\in(\text{ker}(d)\cap\mathcal{H}_{+})^{\perp}.$

Since $\psi_{\infty}(\bar{a})=\psi_{\infty}(a)$, then
$\psi_{\infty}\in\mathcal{H}_{+}=\mathcal{H}_{-}^{\perp}$. Therefore
$\psi_{\infty}\in\ker(\tilde{C})^{\perp}=\text{Range}(\tilde{C}^{*})$.

Furthermore, since $G_{0}$ is non-bipartite, the least eigenvalue of $Q$ is
positive (cf. [6]) and hence $Q$ is invertible. This completes the proof of
the existence and the uniqueness of $\phi$. ∎

####  5.2.3 Comfortability

We have seen that relations between stationary state and the
(signless-)Laplacian, which contains information of the geometry of the graph.
Let us express the comfortability in terms of some graph geometrical
properties. This leads the completion of the proof of Theorem 2.

Bipartite case
Now we introduce the energy of the electric circuit
$\mbox{\Large$\varepsilon$}_{EC}(G_{0})$ which is given by,

$\mbox{\Large$\varepsilon$}_{EC}(G_{0})=\dfrac{1}{2}\left\lVert
j\right\rVert^{2}=\frac{1}{2}\sum_{a\in A_{0}}|j(a)|^{2}.$

To give the next proposition, we prepare the following notion. Note that the
Laplacian matrix $L$ is singular and hence $\phi$ is not determined uniquely.
We impose the ground condition $\phi(n)=0$ which reduces the equation in
Theorem 7 to $L^{(n)}\phi^{(n)}=-q^{(n)}$, where $L^{(n)}$ is the matrix
obtained by removing the $n$-th row and the $n$-th column of the Laplacian
matrix, $\phi^{(n)}$ and $q^{(n)}$ are the vectors obtained by removing the
$n$-th element from $\phi$ and $q$ respectively. Here, $\text{det}(L^{(n)})$
is the number of spanning trees of $G_{0}$ (see [2]), and hence non-zero. So
$\phi^{(n)}$ is determined uniquely by $\phi^{(n)}=-(L^{(n)})^{-1}q^{(n)}$.
More over, we denote by $B$ and $\tilde{B}$, the usual incidence matrix and
the non-oriented incidence matrix on the set of edges respectively. More
precisely, we fix an orientation of each $e\in E_{0}$ and denote it by
$\vec{E}_{0}$:

$A_{0}=\vec{E}_{0}\cup\overline{(\vec{E}_{0})},$

where $\overline{(\vec{E}_{0})}=\\{a\in A_{0}\;|\;\bar{a}\in\vec{E}_{0}\\}$.
Then $B:\mathbb{C}^{\vec{E}_{0}}\to\mathbb{C}^{V_{0}}$ is denoted by

$\displaystyle(B\psi)(u)$
$\displaystyle=\sum_{t(a)=u}\psi(a)-\sum_{o(a)=u}\psi(a);$

then its adjoint is expressed by

$(B^{*}f)(a)=f(t(a))-f(o(a)).$

The non-oriented incidence matrix
$\tilde{B}:\mathbb{C}^{\vec{E}_{0}}\to\mathbb{C}^{V_{0}}$ is denoted by

$\displaystyle(\tilde{B}\psi)(u)$
$\displaystyle=\sum_{t(a)=u}\psi(a)+\sum_{o(a)=u}\psi(a);$

then its adjoint is expressed by

$({\tilde{B}}^{*}f)(a)=f(t(a))+f(o(a)).$

Now we give the following proposition.

######  Proposition 1.

The electrical energy of the circuit is given by

$\mbox{\Large$\varepsilon$}_{EC}(G_{0})=\dfrac{1}{\mathrm{det}(L^{(n)})}\sum\limits_{i,j=1}^{n-1}(-1)^{i+j}q^{(n)}(i)q^{(n)}(j)\sum\limits_{\begin{subarray}{c}H\subset
G_{0}\\\
|E(H)|=n-2\end{subarray}}\mathrm{det}(B_{H}^{(n,j)})\mathrm{det}((B_{H}^{(n,i)})^{*}),$

where $B_{H}^{(n,j)}$ is the matrix obtained by choosing the columns
corresponding to the edges in $H$ and removing the $j$-th and $n$-th rows in
the oriented incidence matrix of $G_{0}$.

###### Proof.

By definition, we can write the electrical energy in terms of the Laplacian
matrix as follows.

$\displaystyle\mbox{\Large$\varepsilon$}_{EC}(G_{0})$
$\displaystyle=\dfrac{1}{2}\left\lVert j\right\rVert^{2}=\left\langle
B^{*}\phi,B^{*}\phi\right\rangle=\left\langle\phi,L\phi\right\rangle=-\left\langle\phi,q\right\rangle=-\left\langle\phi^{(n)},q^{(n)}\right\rangle=\left\langle(L^{(n)})^{-1}q^{(n)},q^{(n)}\right\rangle$
$\displaystyle=\sum\limits_{i=1}^{n-1}q^{(n)}(i)((L^{(n)})^{-1}q^{(n)})(i).$

By Cramer’s rule, we get,

$\mbox{\Large$\varepsilon$}_{EC}(G_{0})=\dfrac{1}{\text{det}(L^{(n)})}\sum\limits_{i=1}^{n-1}q^{(n)}(i)\text{det}(L^{(n)}_{i}),$

where $\text{det}(L^{(n)}_{i})$ is the matrix obtained by replacing the $i$-th
column of $L^{(n)}$ by $q^{(n)}$. Now by expanding along the $i$-th column, we
get

$\mbox{\Large$\varepsilon$}_{EC}(G_{0})=\dfrac{1}{\text{det}(L^{(n)})}\sum\limits_{i,j=1}^{n-1}q^{(n)}(i)q^{(n)}(j)\text{det}(L^{(n)}_{(j,i)}),$

where $L^{(n)}_{(j,i)}$ is the matrix obtained by removing the $j$-th row and
the $i$-th column from $L^{(n)}$. Note that
$L^{(n)}_{(j,i)}=B^{(j,n)}(B^{(i,n)})^{*}$ and hence

$\mbox{\Large$\varepsilon$}_{EC}(G_{0})=\dfrac{1}{\text{det}(L^{(n)})}\sum\limits_{i,j=1}^{n-1}q^{(n)}(i)q^{(n)}(j)\text{det}(B^{(j,n)}(B^{(i,n)})^{*}),$

where $B^{(j,n)}$ is the matrix obtained by removing the $j$-th and the $n$-th
rows from $B$. Now by Binet-Cauchy theorem (see [6]), it follows that

$\mbox{\Large$\varepsilon$}_{EC}(G_{0})=\dfrac{1}{\text{det}(L^{(n)})}\sum\limits_{i,j=1}^{n-1}(-1)^{i+j}q^{(n)}(i)q^{(n)}(j)\sum\limits_{\begin{subarray}{c}H\subset
G_{0}\\\
|E(H)|=n-2\end{subarray}}\text{det}(B_{H}^{(n,j)})\text{det}((B_{H}^{(n,i)})^{*}),$

where $B_{H}^{(n,j)}$ is the matrix obtained by choosing the columns
corresponding to the edges in $H$ from $B^{(j,n)}$. ∎

Now we give the proof of Theorem 2 by applying Proposition 1. Observing that
$\rho=1/2$, $q^{(n)}(1)=1-\rho=1/2$ and $q^{(n)}(i)=0$ $(i=2,\dots,n-1)$ in
our setting of Theorem 2 and applying Proposition 1 to our setting, we get

$\mbox{\Large$\varepsilon$}_{EC}(G_{0})=\frac{1}{4}\dfrac{1}{\text{det}(L^{(n)})}\sum\limits_{\begin{subarray}{c}H\subset
G_{0}\\\ |E(H)|=n-2\end{subarray}}\left(\text{det}(B_{H}^{(n,1)})\right)^{2}.$

Focusing on the linearly dependence on the column vectors of the incidence
matrix of the spanning subgraph $H\subset G_{0}$, we obtain the following:

  1. 1.

If $H$ contains a cycle, then $\text{det}(B_{H}^{(n,1)})=0$;

  2. 2.

If $H$ contains a connected component including both $u_{1}$ and $u_{n}$, then
$\text{det}(B_{H}^{(n,1)})=0$.

Hence, it implies that if $\text{det}(B_{H}^{(n,1)})\neq 0$. Then $H$ is a
spanning forest which contains exactly two components, one containing $u_{1}$
and the other one containing $u_{n}$. On the other hand, if $H$ is a spanning
forest which contains exactly two components, one containing $u_{1}$ and the
other one containing $u_{n}$, $B_{H}^{(n,1)}$ is of the form

$B_{H}^{(n,1)}=\left(\begin{array}[]{@{}c|c@{}}B_{T_{1}}&0\\\ \hline\cr
0&B_{T_{2}}\end{array}\right)$

for the trees $T_{1}$ and $T_{2}$ in the forest which are the spanning trees
of the two components of the forest. Now by [2],
$\text{det}(B_{T_{1}})=\text{det}(B_{T_{2}})=\pm 1$ and hence
$\left(\text{det}(B_{H}^{(n,1)})\right)^{2}=1$. Thus,
$\left(\text{det}(B_{H}^{(n,1)})\right)^{2}=1$ if and only if $H$ is a
spanning forest which contains exactly two components, one containing $u_{1}$
and the other one containing $u_{n}$. Hence it follows that

$4\mbox{\Large$\varepsilon$}_{EC}(G_{0})=\dfrac{\chi_{2}(G_{0};u_{1},u_{n})}{\chi_{1}(G_{0})},$

where $\chi_{1}(G_{0})$ is the tree number of $G_{0}$ and
$\chi_{2}(G_{0};u_{1},u_{n})$ is the number of spanning forests of $G_{0}$
with exactly two components, one containing $u_{1}$ and the other containing
$u_{n}$.

Let $G_{0}$ be a bipartite graph. Then

$\displaystyle\mbox{\Large$\varepsilon$}_{QW}$
$\displaystyle=\dfrac{1}{2}\sum\limits_{a\in
A_{0}}|\Psi_{\infty}(a)|^{2}=\dfrac{1}{2}\sum\limits_{a\in
A_{0}}|j(a)+\rho|^{2}=\dfrac{1}{2}\sum\limits_{a\in
A_{0}}j(a)^{2}+\rho\sum\limits_{a\in A_{0}}j(a)+\rho^{2}|E_{0}|$
$\displaystyle=\mbox{\Large$\varepsilon$}_{EC}(G_{0})+\rho^{2}|E_{0}|.$ (12)

Note that in our setting with only two tails, we have $\rho^{2}=\dfrac{1}{4}$,
which leads to the formula in the theorem.

Non-bipartite case

Now let $G_{0}$ be non-bipartite. Then we have
$\psi_{\infty}(e)=\psi_{\infty}(\bar{e})=(\tilde{B}^{*}\phi)(e)$ for any
$e\in\vec{E}_{0}$ and $Q\phi=-q$. Now since $G_{0}$ is non-bipartite, it
follows that $Q$ is invertible (for example, see [6, Theorem 7.8.1]) and hence
$\phi=-Q^{-1}q$. By a similar argument, it follows that

$\displaystyle\mbox{\Large$\varepsilon$}_{QW}(G_{0})$
$\displaystyle=\dfrac{1}{2}\sum\limits_{a\in
A_{0}}|\Psi_{\infty}(a)|^{2}=\dfrac{1}{2}\left\langle\psi_{\infty},\psi_{\infty}\right\rangle=\left\langle\tilde{B}^{*}\phi,\tilde{B}^{*}\phi\right\rangle=\left\langle\phi,Q\phi\right\rangle=\left\langle
Q^{-1}q,q\right\rangle.$

By using the Cramer’s rule and the Binet-Cauchy theorem, we can derive a
similar expression for the non-bipartite graphs as follows:

######  Proposition 2.

Let $G_{0}$ be a non-bipartite graph with arbitrary boundary . Then we have

$\mbox{\Large$\varepsilon$}_{QW}(G_{0})=\dfrac{1}{\text{det}(Q)}\sum\limits_{i,j=1}^{n}(-1)^{i+j}q(i)q(j)\sum\limits_{\begin{subarray}{c}H\subset
G_{0}\\\
|E(H)|=n-1\end{subarray}}\text{det}(\tilde{B}_{H}^{(i)})\text{det}(\tilde{B}_{H}^{(j)}),$

where $\tilde{B}_{H}^{(j)}$ is the matrix obtained by choosing the columns
corresponding to the edges in $H$ and removing the $j$-th row from
$\tilde{B}$.

Observing that $q(j)=\delta_{1}(j)$ in our setting and applying Proposition 2,
then we have

$\mbox{\Large$\varepsilon$}_{QW}(G_{0})=\dfrac{1}{\text{det}(Q)}\sum\limits_{\begin{subarray}{c}H\subset
G_{0}\\\
|E(H)|=n-1\end{subarray}}\left(\text{det}(\tilde{B}_{H}^{(1)})\right)^{2}.$

Focusing on the linearly dependence on the column vectors of the incidence
matrix of the spanning subgraph $H\subset G\setminus\\{{u_{1}}\\}$, we obtain
the following:

  1. 1.

If $H$ has an even cycle, then $\text{det}(\tilde{B}_{H}^{(1)})=0$;

  2. 2.

If $H$ has a connected component having at least two odd cycles, then
$\text{det}(\tilde{B}_{H}^{(1)})=0$;

  3. 3.

If $H$ has a connected component having an odd cycle and $u_{1}$, then
$\text{det}(\tilde{B}_{H}^{(1)})=0$.

Hence it implies that if $\text{det}(\tilde{B}_{H}^{(1)})\neq 0$ then $H=T\cup
C_{1}\cup...\cup C_{k}$ where $u_{1}\in T$ where $T$ is a tree and
$C_{1}\cup...\cup C_{k}$ are odd unicycles. Now if $H=T\cup C_{1}\cup...\cup
C_{k}$ where $u_{1}\in T$ where $T$ is a tree and $C_{1}\cup...\cup C_{k}$ are
odd unicycles, then $\tilde{B}_{H}^{(1)}$ is of the form

$\tilde{B}_{H}^{(1)}=\left(\begin{array}[]{<EMAIL_ADDRESS>\hline\cr 0&\tilde{B}_{C_{1}}&...&0\\\ \hline\cr.&&&\\\ .&&&\\\ .&&&\\\
\hline\cr 0&...&0&\tilde{B}_{C_{k}}\end{array}\right).$

Note that $\text{det}(\tilde{B}_{T})=\pm 1$ (by [2]) and by expanding the
determinant of the non-oriented incidence matrix of a cycle, we can show that
$\text{det}(\tilde{B}_{C_{i}})=\pm 2$ (see Appendix for the details), which
implies that

$\left(\text{det}(\tilde{B}_{H}^{(1)})\right)^{2}=4^{\omega(H)-1},$

where $\omega(H)$ is the number of components in $H$. Furthermore, let

$\mathcal{C}_{o}=\\{\\{C_{1},...,C_{r}\\}|C_{i}\text{'s are odd unicyclic
graphs}\\}$

and

$\mathcal{T}\mathcal{C}_{o}=\\{\\{T,C_{1},...,C_{k}\\}|u_{1}\in T\text{ where
}T\text{ is a tree and }C_{i}\text{'s are odd unicyclic graphs}\\}.$

Then by [5],

$\text{det}(Q)=\sum\limits_{H\in C_{0}}4^{\omega(H)}$

and it follows that

$\mbox{\Large$\varepsilon$}_{QW}=\dfrac{\sum\limits_{H\in\mathcal{T}\mathcal{C}_{o}}4^{\omega(H)-1}}{\sum\limits_{H\in
C_{0}}4^{\omega(H)}}$

which completes the proof. $\hfill\square$

## Appendix

Let $C_{i}$ be an odd unicyclic graph and let $\tilde{B}_{C_{i}}$ be the non-
oriented incident matrix of $C_{i}$. Let us prove that
$\text{det}(\tilde{B}_{C_{i}})=\pm 2$. Since an odd unicyclic graph is
obtained by connecting trees to an odd cycle (say $C^{\prime}$), If we expand
$\text{det}(\tilde{B}_{C_{i}})$ along the row corresponding to a leaf of a
tree connected to $C^{\prime}$, it reduces to a similar determinant. By
expanding recursively along the rows corresponding to the leaves of the graph,
we obtain

$\text{det}(\tilde{B}_{C_{i}})=\pm\text{det}(B_{C^{\prime}}).$

Now it is enough to show that $\text{det}(B_{C^{\prime}})=2$. Observe that we
have

$\text{det}(B_{C^{\prime}})=\text{det}\left(\begin{array}[]{@{}c c c c
<EMAIL_ADDRESS>1&1&0&...&0\\\ .&.&&&\\\ .&&.&&\\\ .&&&.&\\\
0&...&0&1&1\end{array}\right).$

Expanding the determinant in the right hand side along the first row, since
there are odd number of rows and columns, we get

$\text{det}(B_{C^{\prime}})=\text{det}\left(\begin{array}[]{@{}c c c c
<EMAIL_ADDRESS>1&1&0&...&0\\\ .&.&&&\\\ .&&.&&\\\ .&&&.&\\\
0&...&0&1&1\end{array}\right)+\text{det}\left(\begin{array}[]{@{}c c c c
<EMAIL_ADDRESS>0&1&1&...&0\\\ .&.&&&\\\ .&&.&&\\\ .&&&.&\\\
0&...&0&0&1\end{array}\right).$

Now to compute the two determinants in the right hand side, we expand the
first determinant recursively along the rows and the second along the columns
and we obtain that these two determinants are equal to $1$. Hence we conclude
that

$\text{det}(\tilde{B}_{C_{i}})=\pm 2.$

Acknowledgments: Yu.H. acknowledges financial supports from the Grant-in-Aid
of Scientific Research (C) Japan Society for the Promotion of Science (Grant
No. 18K03401). M.S. acknowledges financial supports from JST SPRING (Grant No.
JPMJSP2114). E.S. acknowledges financial supports from the Grant-in-Aid of
Scientific Research (C) Japan Society for the Promotion of Science (Grant No.
19K03616) and Research Origin for Dressed Photon. We would like to thank prof.
Hajime Tanaka for the invaluable discussions and the comments which were very
useful to carry out this study.

## References

  * [1] Ambainis, A. (2003) Quantum walks and their algorithmic applications. Int. J. Quantum Inf., 1 (04), 507-518.
  * [2] Biggs, N. (1993) Algebraic Graph Theory (2nd ed.). Cambridge University Press.
  * [3] Boettcher,S., Varghese, C. and Novotny,M.A., Quantum transport through hierarchical structures, Phys. Rev. E 83 041106 (2011).
  * [4] Bollobás, B. (2013) Modern Graph Theory. Springer.
  * [5] Cvetkovic, D.M., Rowlinson, P. and Simic, S. (2007) Signless Laplacians of finite graphs. Linear Algebra Appl. , 423(1), 155-171.
  * [6] Cvetkovic, D.M., Rowlinson, P. and Simic, S. (2010) An introduction to the theory of graph spectra. Cambridge: Cambridge University Press.
  * [7] Domany, E., Alexander, S., Bensimon, D. and Kadanaff, L.P., Solution to the Schrödinger equation on some fractal lattices, Phys. Rev. B 28 (1998), 3100–3123.
  * [8] Doyle, P. G., and Snell, J. L. (1984). Random walks and electric networks (Vol. 22). American Mathematical Socety.
  * [9] Farhi,E. and Gutmann, S. Quantum computation and decision trees, Phys. Rev. A 58 (1998), 915–928.
  * [10] Feldman, E. and Hillery, M. (2005) Quantum walks on graphs and quantum scattering theory. Contemp. Math. 381, 71.
  * [11] Feldman, E. and Hillery, M. (2007) Modifying quantum walks: a scattering theory approach. J. Phys. A: Math. Theor. 40, 11343.
  * [12] Chris Godsil, Hanmeng Zhan, Discrete-Time Quantum Walks and Graph Structures, Journal of Combinatorial Theory, Series A 167 (2019) pp.181-212.
  * [13] Grover, L.K. (1997) Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett., 79(2), 325.
  * [14] Higuchi, Yu., Konno, N., Sato, I. and Segawa, E. (2014) Spectral and asymptotic properties of Grover walks on crystal lattices. J. Funct. Anal. 267., 4197–4235.
  * [15] Higuchi, Yu., Sabri, M. and Segawa, E. (2020) Electric Circuit Induced by Quantum Walk. J. Stat. Phys., 181, 603-617.
  * [16] Higuchi, Yu. and Segawa, E. (2018) Quantum walks induced by Dirichlet random walks on infinite trees, J. Phys. A: Math. Theor., 51, 075303\.
  * [17] Higuchi, Yu. and Segawa, E. (2019) A dynamical system induced by quantum walk. J. Phys. A: Math. Theor., 52, 395202\.
  * [18] Konno, N. (2008) Quantum Walks, In: Quantum Potential Theory pp.309-452, Springer.
  * [19] Konno, N. and Takei, M. (2015) The non-uniform stationary measure for discrete-time quantum walks in one dimension. Quantum Inf. Comput. 15(11,12) pp.1060-1075.
  * [20] Manouchehri, K. and Wang, J. (2014) Physical Implementation of Quantum Walks. Springer.
  * [21] Jan Mareš, Jaroslav Novotný, Igor Jex, Percolated quantum walks with a general shift operator: From trapping to transport, Phys.Rev.A.99 (2019) 042129.
  * [22] Portugal, R. (2018) Quantum Walks and Search Algorithms (2nd ed.). Springer.
  * [23] Shenvi, N., Kempe, J., and Whaley, K. B. (2003) Quantum random-walk search algorithm. Phys. Rev. A, 67(5), 052307.


† Rutgers, The State University of New Jersey, Piscataway, NJ
‡Princeton University, Princeton, NJ

# Deep Reinforcement Learning for IRS phase shift design in spatiotemporally
correlated environments

###### Abstract

The paper studies the problem of designing the Intelligent Reflecting Surface
(IRS) phase shifters for Multiple Input Single Output (MISO) communication
systems in spatiotemporally correlated channel environments, where the
destination can move within a confined area. The objective is to maximize the
expected sum of SNRs at the receiver over infinite time horizons. The problem
formulation gives rise to a Markov Decision Process (MDP). We propose a deep
actor-critic algorithm that accounts for channel correlations and destination
motion by constructing the state representation to include the current
position of the receiver and the phase shift values and receiver positions
that correspond to a window of previous time steps. The channel variability
induces high frequency components on the spectrum of the underlying value
function. We propose the preprocessing of the critic’s input with a Fourier
kernel which enables stable value learning. Finally, we investigate the use of
the destination SNR as a component of the designed MDP state, which is common
practice in previous work. We provide empirical evidence that, when the
channels are spatiotemporally correlated, the inclusion of the SNR in the
state representation interacts with function approximation in ways that
inhibit convergence.

Index Terms—  Intelligent Reflecting Surfaces, deep learning, reinforcement
learning

##  1 Introduction

The emergence of Intelligent Reflecting Surfaces (IRSs) [1] paves yet another
avenue for impactful research in the area of Wireless Communications. IRS
typically consists of a panel of passive reflective elements. Each element’s
reflection coefficient can be explicitly controlled independently of the
coefficients of the other elements. Consequently, the deployment of IRS
introduces a number of new degrees of freedom for wireless system design.
Therefore, holds the promise for performance improvements in terms of Quality-
of-Service (QoS) [2], security [3] and energy preservation [4].

For these ambitions to materialize, there needs to be a collective effort
towards developing regimens that decide upon the state of the IRS phase
shifters on the fly so as to imprint desirable conditions on the signal
propagation environment. Typically, the phase shift design aspiration induces
the formulation of NP hard problems. The authors in [5, 6] propose IRS phase
shift design approaches that are predicated upon semidefinite relaxations. The
performance of said methods is compelling, but the methods induce high
computational complexity ($\mathcal{O}(n^{6})$ where $n$ is the number of IRS
phase shifters).

Due to the need for low computational complexity, researchers turned towards
the employment of data-driven approaches for IRS phase-shift design. The
authors in [7] employ graph neural networks for estimating the IRS phase
shifters. The neural network is trained, in a supervised fashion, to estimate
the phase shift coefficients from channel pilots. The works in [8, 9] also
pose the IRS phase shift design as a supervised learning problem and use
labels to train a neural network to map channel measurements to phase shift
values. Supervised learning methods require the availability of ground truth
labels which are scarce for the problem at hand. Second, the supervised
learning regimes assume that channel data are i.i.d samples from the same
stationary distribution. This view is inadequate when the channels exhibit
correlations with respect to time and space. This is mostly the case for urban
communications due to shadowing [10].

Both shortcoming of supervised learning can be surpassed by the employment of
deep Reinforcement Learning (RL). In the case of deep RL there is no need for
labels, just measurements of a reward signal which can be the QoS metric of
interest (SNR). Furthermore, the i.i.d assumption for the channel measurements
can be lifted and the presupposition for spatiotemporal channel correlations
can be readily adopted. Nonetheless such a setup has not been studied yet, to
the best of our knowledge. The authors in [11] investigate a communication
scenario between a MIMO source and a mobile destination, assisted by a single
IRS. They benchmark the performance of a simple deep RL algorithm against
multiple numerical methods under highly noisy channels. They demonstrate that
the deep RL method is noticeably more robust with respect to noise. This
provides strong incentive towards developing deep RL algorithms for IRS phase
shift optimization. RL approaches have previously been employed for IRS phase
shift design in single-user [12, 11] and multi-user [13, 14] set ups. We
differentiate from the aforementioned approaches in the following ways. First,
all previous methods do not assume the spatiotemporal correlations of the
channels. We provide an algorithm that is specifically designed to address the
case of spatiotemporally correlated channels. Channel correlations are very
prominent in urban communication environments and arise due to shadowing.
Furthermore, the underlying value functions of MDPs that depend on
spatiotemporally correlated channels typically possess high frequencies in the
corresponding spectra [15]. Recent results in deep learning regression
demonstrate the inability of feedforward neural networks to represent high
frequency functions [16] (a phenomenon coined as Spectral Bias). Motivated by
recent results in graphics [17], we propose to preprocess the input of the
critic with a Fourier kernel to overcome the Spectral Bias. Finally, we
investigate the inclusion of the destination SNR in the representation of the
MDP state. This has been common practice in previous work [12, 11, 13]. We
showcase that, for spatiotemporally varying channels, including the SNR in the
state interacts undesirably with function approximation and causes divergence
and instability.

Fig. 1: IRS-aided single-user MISO

##  2 Signal Model

We consider a Multiple-Input-Single-Output (MISO) Communication system, as
shown in Fig. 1. The source is a Uniform Linear Array (ULA) with $N$ antennas.
The IRS is a panel of $M=M_{x}\times M_{y}$ passive phase shift elements. The
source-IRS and IRS-destination channels are denoted by
$\mathbf{G}\in\mathbb{C}^{M\times N}$, and $\mathbf{h}\in\mathbb{C}^{M\times
1}$, respectively. The IRS phase shifts are denoted by
$\theta_{i}\in[-\pi,\pi]$, $i=1,\dots M$. The source transmits symbol
$\mu(t)\in\mathbb{C}$, precoded by $\mathbf{b}\in\mathbb{C}^{N\times 1}$, with
$\lVert\mathbf{b}\rVert^{2}\leq P_{max}$. We assume that there is no direct
link from the source to the destination, so the propagation path goes through
the IRS. The received signal is

$y=\mathbf{h}^{H}\mathbf{\Phi}\mathbf{G}\mathbf{b}\mu+n\vspace{-0.2cm}$ (1)

where $\mathbf{\Phi}=\text{diag}(e^{j\theta_{1}},e^{j\theta_{2}},\dots
e^{j\theta_{M}})$, $n\sim\mathcal{C}\mathcal{N}\left(0,\sigma^{2}\right)$ is
the reception noise at the destination and $\mathbb{E}\left[\mu^{2}\right]=1$.
If we assume that the phase shifters are fixed ($\mathbf{\Phi}$ is fixed),
then the optimal beamforming weights are given by [6]:

$\mathbf{b}^{*}=\sqrt{P_{max}}\frac{(\mathbf{h}^{H}\mathbf{\Phi}\mathbf{G})^{H}}{\lVert\mathbf{h}^{H}\mathbf{\Phi}\mathbf{G}\rVert}\vspace{-0.3cm}$
(2)

We adopt the following assumptions. First of all, both channels (BS-IRS and
IRS-destination) exhibit correlations with respect to time, so
$\mathbf{h}=\mathbf{h}(t)$ and $\mathbf{G}=\mathbf{G}(t)$. We also assume that
the destination can move, but its motion is confined to a small area of space.
The channel from the IRS to the destination also exhibits correlations with
respect to space that depend on the relative position of the destination to
the IRS. So, $\mathbf{h}=\mathbf{h}(t,\mathbf{x}_{t})$, where
$\mathbf{x}_{t}\in\mathbb{R}^{3}$ is the position of the destination in the
$3D$ space at time step $t$; $\mathbf{x}_{t}$ is assumed known at the IRS
controller, estimated by a coexistent radar perception system [18]. One way to
design the phase shift matrix $\mathbf{\Phi}(t)$ at time $t$, assuming that
the channels $\mathbf{h}(t)$ and $\mathbf{G}(t,\mathbf{x}_{t}$ are known, is
to solve the following problem:

$\displaystyle\max_{\mathbf{\Phi}(t)}$ $\displaystyle
SNR(t)\equiv\frac{1}{\sigma^{2}}{\left\lVert\mathbf{h}\left(t,\mathbf{x}_{t}\right)^{H}\mathbf{\Phi}(t)\mathbf{G}(t)\right\rVert^{2}}$
(3) s.t.
$\displaystyle\left\lvert\mathbf{\Phi}(t)_{(i,i)}\right\rvert=1,\hskip
5.69046pt\forall i=1,2,\dots,M.$

Even if one neglects the computational overhead of estimating the channels at
each time step (which is not negligible in practice), solving problem (3)
induces complexity $\mathcal{O}(M^{6})$ [5]. The calculation cost of the
solution at every time step is prohibitive for real system deployment.

Instead of solving the above problem, we design an actor-critic algorithm that
learns a policy which maps the position of the destination at time step $t$
and information from previous time steps to the IRS phase shift values of the
current time step. The policy is constructed so as to maximize the expected
sum of destination SNRs over infinite time horizons of system operation. In
such case, after learning the policy/actor, the IRS phase shift computation is
a simple forward pass through the policy function.

##  3 Off-Policy Deep RL

Reinforcement Learning (RL) studies the class of problems where an agent
interacts with the environment in a sequence of states, actions and rewards.
This gives birth to a Markov Decision Process (MDP). The MDP is defined as a
tuple $\langle S,A,R,P,p,\gamma\rangle$, where $S$ is the state space, $A$ is
the action space, $R:S\times A\rightarrow\mathbb{R}$ is the reward function
and $P:S\times A\rightarrow S$ is the transition function that depends on the
environment dynamics. $p(\mathbf{s})$ is the initial state distribution and
$\gamma\in(0,1)$ is the discount factor that quantifies how ”far-sighted” the
agent is. The goal of RL is to learn a mapping from states to actions, namely
a policy, $\pi(\mathbf{a}|\mathbf{s})$ that maximizes the expected discounted
sum of rewards
$J=\mathbb{E}\Bigl{[}\sum_{t=0}^{\infty}\gamma^{t}R(\mathbf{s}_{t},\mathbf{a}_{t})\Bigr{]}=\mathbb{E}\Bigl{[}\sum_{t=0}^{\infty}\gamma^{t}r(t)\Bigr{]}$.

The state-action value function $Q^{\pi}$ is defined as the expected
discounted sum of rewards starting from a state-action pair and following the
policy $\pi$ thereafter.

$Q^{\pi}(\mathbf{s},\mathbf{a})=\mathbb{E}\Bigl{[}\sum_{t=0}^{\infty}\gamma^{t}R(\mathbf{s}_{t},\mathbf{a}_{t})|(\mathbf{s}_{0},\mathbf{a}_{0})=(\mathbf{s},\mathbf{a})\Bigr{]}\vspace{-0.4cm}$
(4)

The optimal value function $Q^{*}(\mathbf{s},\mathbf{a})$ is the fixed point
of the Bellman backup operator:

$B^{*}Q(\mathbf{s},\mathbf{a})=\mathbb{E}_{\mathbf{s}^{\prime}\sim
P}\Bigl{[}R(\mathbf{s},\mathbf{a})+\gamma\max_{\mathbf{a}^{\prime}}Q(\mathbf{s}^{\prime},\mathbf{a}^{\prime})\Bigr{]}\vspace{-0.2cm}$
(5)

In off-policy RL, we assume the availability of an Experience Replay that
contains $N_{exp}$ transitions from the interaction of the agent with the
environment
$\left(D=\\{\mathbf{s}_{i},\mathbf{a}_{i},\mathbf{s}_{i}^{\prime},r_{i}\\}_{i=1}^{N_{exp}}\right)$
. The optimal state-action value function is parameterized as a neural network
with parameters $\mathbf{w}$, denoted as
$Q_{\mathbf{w}}(\mathbf{s},\mathbf{a})$. The process of approximating the
value function entails the sampling of a batch of transitions from the
Experience Replay and the following parameter update:

$\mathbf{w}\rightarrow\mathbf{w}+2\eta\mathbb{E}_{(\mathbf{s},\mathbf{a},\mathbf{s}^{\prime},r)\sim
D}\\\
\Bigl{[}\Bigl{(}B^{*}Q_{\mathbf{w}}(\mathbf{s},\mathbf{a})-Q_{\mathbf{w}}(\mathbf{s},\mathbf{a})\Bigr{)}\nabla_{\mathbf{w}}Q_{\mathbf{w}}(\mathbf{s},\mathbf{a})\Bigr{]}\vspace{-1.5cm}$
(6)

The process of learning the value function is usually unstable due to the fact
that the bootstrapping target
$\Bigl{(}B^{*}Q_{\mathbf{w}}(\mathbf{s},\mathbf{a})\Bigr{)}$ depends on the
estimator $Q_{\mathbf{w}}(\mathbf{s},\mathbf{a})$. One popular heuristic
includes the use of a target network with parameters $\bm{\psi}$ for computing
the bootstrapping target. The parameter vector $\bm{\psi}$ slowly tracks the
parameter vector $\mathbf{w}$ as proposed in [19].

The policy is parameterized by a neural network with parameters $\bm{\phi}$,
denoted as $\pi_{\bm{\phi}}(\mathbf{s})$. The policy is updated by the
following rule (deterministic policy gradient theorem):

$\bm{\phi}\rightarrow\bm{\phi}+\eta\mathbb{E}_{\mathbf{s}\sim
D}\Bigl{[}\nabla_{\mathbf{a}}Q_{\mathbf{w}}(\mathbf{s},\mathbf{a})|_{\mathbf{a}=\pi_{\bm{\phi}}(\mathbf{s})}\nabla_{\bm{\phi}}\pi_{\bm{\phi}}(\mathbf{s})\Bigr{]}\vspace{-0.3cm}$
(7)

##  4 Deep RL for IRS phase shift design

In order to develop the RL algorithm for the IRS phase shift design we need to
define the elements of the MDP.

State: The first component of the state is the position of the destination,
$\mathbf{x}_{t}\in\mathbb{R}^{3}$. It can be estimated by a deployed radar
perception system. Since the channels evolve as a temporally correlated
process, the IRS phase shifters will also exhibit spatiotemporal correlations.
We, therefore, include the phase shift values of the IRS for a window of
previous time steps along with the destination positions at these time steps.
The window length is denoted as $W$. The incentive is that, by including the
phase shifters and destination locations for enough previous time steps, we
can safely assume that the state is Markovian. In that sense, we operate in
the context of a fully observable MDP. This nuance is similar to the practice
in [20], where the state is the concatenation of consecutive frames for the
environments of the Atari Domain.

$\mathbf{s}_{t}=\left[\mathbf{x}_{t},\mathbf{x}_{t-1},\theta_{1}^{t-1},\dots,\theta_{M}^{t-1},\dots,\mathbf{x}_{t-W},\dots,\theta_{M}^{t-W}\right],\vspace{-0.3cm}$

where $\theta_{i}^{j}$ is the value of the IRS phase shifter $i$ at time step
$j$.

Action: The action is the component-wise difference between the phase shift
elements of the current step and those of the previous step:

$\mathbf{a}_{t}=\left[\delta\theta^{t}_{1},\delta\theta^{t}_{2},\dots\delta\theta^{t}_{M}\right],\vspace{-0.3cm}$

where $\delta\theta^{t}_{i}=\theta_{i}^{t}-\theta_{i}^{t-1}$.

Reward: The reward is the destination SNR at step $t$:

$r(t)=SNR(t).\vspace{-0.3cm}$

We adopt the DDPG [19] algorithm to learn the policy that maps the agent’s
state to the phase shifters of the IRS. We employ $3$ main networks, namely
the actor network, $\pi_{\phi}$, and the critic networks, $Q_{w_{1}}$ and
$Q_{w_{2}}$. At every update step, we sample a batch of transitions from the
Experience Replay and update the $2$ critic networks with the update rule of
eq. (6) and the actor with the update rule of eq. (7). The $2$ critic networks
are trained independently, but the minimum of the $2$ is used for the update
of the policy (eq. (7)) to hedge against overestimation. We employ
corresponding target networks for all the main ones and update their
parameters following the framework in [19].

Each neural network is a Multilayer Perceptron with ReLU activations (ReLU
MLP). A critical question is how to ensure that the unit modulus constraints
of problem (3) are satisfied during training. We address the challenge by
explicitly designing the actor architecture. In particular, the in-between-
layer activations of the actor are ReLUs, but the activation of the output
layer is hyperbolic tangent (Tanh). The Tanh squashes each output component to
the $\left[-1,1\right]$ range. Subsequently, we multiply each output component
with $\pi$. Therefore, we ensure that the output of the actor belongs to
$\left[-\pi,\pi\right]^{M}$. Since the actor estimates the difference between
the phase shifters of the current time step and those of the previous time
step, we clip each resulting phase shifter to $\left[-\pi,\pi\right]$ for
every IRS element at every time step. We denote this variation as RL-IRS-Base.

It has been common practice, when employing Deep RL for IRS phase shift
design, to include the destination service metric (SNR) in the state
representation [12, 11, 13]. Even though such a choice might seem intuitive,
the way that it interacts with function approximation remains elusive. We
implement a variation of the RL-IRS-Base that includes the destination SNR as
a component of the state to test whether the aforementioned design choice is
appropriate for the case of spatiotemporally correlated channels. We denote
this variation as RL-IRS-SNR-state.

###  4.1 Fourier Preprocessing

As discussed in [15, 21], value functions that depend on spatiotemporally
correlated communication channels typically inhere high frequency content.
When it comes to the RL-IRS-Base algorithm, the critics are ReLU MLPs that
regress the value function of the formulated MDP. The value function depends
on spatiotemporally correlated channels. Due to spectral bias, the critic
might not be able to learn the high frequencies of the value function. Since
the policy is updated to select the action that maximizes the critic estimate
at each state, inaccurate value estimation results in suboptimal policies
and/or divergence. We propose the preprocessing of the state-action pair with
a random Fourier Kernel before passing it through the critic. We denote as
$\mathbf{\tilde{s}}\in\mathbb{R}^{(W+1)(M+3)}$ the concatenation of state
$\mathbf{s}$ and action $\mathbf{a}$, i.e.,

$\mathbf{\tilde{s}}=[\mathbf{s},\mathbf{a}]^{\mathsf{T}}\rightarrow\mathbf{v}=[cos(2\pi{\bf
B}\mathbf{\mathbf{\tilde{s}}}),sin(2\pi{\bf
B}\tilde{s})]^{\mathsf{T}},\vspace{-0.2cm}$ (8)

where matrix ${\bf B}$ is the transformation Kernel. Each element of ${\bf B}$
is drawn from $\mathcal{N}(0,\sigma_{{\bf B}}^{2})$. The operations
$cos(\cdot)$ and $sin(\cdot)$ in (8) are applied element-wise. The variation
that employs the Fourier preprocessing is denoted as RL-IRS-FF.

Fig. 2: The training performance of the $3$ proposed algorithms for $50$
episodes. Each episode is comprised by $300$ time steps. Each curve is the
average over $10$ seeds.

##  5 Experiments

We simulate a scenario as in Fig. 1. The operation space is a $3$D cube
$(20^{3}m^{3})$, discretized into cube cells of volume $(1m^{3})$. The source
and IRS positions are fixed. The destination can freely move in an area within
$4$ cube cells. It occupies one cell per time slot and can also move to a
neighboring cell at the subsequent slot. We simulate the channels so that they
have statistics as described in [22]. The log-magnitude of the channel has $3$
additive components, the pathloss with exponent $l=2.3$, the multipath, which
is i.i.d zero-mean Gaussian with variance $\sigma_{\xi}=0.6$, and the
shadowing which is a a zero-mean Gaussian correlated in time and space. The
correlation distance is $c_{1}=1.2$, the correlation time $c_{2}=5$, and the
shadowing power is $\eta^{2}=6$. The source transmit power is $P_{max}=65dBm$.
The noise variance at the destination is $\sigma^{2}=0.5$. These parameters
are consistent with real measurements [10] for urban channels. Each neural
network is an MLP with $3$ layers. Each layer consists of $400$ neurons. We
employ the Adam optimizer for the updates, with a learning rate of $2$e-$4$
and batch size of $64$. The elements of the Fourier kernel are drawn from a
gaussian distribution with variance $0.01$. The Experience Replay size is
$1$e+$6$ and the discount factor $\gamma$ is $0.99$. The source has $5$
antenna elements.

Fig. 3: The training performance of RL-IRS-FF for $3$ different values of the
window size $W$. Each episode is comprised by $300$ time steps and each curve
is an average over $10$ seeds. Fig. 4: The performances of RL-IRS-FF and RL-
IRS-Base, after convergence, with respect to the size of the IRS.

As can be inferred by Fig. 2, the algorithm that introduces the Fourier
preprocessing performs significantly better than both the base implementation
and the base implementation that includes the SNR at the state when it comes
to convergence speed and destination SNR (increase of approximately $1.5dB$) .
We attribute this to the amelioration of the Spectral Bias and, therefore, the
more precise estimation of the value function. Fig. 3 demonstrates the
performance of the RL-IRS-FF for $3$ different values of the window size $W$.
The performance is improved for larger window sizes and best performance is
exhibited for $W=5$ which is equal to the temporal correlation coefficient of
the channels. We noticed that stability requires a window size that is, at
least, equal to the coefficient of the temporal correlation. The experiments
for Figures 2 and 3 are conducted with an IRS of $20$ elements. Fig. 4
illustrates the peformances of RL-IRS-FF and RL-IRS-Base, after convergence,
with respect to the number of IRS elements. The Fourier features provide
consistent improvements as we scale to larger IRSs. Both approaches seem to
plateau at about $25$ elements. At this point, we have probably reached the
representation capacity of the critic. Further increase in performance for
IRSs of larger sizes would require an increase in the parameter size of the
networks (critics and actor). The variation that includes the SNR as a state
component is prone to divergence. We attribute this to the fact that, when the
channels are correlated, states that correspond to different destination
positions and different IRS phase shift values for a window $W$ of previous
time steps can result in similar SNRs. Therefore, by including the SNR in the
state, we implicitly cause state-aliasing, where intrinsically different
states are processed by the critic as similar. This agrees with results in
neural value approximation [23] which report that state-aliasing causes
instability during value learning.

##  6 Conclusion

The paper proposes a deep actor-critic algorithm for IRS phase shift design
for MISO communication systems and spatiotemporally correlated channels. The
variability of the correlated channels induces high frequency components on
the spectrum of the underlying value function. We propose the preprocessing of
the state-action vector with a Fourier Kernel before passing it through the
critic, which helps in the process of learning the high frequencies of the
value function. We empirically showcase that the inclusion of the SNR in the
state, a common practice in prior works, inhibits stability and convergence.
Further investigation on how the SNR as a state component interacts with value
function approximation will be part of future work.

## References

  * [1] Marco Di Renzo et al.  “Smart radio environments empowered by reconfigurable intelligent surfaces: How it works, state of research, and the road ahead”  In _IEEE journal on selected areas in communications_ 38.11 IEEE, 2020, pp. 2450–2525
  * [2] Tao Jiang and Yuanming Shi  “Over-the-air computation via intelligent reflecting surfaces”  In _2019 IEEE Global Communications Conference (GLOBECOM)_ , 2019, pp. 1–6  IEEE
  * [3] Xianghao Yu et al.  “Robust and secure wireless communications via intelligent reflecting surfaces”  In _IEEE Journal on Selected Areas in Communications_ 38.11 IEEE, 2020, pp. 2637–2652
  * [4] Chongwen Huang et al.  “Reconfigurable intelligent surfaces for energy efficiency in wireless communication”  In _IEEE Transactions on Wireless Communications_ 18.8 IEEE, 2019, pp. 4157–4170
  * [5] Xianghao Yu, Dongfang Xu and Robert Schober  “MISO Wireless Communication Systems via Intelligent Reflecting Surfaces : (Invited Paper)”  In _2019 IEEE/CIC International Conference on Communications in China (ICCC)_ , 2019, pp. 735–740  DOI: 10.1109/ICCChina.2019.8855810
  * [6] Qingqing Wu and Rui Zhang  “Intelligent reflecting surface enhanced wireless network via joint active and passive beamforming”  In _IEEE Transactions on Wireless Communications_ 18.11 IEEE, 2019, pp. 5394–5409
  * [7] Tao Jiang, Hei Victor Cheng and Wei Yu  “Learning to reflect and to beamform for intelligent reflecting surface with implicit channel estimation”  In _IEEE Journal on Selected Areas in Communications_ 39.7 IEEE, 2021, pp. 1931–1945
  * [8] Chongwen Huang, George C Alexandropoulos, Chau Yuen and Mérouane Debbah  “Indoor signal focusing with deep learning designed reconfigurable intelligent surfaces”  In _2019 IEEE 20th international workshop on signal processing advances in wireless communications (SPAWC)_ , 2019, pp. 1–5  IEEE
  * [9] Abdelrahman Taha, Muhammad Alrabeiah and Ahmed Alkhateeb  “Enabling large intelligent surfaces with compressive sensing and deep learning”  In _IEEE access_ 9 IEEE, 2021, pp. 44304–44321
  * [10] Rui Wang et al.  “Stationarity region of mm-wave channel based on outdoor microcellular measurements at 28 GHz”  In _MILCOM 2017-2017 IEEE Military Communications Conference (MILCOM)_ , 2017, pp. 782–787  IEEE
  * [11] Amal Feriani, Amine Mezghani and Ekram Hossain  “On the robustness of deep reinforcement learning in IRS-aided wireless communications systems”  In _arXiv preprint arXiv:2107.08293_ , 2021
  * [12] Keming Feng, Qisheng Wang, Xiao Li and Chao-Kai Wen  “Deep reinforcement learning based intelligent reflecting surface optimization for MISO communication systems”  In _IEEE Wireless Communications Letters_ 9.5 IEEE, 2020, pp. 745–749
  * [13] Chongwen Huang, Ronghong Mo and Chau Yuen  “Reconfigurable intelligent surface assisted multiuser MISO systems exploiting deep reinforcement learning”  In _IEEE Journal on Selected Areas in Communications_ 38.8 IEEE, 2020, pp. 1839–1850
  * [14] Canwei Zhong et al.  “Deep Reinforcement Learning-Based Optimization for IRS-Assisted Cognitive Radio Systems”  In _IEEE Transactions on Communications_ 70.6, 2022, pp. 3849–3864  DOI: 10.1109/TCOMM.2022.3171837
  * [15] Spilios Evmorfos, Konstantinos I. Diamantaras and Athina P. Petropulu  “Reinforcement Learning for Motion Policies in Mobile Relaying Networks”  In _IEEE Transactions on Signal Processing_ 70, 2022, pp. 850–861  DOI: 10.1109/TSP.2022.3141305
  * [16] Yuan Cao et al.  “Towards understanding the spectral bias of deep learning”  In _arXiv preprint arXiv:1912.01198_ , 2019
  * [17] Matthew Tancik et al.  “Fourier features let networks learn high frequency functions in low dimensional domains”  In _Advances in Neural Information Processing Systems_ 33, 2020, pp. 7537–7547
  * [18] Yikai Li and Athina Petropulu  “Dual-Function Radar-Communication System Aided by Intelligent Reflecting Surfaces”  In _arXiv preprint arXiv:2204.04721_ , 2022
  * [19] Timothy P Lillicrap et al.  “Continuous control with deep reinforcement learning”  In _arXiv preprint arXiv:1509.02971_ , 2015
  * [20] Volodymyr Mnih et al.  “Human-level control through deep reinforcement learning”  In _nature_ 518.7540 Nature Publishing Group, 2015, pp. 529–533
  * [21] Spilios Evmorfos and Athina P. Petropulu  “Deep Actor-Critic for Continuous 3D Motion Control in Mobile Relay Beamforming Networks”  In _ICASSP 2022 - 2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2022, pp. 5353–5357  DOI: 10.1109/ICASSP43922.2022.9746407
  * [22] Dionysios S Kalogerias and Athina P Petropulu  “Spatially Controlled Relay Beamforming: $2$-Stage Optimal Policies”  In _arXiv preprint arXiv:1705.07463_ , 2017
  * [23] Joshua Achiam, Ethan Knight and Pieter Abbeel  “Towards characterizing divergence in deep q-learning”  In _arXiv preprint arXiv:1903.08894_ , 2019