A comfortable graph structure for Grover walk

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

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

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.

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

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.

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.

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

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

for any $o(a)\notin V_{0}$. We set the $l^{\infty}$-initial state by using a complex value $z$ with $|z|=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.

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,

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

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

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

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

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.

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.

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

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.

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})$.

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

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.

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

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):

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

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

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

and hence

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

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

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

and hence

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

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

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

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:

We set

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.

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

and for $z=1$,