Localization of Discrete Time Quantum Walks on the Glued Trees

Abstract

In this paper, we consider the time averaged distribution of discrete time quantum walks on the glued trees. In order to analyze the walks on the glued trees, we consider a reduction to the walks on path graphs. Using a spectral analysis of the Jacobi matrices defined by the corresponding random walks on the path graphs, we have a spectral decomposition of the time evolution operator of the quantum walks. We find significant contributions of the eigenvalues, ±1, of the Jacobi matrices to the time averaged limit distribution of the quantum walks. As a consequence, we obtain the lower bounds of the time averaged distribution.

1. Introduction

The discrete time quantum walks (DTQWs) as quantum counterparts of the random walks, which play important roles in various fields, have been attractive research objects in the last decade [1–8]. In the theory of quantum algorithms, quantum walks on various graphs also play important roles, for example, graph isomorphism testing and network characterization [9–12], search algorithms on the hypercube [13] or the glued binary tree [14] and an algorithm for element distinctness on the Johnson graph [15]. In these studies, the algorithms are often reduced to DTQWs on the path graphs. Therefore, investigations of DTQWs on the path graph corresponding to the original graphs are important. Rohde et al. [16] studied the periodic properties of entanglement for DTQW on the path determined by biased Hadamard coins numerically. Godsil [17] studied the time averaged distributions of continuous-time quantum walks on the path using the average mixing matrix. Ide et al. [18] studied the time averaged distribution of DTQWs on the path graph, which can be viewed as a quantization of random walks on the path. In this paper, we consider DTQWs on the path graphs corresponding to the random walks on the glued trees. We obtain lower bounds of the time averaged distribution of the DTQWs by using spectral analysis of the corresponding Jacobi matrices.

The rest of this paper is organized as follows. The definition of our DTQW is given in Section 2, and the main result of this paper is stated in Section 3. The remaining section (Section 4) is devoted to the proof of our result.

2. Definition of the DTQW

Let T_k(n) be the k-ary tree on ${\sum }_{h=1}^n{k}^{h-1}$ vertices (height = n), i.e., the graph which is constructed inductively as follows: We start with a vertex called the “root” of T_k(n) and set the height of the root = 1. We add k numbers of vertices and set the height of these vertices = 2. Then, we connect the root and all the vertices with its height = 2. Similarly, for every vertex with its height = h, we add k numbers of new vertices and set the height of these vertices = h + 1. Then, we connect the vertex with its height = h and all the new k vertices with their height = h + 1. Note that there are k^h−1 numbers of vertices with their height = h. We repeat this procedure, until all the vertices with its height = n − 1 connect with k numbers of new vertices with their height = n. We call each vertex with its height = n a “leaf”, because the degree of these vertices equals one. Note that the degree of the root equals k; the degree of the leaves is one, and the degree of all other vertices is k + 1.

In this paper, we consider the glued trees, G_k(2n), consisting of two k-ary trees, $T_k^1(n)$ and $T_k^2(n)$. The glued tree, G_k(2n), is constructed as follows: Each leaf in $T_k^1(n)$ and $T_k^2(n)$ has k numbers of “potential edges”. We select a pair of potential edges (e_i, e_j) at random, where e_i is a potential edge of a vertex, i, in $T_k^1(n)$ and e_j is that of j in $T_k^2(n)$. After that, we connect a pair of vertices, i and j, with an edge and erase the pair of potential edges, e_i and e_j. We continue this procedure until all the potential edges disappear. Note that the degree of the vertices in G_k(2n) except for the two roots of $T_k^1(n)$ and $T_k^2(n)$ are k + 1, and the degree of the roots are equal to k.

In a quantum search algorithm [14], it is known that the algorithms on the glued trees work on the path graphs. For the Grover walks on the spidernets, it can be shown that there is a subspace that is isomorphic to a DTQW on the path graph. On this subspace, the Grover walk behaves as the DTQW, which is called the Szegedy walk on the path graph (see [19] for more details). Using a similar argument, we can construct the Szegedy walks on the path graph corresponding to the Grover walks on the glued tree. Following these observations, we consider a reduction of G_k(2n) on the path graph, P_2n, on 2n numbers of vertices with the vertex set V (P_2n) = {1, 2, · · · 2n} and the edge set E(P_2n) = {(i, i+1) : i = 1, 2, . . . 2n − 1}. The results shown in this paper are restricted to the Szegedy walks on the path graph. However, the results describe the behaviors of the corresponding Grover walks on the glued tree. Therefore, it is useful to consider the Szegedy walks on the path graph.

First of all, we identify all the vertices with their height = h in $T_k^1(n)$ and as the vertex, h, in P_2n and all the vertices with their height = h in $T_k^2(n)$ as the vertex 2n − h + 1 in P_2n. Figure 1 shows an example of the glued tree with the k = 2 and n = 3 case. The figure also exhibits the corresponding path graph.

Recall that the simple random walk on $T_k^1(n)$ and $T_k^2(n)$ has the transition probabilities from a vertex, i, to a neighboring vertex, j, as:

$$p_{i,j}=\{\begin{array}{ll}\frac{k}{k+1},\hfill & \text{if\hspace{0.17em}the\hspace{0.17em}height\hspace{0.17em}of\hspace{0.17em}}j\hspace{0.17em}\text{equals\hspace{0.17em}that}\hspace{0.17em}\text{of\hspace{0.17em}}i\hspace{0.17em}\text{plus\hspace{0.17em}}1\hfill \\ \frac{1}{k+1},\hfill & \text{if\hspace{0.17em}the\hspace{0.17em}height\hspace{0.17em}of\hspace{0.17em}}j\hspace{0.17em}\text{equals}\hspace{0.17em}\text{that\hspace{0.17em}of\hspace{0.17em}}i\hspace{0.17em}\text{minus\hspace{0.17em}}1\hfill \end{array}$$

for the vertices, i, except for the roots and:

$$p_{i,j}=\frac{1}{k},\mathrm{\hspace{0.17em} }\mathrm{\hspace{0.17em} }\mathrm{\hspace{0.17em} }\text{if\hspace{0.17em}the}\hspace{0.17em}\text{height\hspace{0.17em}of\hspace{0.17em}}j\hspace{0.17em}\text{equals\hspace{0.17em}}2,$$

if the vertex, i, is the root. Based on this fact, we consider the following random walk on P_2n corresponding to G_k(2n): let p = 1/(k + 1) and q = k/(k + 1). The transition probabilities of the random walk is:

$$p_{i,i+1}=\{\begin{array}{ll}1,\hfill & \text{if\hspace{0.17em}}i=1,\hfill \\ q,\hfill & \text{if\hspace{0.17em}}i=2,\dots ,n,\hfill \\ p,\hfill & \text{if\hspace{0.17em}}i=n+1,\dots ,2n-1\hfill \end{array}$$

$$p_{i,i-1}=\{\begin{array}{ll}1,\hfill & \text{if\hspace{0.17em}}i=2n,\hfill \\ q,\hfill & \text{if\hspace{0.17em}}i=n+1,\dots ,2n-1\hfill \\ p,\hfill & \text{if\hspace{0.17em}}i=2,\dots ,n.\hfill \end{array}$$

Now, we define corresponding DTQWs, which we call the Szegedy walk [18,20,21] on P_2n with the general settings of transition probabilities p and q with p+q = 1. This is the reduced DTQW on the path graph from the original Grover walk on the glued tree. Let $\mathscr{H}$_2n = span{|0,R〉, |1, L〉, |1,R〉, . . . , |2n − 1, L〉, |2n − 1,R〉, |2n, L〉} be a Hilbert space with |i, J〉 = |i〉 ⊗ |J〉 (i ∈ V (P_2n), J ∈ {L,R}) the tensor product of elements of two orthonormal bases {|i〉 : i ∈ V (P_2n)} for the position of the walker and {|L〉 = ^T [1, 0], |R〉 = ^T [0, 1]} for the chirality, which means the direction of the motion of the walker, where ^TA denotes the transpose of a matrix, A. Then, we consider the time evolution operator, U⁽²ⁿ⁾, on $\mathscr{H}$_2n defined by U⁽²ⁿ⁾ = S⁽²ⁿ⁾C⁽²ⁿ⁾ with the following coin operator, C⁽²ⁿ⁾, and shift operator, S⁽²ⁿ⁾:

$$\begin{array}{l}{C}^{(2n)}=\mid 0\rangle \hspace{0.17em}\langle 0\mid \otimes \mid R\rangle \hspace{0.17em}\langle R\mid \\ +\sum _{j=1}^n\mid j\rangle \hspace{0.17em}\langle j\mid \otimes (2\mid {\phi }_1\rangle \hspace{0.17em}\langle {\phi }_1\mid -I_2\rangle +\sum _{j=n+1}^{2n}\mid j\rangle \hspace{0.17em}\langle j\mid \otimes (2\mid {\phi }_2\rangle \hspace{0.17em}\langle {\phi }_2\mid -I_2\rangle \\ +\mid 2n\rangle \hspace{0.17em}\langle 2n\mid \otimes \mid L\rangle \hspace{0.17em}\langle L\mid \\ S^{(2n)}\mid i,J\rangle =\{\begin{array}{cc}\mid i+1,L\rangle & \text{if\hspace{0.17em}}J=R\\ \mid i-1,R\rangle & \text{if\hspace{0.17em}}J=L\end{array}\end{array}$$

where $\mid {\phi }_1\rangle =\sqrt{p}\mid L\rangle +\sqrt{q}\mid R\rangle ,\mid {\phi }_2\rangle =\sqrt{q}\mid L\rangle +\sqrt{p}\mid R\rangle$ and I_n are the n × n identity matrix.

Let $X_t^{(2n)}$ be the position of our quantum walker at time t. The probability that the walker with initial state |ψ〉 is found at time t and the position, x, is defined by:

$${\mathbb{P}}_{\mid \psi \rangle }(X_t^{(2n)}=x)={\Vert (\mid x\rangle \hspace{0.17em}\langle x\mid \otimes I_2)\hspace{0.17em}{(U^{(2n)})}^t\mid \psi \rangle \Vert }^2$$

In this paper, we consider the DTQW starting from a vertex, i ∈ V (P_2n), and choose the initial chirality state with equal probability, i.e., we choose the initial state as |ψ〉₁ = |1〉⊗|R〉 for i = 1, |ψ〉_i = |i〉⊗|L〉 or |ψ〉_i = |i〉 ⊗ |R〉 with probability 1/2 for 2 ≤ i ≤ 2n − 1 or |ψ〉_2n = |2n〉 ⊗ |L〉 for i = 2n. For the sake of simplicity, we write ${\mathbb{P}}_i(X_t^{(2n)}=x)$ for ${\mathbb{P}}_{{\mid \psi \rangle }_i}(X_t^{(2n)}=x)$. Let the time averaged distribution:

$${\overline{p}}_i^{(2n)}(x)=\underset{T\to \infty }{\text{lim}}\mathbb{E}\hspace{0.17em}\left[\frac{1}{T}\sum _{t=0}^{T-1}{\mathbb{P}}_i(X_t^{(2n)}=x)\right]$$

where the expectation takes the choice of the initial chirality state. For the sake of simplicity, we only consider the i, x ∈ {1, . . . , n} case from now on.

3. Results

In this section, we show our main result on the time averaged distribution, ${\overline{p}}_i^{(2n)}(x)$. We allow i, x ∈ {1, . . . , n} to be fixed and diverging in n cases. We have the following properties for ${\overline{p}}_i^{(2n)}(x)$:

Theorem 3.1

The time averaged distribution, ${\overline{p}}_i^{(2n)}(x)$, is symmetric, i.e.,${\overline{p}}_i^{(2n)}(x)={\overline{p}}_{2n+1-i}^{(2n)}(x)$ and${\overline{p}}_i^{(2n)}(x)={\overline{p}}_i^{(2n)}(2n+1-x)$ for i, x ∈ {1, . . . , n}. The time averaged distribution has the following lower bounds:

$${\overline{p}}_i^{(2n)}(x)\ge \frac{{(p-q)}^2{(q/p)}^{i-1}}{2\hspace{0.17em}[{\delta }_1(i)+\{1-{\delta }_1(i)\}\hspace{0.17em}2q]\hspace{0.17em}{\{2p-{(q/p)}^{n-1}\}}^2}\left[{\delta }_1(x)+\{1-{\delta }_1(x)\}\frac{{(q/p)}^{x-1}}{q}\right]$$

This leads to the following result:

(1)

If p > q, then,

$$\underset{n\to \infty }{\text{lim\hspace{0.17em}inf}}{\overline{p}}_i^{(2n)}(x)\ge \{\begin{array}{ll}\frac{{(q/p)}^{i+x-2}}{2\hspace{0.17em}[{\delta }_1(i)+\{1-{\delta }_1(i)\}\hspace{0.17em}2q]\hspace{0.17em}[{\delta }_1(x)+\{1-{\delta }_1(x)\}\hspace{0.17em}q]}{\left(\frac{1-q/p}{2}\right)}^2,\hfill & \text{if\hspace{0.17em}}i+x<\infty \hfill \\ 0,\hfill & otherwise.\hfill \end{array}$$

(2)

If p < q, then,

$$\underset{n\to \infty }{\text{lim\hspace{0.17em}inf}}\hspace{0.17em}{\overline{p}}_i^{(2n)}(x)\ge \{\begin{array}{ll}{(p/q)}^k{\left(\frac{1-p/q}{2}\right)}^2,\hfill & if\hspace{0.17em}{\text{lim}}_{n\to \infty }\{2n-(i+x)\}=k\ge 0\hfill \\ 0,\hfill & otherwise.\hfill \end{array}$$

Note that the p = q = 1/2 case is included in the path graph case [18]. Theorem 3.1 shows that if the random walker is likely to go to the two roots, then the corresponding quantum walker localizes in vertices that are finitely close to the two roots. On the other hand, if the random walker is likely to go to the center of the glued tree, then the quantum walker localizes in vertices that are finitely close to the leaves in T¹(n) and T²(n). The proof of Theorem 3.1 is based on [18,21]. In this proof, the eigenvalues and eigenvectors of the following 2n × 2n finite Jacobi matrix, J_2n(p), induced by the random walk on P_2n, the (i, j) component of which is determined by ${\{J_{2n}(p)\}}_{ij}=\sqrt{p_{i,j}{p}_{j,i}}$ plays an important role:

$$J_{2n}(p)=\left[\begin{array}{cccccccccc}0& \sqrt{p}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}\\ \sqrt{p}& 0& \sqrt{pq}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& O& \hspace{0.17em}\\ \hspace{0.17em}& \sqrt{pq}& \ddots & \ddots & \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}\\ \hspace{0.17em}& \hspace{0.17em}& \ddots & \ddots & \sqrt{pq}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}\\ \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \sqrt{pq}& 0& q& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}\\ \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& q& 0& \sqrt{pq}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}\\ \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \sqrt{pq}& \ddots & \ddots & \hspace{0.17em}& \hspace{0.17em}\\ \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \ddots & \ddots & \sqrt{pq}& \hspace{0.17em}\\ \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \sqrt{pq}& 0& \sqrt{p}\\ O& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \sqrt{p}& 0\end{array}\right].$$

Indeed, as is shown in Lemma 4.3, the eigenvalues and the eigenvectors of the time evolution operator, U⁽²ⁿ⁾, are given by that of J_2n(p). On the other hand, the time averaged distribution is completely described by all the eigenvectors of U⁽²ⁿ⁾. Unfortunately, as is shown in Lemma 4.2, we cannot obtain all of the eigenvalues of J_2n(p) explicitly. The lower bounds in Theorem 3.1 are calculated by the eigenvectors corresponding to ±1 eigenvalues of U⁽²ⁿ⁾.

4. Proof of Theorem 3.1

In order to prove Theorem 3.1, we have the following result for the eigenspace of the Jacobi matrices at first:

Lemma 4.1

(The determinantal formula for a symmetric Jacobi matrix). Let J_2n be the following 2n×2n finite Jacobi matrix:

$$J_{2n}=\left[\begin{array}{cccccccc}{\alpha }_n& \sqrt{w_{n-1}}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}\\ \sqrt{w_{n-1}}& \ddots & \ddots & \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& O& \hspace{0.17em}\\ \hspace{0.17em}& \ddots & \ddots & \sqrt{w_1}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}\\ \hspace{0.17em}& \hspace{0.17em}& \sqrt{w_1}& {\alpha }_1& \sqrt{w_0}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}\\ \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \sqrt{w_0}& {\alpha }_1& \sqrt{w_1}& \hspace{0.17em}& \hspace{0.17em}\\ \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \sqrt{w_1}& \ddots & \ddots & \hspace{0.17em}\\ \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \ddots & \ddots & \sqrt{w_{n-1}}\\ O& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \sqrt{w_{n-1}}& {\alpha }_n\end{array}\right]$$

where α_i ∈ ℝ for i = 1, . . . n and w_i ∈ (0, ∞) for i = 0, . . . n − 1. Then, the characteristic equation of J_2n, i.e., det(λI_2n − J_2n) = 0, is:

$$\{(\lambda -{\alpha }_1-\sqrt{w_0})\hspace{0.17em}\text{det}(E_2)-w_1\hspace{0.17em}\text{det}(E_3)\}\hspace{0.17em}\{(\lambda -{\alpha }_1+\sqrt{w_0})\hspace{0.17em}\text{det}(E_2)-w_1\hspace{0.17em}\text{det}(E_3)\}=0$$

where E_k is the following (n − k + 1) × (n − k + 1) matrix:

$$E_k=\left[\begin{array}{ccccc}\lambda -{\alpha }_n& -\sqrt{w_{n-1}}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}\\ -\sqrt{w_{n-1}}& \ddots & \ddots & \hspace{0.17em}& O\\ \hspace{0.17em}& \ddots & \ddots & \ddots & \hspace{0.17em}\\ \hspace{0.17em}& \hspace{0.17em}& \ddots & \ddots & -\sqrt{w_k}\\ O& \hspace{0.17em}& \hspace{0.17em}& -\sqrt{w_k}& \lambda -{\alpha }_k\end{array}\right]$$

In addition:

(1)

The eigenvector corresponding to the eigenvalue, λ, with $(\lambda -{\alpha }_1-\sqrt{w_0})\hspace{0.17em}\text{det}(E_2)-w_1\hspace{0.17em}\text{det}(E_3)=0$

is:

$$T\hspace{0.17em}\left[1,\frac{\text{det}(E_n)}{\sqrt{w_{n-1}}},\frac{\text{det}(E_{n-1})}{\sqrt{w_{n-2}{w}_{n-1}}},\dots ,\frac{\text{det}(E_2)}{\sqrt{w_1\cdots w_{n-1}}},\frac{\text{det}(E_2)}{\sqrt{w_1\cdots w_{n-1}}},\dots ,\frac{\text{det}(E_{n-1})}{\sqrt{w_{n-2}{w}_{n-1}}},\frac{\text{det}(E_n)}{\sqrt{w_{n-1}}},1\right]$$

(2)

The eigenvector corresponding to the eigenvalue, λ, with $(\lambda -{\alpha }_1+\sqrt{w_0})\hspace{0.17em}\text{det}(E_2)-w_1\hspace{0.17em}\text{det}(E_3)=0$ is:

$$T\hspace{0.17em}\left[1,\frac{\text{det}(E_n)}{\sqrt{w_{n-1}}},\frac{\text{det}(E_{n-1})}{\sqrt{w_{n-2}{w}_{n-1}}},\dots ,\frac{\text{det}(E_2)}{\sqrt{w_1\cdots w_{n-1}}},-\frac{\text{det}(E_2)}{\sqrt{w_1\cdots w_{n-1}}},\dots ,-\frac{\text{det}(E_{n-1})}{\sqrt{w_{n-2}{w}_{n-1}}},-\frac{\text{det}(E_n)}{\sqrt{w_{n-1}}},1\right]$$

We should remark that every eigenvalue of J_2n is simple (see, e.g., [22]). Therefore, the eigenvectors are mutually orthogonal.

Proof of Lemma 4.1

Let:

$${\overline{E}}_k=\left[\begin{array}{ccccc}\lambda -{\alpha }_k& -\sqrt{w_k}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}\\ -\sqrt{w_k}& \ddots & \ddots & \hspace{0.17em}& O\\ \hspace{0.17em}& \ddots & \ddots & \ddots & \hspace{0.17em}\\ \hspace{0.17em}& \hspace{0.17em}& \ddots & \ddots & -\sqrt{w_{n-1}}\\ O& \hspace{0.17em}& \hspace{0.17em}& -\sqrt{w_{n-1}}& \lambda -{\alpha }_n\end{array}\right]$$

Note that by exchanging rows and columns, we have det(E_k) = det(Ē_k).

By expanding det(λI_2n − J_2n) in the n-th row, we have:

$$\begin{array}{l}\text{det}(\lambda I_{2n}-J_{2n})\\ =\sqrt{w_1}·\text{det\hspace{0.17em}}\left[\begin{array}{ccccc}{E}_3& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& O\\ -\sqrt{w_2}& -\sqrt{w_1}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}\\ \hspace{0.17em}& -\sqrt{w_0}& \lambda -{\alpha }_1& -\sqrt{w_1}& \hspace{0.17em}\\ \hspace{0.17em}& \hspace{0.17em}& -\sqrt{w_1}& \lambda -{\alpha }_2& -\sqrt{w_2}\\ \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& -\sqrt{w_2}& \hspace{0.17em}\\ O& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& {\overline{E}}_3\end{array}\right]\\ +(\lambda -{\alpha }_1)·\text{det\hspace{0.17em}}\left[\begin{array}{cc}{E}_2& O\\ O& {\overline{E}}_1\end{array}\right]+\sqrt{w_0}·\text{det\hspace{0.17em}}\left[\begin{array}{cccc}{E}_2& -\sqrt{w_1}& \hspace{0.17em}& O\\ \hspace{0.17em}& -\sqrt{w_0}& -\sqrt{w_1}& \hspace{0.17em}\\ \hspace{0.17em}& \hspace{0.17em}& \lambda -{\alpha }_2& -\sqrt{w_2}\\ \hspace{0.17em}& \hspace{0.17em}& -\sqrt{w_2}& \hspace{0.17em}\\ O& \hspace{0.17em}& \hspace{0.17em}& {\overline{E}}_3\end{array}\right]\end{array}$$

On the other hand, repeating the expansion of the determinants, we obtain:

$$\begin{array}{l}\text{det\hspace{0.17em}}\left[\begin{array}{ccccc}{E}_3& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& O\\ -\sqrt{w_2}& -\sqrt{w_1}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}\\ \hspace{0.17em}& -\sqrt{w_0}& \lambda -{\alpha }_1& -\sqrt{w_1}& \hspace{0.17em}\\ \hspace{0.17em}& \hspace{0.17em}& -\sqrt{w_1}& \lambda -{\alpha }_2& -\sqrt{w_2}\\ \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& -\sqrt{w_2}& \hspace{0.17em}\\ O& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& {\overline{E}}_3\end{array}\right]\\ =-\sqrt{w_1}(\lambda -{\alpha }_1)·\text{det\hspace{0.17em}}\left[\begin{array}{cc}{E}_3& O\\ O& {\overline{E}}_2\end{array}\right]+w_1\sqrt{w_1}·\text{det\hspace{0.17em}}\left[\begin{array}{cc}{E}_3& O\\ O& {\overline{E}}_3\end{array}\right]\end{array}$$

and:

$$\text{det\hspace{0.17em}}\left[\begin{array}{cccc}{E}_2& -\sqrt{w_1}& \hspace{0.17em}& O\\ \hspace{0.17em}& -\sqrt{w_0}& -\sqrt{w_1}& \hspace{0.17em}\\ \hspace{0.17em}& \hspace{0.17em}& \lambda -{\alpha }_2& -\sqrt{w_2}\\ \hspace{0.17em}& \hspace{0.17em}& -\sqrt{w_2}& \hspace{0.17em}\\ O& \hspace{0.17em}& \hspace{0.17em}& {\overline{E}}_3\end{array}\right]=-\sqrt{w_0}·\text{det\hspace{0.17em}}\left[\begin{array}{cc}{E}_2& O\\ O& {\overline{E}}_2\end{array}\right]$$

Therefore, we have:

$$\begin{array}{l}\text{det}(\lambda I_{2n}-J_{2n})\\ =-w_1(\lambda -{\alpha }_1)\text{det}(E_2)\text{det}(E_3)+w_1^2\text{det}{(E_3)}^2+(\lambda -{\alpha }_1)\hspace{0.17em}\text{det}(E_1)\hspace{0.17em}\text{det}(E_2)-w_0\text{det}{(E_2)}^2\\ ={(\lambda -{\alpha }_1)}^2\text{det}{(E_2)}^2-2w_1(\lambda -{\alpha }_1)\text{det}(E_2)\text{det}(E_3)+w_1^2\text{det}{(E_3)}^2-w_0\text{det}{(E_2)}^2\\ =\{(\lambda -{\alpha }_1-\sqrt{w_0})\hspace{0.17em}\text{det}(E_2)-w_1\hspace{0.17em}\text{det}(E_3)\}\hspace{0.17em}\{(\lambda -{\alpha }_1+\sqrt{w_0})\hspace{0.17em}\text{det}(E_2)-w_1\hspace{0.17em}\text{det}(E_3)\}\end{array}$$

For the second equality, we use the following relation:

$$\text{det}(E_k)=(\lambda -{\alpha }_k)\text{det}(E_{k+1})-w_k\text{det}(E_{k+2}),\hspace{0.17em}\text{for\hspace{0.17em}}k=2,\dots ,n-1$$

This completes the first half of the proof.

We can easily check that:

$$\sqrt{w_{n-1}}\times \frac{\text{det}(E_n)}{\sqrt{w_{n-1}}}=\text{det}(E_n)=(\lambda -{\alpha }_n)=(\lambda -{\alpha }_n)\times 1$$

and:

$$\begin{array}{l}\sqrt{w_{k-1}}\times \frac{\text{det}(E_k)}{\sqrt{w_{k-1}\cdots w_{n-1}}}=\frac{1}{\sqrt{w_k\cdots w_{n-1}}}\times \{(\lambda -{\alpha }_k)\text{det}(E_{k+1})-w_k\text{det}(E_{k+2})\}\\ =(\lambda -{\alpha }_k)\times \frac{\text{det}(E_{k+1})}{\sqrt{w_k\cdots w_{n-1}}}-\sqrt{w_k}\times \frac{\text{det}(E_{k+2})}{\sqrt{w_{k+1}\cdots w_{n-1}}}\end{array}$$

for k = 2, . . . , n − 1.

From the condition $(\lambda -{\alpha }_1-\sqrt{w_0})\hspace{0.17em}\text{det}(E_2)-w_1\hspace{0.17em}\text{det}(E_3)=0$, we have:

$$-\sqrt{w_1}\times \frac{\text{det}(E_3)}{\sqrt{w_2\cdots w_{n-1}}}+(\lambda -{\alpha }_1)\times \frac{\text{det}(E_2)}{\sqrt{w_1\cdots w_{n-1}}}-\sqrt{w_0}\times \frac{\text{det}(E_2)}{\sqrt{w_1\cdots w_{n-1}}}=0$$

Similarly, from the condition $(\lambda -{\alpha }_1+\sqrt{w_0})\hspace{0.17em}\text{det}(E_2)-w_1\hspace{0.17em}\text{det}(E_3)=0$, we have:

$$-\sqrt{w_1}\times \frac{\text{det}(E_3)}{\sqrt{w_2\cdots w_{n-1}}}+(\lambda -{\alpha }_1)\times \frac{\text{det}(E_2)}{\sqrt{w_1\cdots w_{n-1}}}-\sqrt{w_0}\times \left(-\frac{\text{det}(E_2)}{\sqrt{w_1\cdots w_{n-1}}}\right)=0$$

These conditions imply that the vectors described in the lemma are the corresponding eigenvectors.

Now, we apply Lemma 4.1 with parameters α₁ = · · · = α_n = 0, w₀ = q², w₂ = · · · = w_n−2 = pq and w_n−1 = p to the Jacobi matrix, J_2n(p). We obtain the following characteristic equation of J_2n(p):

$$\{(\lambda -q)\hspace{0.17em}\text{det}(E_{n-1}^{\prime })-pq\hspace{0.17em}\text{det}(E_{n-2}^{\prime })\}\hspace{0.17em}\{(\lambda +q)\hspace{0.17em}\text{det}(E_{n-1}^{\prime })-pq\hspace{0.17em}\text{det}(E_{n-2}^{\prime })\}=0$$

where $E_k^{\prime }$ is the following k × k matrix:

$$E_k^{\prime }=\left[\begin{array}{ccccc}\lambda & -\sqrt{p}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}\\ -\sqrt{p}& \lambda & -\sqrt{pq}& \hspace{0.17em}& O\\ \hspace{0.17em}& -\sqrt{pq}& \ddots & \ddots & \hspace{0.17em}\\ \hspace{0.17em}& \hspace{0.17em}& \ddots & \lambda & -\sqrt{pq}\\ O& \hspace{0.17em}& \hspace{0.17em}& -\sqrt{pq}& \lambda \end{array}\right]$$

Remark that for k ≥ 2,

$$\begin{array}{l}\text{det}(E_k^{\prime })=\lambda \hspace{0.17em}\text{det}(E_{k-1}^{\prime })-pq\hspace{0.17em}\text{det}(E_{k-2}^{\prime })=\lambda \hspace{0.17em}\text{det}(F_{k-1})-p\hspace{0.17em}\text{det}(F_{k-2})\\ \text{det}(F_k)=\lambda \hspace{0.17em}\text{det}(F_{k-1})-pq\hspace{0.17em}\text{det}(F_{k-2})\end{array}$$

where F_k is the following k × k matrix:

$$F_k=\left[\begin{array}{cccc}\lambda & -\sqrt{pq}& \hspace{0.17em}& \hspace{0.17em}\\ -\sqrt{pq}& \ddots & \ddots & O\\ \hspace{0.17em}& \ddots & \ddots & -\sqrt{pq}\\ O& \hspace{0.17em}& -\sqrt{pq}& \lambda \end{array}\right]$$

Using these facts, we can calculate:

$$(\lambda \mp q)\hspace{0.17em}\text{det}(E_{n-1}^{\prime })-pq\hspace{0.17em}\text{det}(E_{n-2}^{\prime })=(\lambda \mp 1)\hspace{0.17em}\{\text{det}(F_{n-1})\pm p\hspace{0.17em}\text{det}(F_{n-2})\}$$

Therefore, the eigenvalues of J_2n(p) are λ = ±1 and λ, satisfying det(F_n−1) ± p det(F_n−2) = 0.

For the λ = ±1 case, we have:

$$\begin{array}{l}\text{det}(E_k^{\prime })=\pm \text{det}(F_{k-1})-p\hspace{0.17em}\text{det}(F_{k-2})\\ \text{det}(F_k)=\pm \text{det}(F_{k-1})-pq\hspace{0.17em}\text{det}(F_{k-2})\end{array}$$

with det(F₁) = ±1 and det(F₀) = 1. This implies:

$$\text{det}(E_k^{\prime })={(\pm 1)}^k{q}^{k-1},\hspace{0.17em}\text{for\hspace{0.17em}}k\ge 1$$

On the other hand, for the λ ≠ = ±1 case, we identify det(F_k) as ${\sqrt{pq}}^k{\tilde{U}}_k(\lambda /\sqrt{pq})$, where Ũ_k(x) is the (monic) Chebyshev polynomial of the second kind, i.e., the series of polynomials satisfying the following recurrence relation:

$$\begin{array}{l}{\tilde{U}}_0(x)=1\\ {\tilde{U}}_1(x)=x\\ {\tilde{U}}_k(x)=x{\tilde{U}}_{k-1}(x)-{\tilde{U}}_{k-2}(x),\hspace{0.17em}\text{for\hspace{0.17em}}k\ge 2\end{array}$$

In this case, we obtain:

$$\begin{array}{l}\text{det}(F_{n-1})\pm p\hspace{0.17em}\text{det}(F_{n-2})=\sqrt{p}{\sqrt{pq}}^{n-2}\left\{\sqrt{q}{\tilde{U}}_{n-1}(\lambda /\sqrt{pq})\pm \sqrt{p}{\tilde{U}}_{n-2}(\lambda /\sqrt{pq})\right\}\\ \text{det}(E_k^{\prime })=\frac{{\sqrt{pq}}^k}{q}\left\{q{\tilde{U}}_k(\lambda /\sqrt{pq})-p{\tilde{U}}_{k-2}(\lambda /\sqrt{pq})\right\},\text{for\hspace{0.17em}}k\ge 1\end{array}$$

with Ũ₋₁(x) = 0. Combining these results with Lemma 4.1, we have the following lemma for the eigen space of J_2n(p):

Lemma 4.2

Let λ be the eigenvalue of J_2n(p) and v_λ be the corresponding eigenvector. Then, we have λ = ±1, and the remaining eigenvalues, λ, satisfy$\sqrt{q}{\tilde{U}}_{n-1}(\lambda /\sqrt{pq})\}\mp \sqrt{p}{\tilde{U}}_{n-2}(\lambda /\sqrt{pq})=0$. The i-th component, v_λ(i), of the eigenvectors, v_λ, is the following:

(1)

For λ = ±1

$$\begin{array}{l}{\mathbf{v}}_{\pm 1}(i)=\{\begin{array}{ll}1,\hfill & if\hspace{0.17em}i=1\hfill \\ {(\pm \sqrt{q/p})}^{i-1}/\sqrt{q},\hfill & if\hspace{0.17em}i=2,\dots ,n\hfill \\ \pm {(\pm \sqrt{q/p})}^{2n-i}/\sqrt{q},\hfill & if\hspace{0.17em}i=n+1,\dots ,2n-1\hfill \\ \pm 1,\hfill & if\hspace{0.17em}i=2n\hfill \end{array}\\ {\Vert {\mathbf{v}}_{\pm 1}\Vert }^2=\{\begin{array}{ll}2(2n-1),\hfill & if\hspace{0.17em}p=q=1/2\hfill \\ \frac{2}{p-q}\{2p-{(q/p)}^{n-1}\},\hfill & if\hspace{0.17em}p\ne q\hfill \end{array}\end{array}$$

(2)

For λ ≠ = ±1

$$\begin{array}{l}{\mathbf{v}}_{\lambda }(i)=\{\begin{array}{ll}1,\hfill & if\hspace{0.17em}i=1\hfill \\ \left\{q{\tilde{U}}_i(\lambda /\sqrt{pq})-p{\tilde{U}}_{i-2}(\lambda /\sqrt{pq})\right\}/q,\hfill & if\hspace{0.17em}i=2,\dots ,n\hfill \\ \pm \left\{q{\tilde{U}}_{2n-i}(\lambda /\sqrt{pq})-p{\tilde{U}}_{2n-i-2}(\lambda /\sqrt{pq})\right\}/\sqrt{q},\hfill & if\hspace{0.17em}i=n+1,\dots ,2n-1\hfill \\ \pm 1\hfill & if\hspace{0.17em}i=2n\hfill \end{array}\\ {\Vert {\mathbf{v}}_{\lambda }\Vert }^2=\frac{2(1-{\lambda }^2)S_{n-1}}{q},\hspace{0.17em}with\hspace{0.17em}{S}_k=\sum _{i=0}^{k-1}{\tilde{U}}_i(\lambda /\sqrt{pq})\end{array}$$

The last part of Lemma 4.2, i.e., ||v_λ||², is calculated as follows:

$$\begin{array}{l}{\Vert {\mathbf{v}}_{\lambda }\Vert }^2=2\hspace{0.17em}\left[1+q{\tilde{U}}_1^2(\lambda /\sqrt{pq})+\frac{1}{q}\sum _{i=2}^{n-1}{\left\{q{\tilde{U}}_i(\lambda /\sqrt{pq})-p{\tilde{U}}_{i-2}(\lambda /\sqrt{pq})\right\}}^2\right]\\ =2\hspace{0.17em}\left\{1+q{\tilde{U}}_1^2(\lambda /\sqrt{pq})+\sum _{i=2}^{n-1}{\tilde{U}}_i^2(\lambda /\sqrt{pq})-\frac{{\lambda }^2}{q}\sum _{i=2}^{n-2}{\tilde{U}}_i^2(\lambda /\sqrt{pq})+\frac{p}{q}\sum _{i=2}^{n-3}{\tilde{U}}_i^2(\lambda /\sqrt{pq})\right\}\end{array}$$

Here, we us ${\lambda }^2{\tilde{U}}_{i-1}^2(\lambda /\sqrt{pq})=pq{\tilde{U}}_i^2(\lambda /\sqrt{pq})+pq{\tilde{U}}_{i-2}^2(\lambda /\sqrt{pq})+2pq{\tilde{U}}_i(\lambda /pq){\tilde{U}}_{i-2}(\lambda /\sqrt{pq})$, obtained from the recurrence relation of the Chebyshev polynomial in the second equality. Using the recurrence relation of the Chebyshev polynomial, U₋₁(x) = 0 and the eigenvalue condition, we finally obtain:

$$\begin{array}{l}{\Vert {\mathbf{v}}_{\lambda }\Vert }^2=2\hspace{0.17em}\left\{\frac{(1-{\lambda }^2)S_n}{q}+\frac{{\lambda }^2-p}{q}{\tilde{U}}_{n-1}^2(\lambda /\sqrt{pq})-\frac{p}{q}{\tilde{U}}_{n-2}^2(\lambda /\sqrt{pq})\right\}\\ =2\left\{\frac{(1-{\lambda }^2)S_n}{q}+\frac{{\lambda }^2-(p+q)}{q}{\tilde{U}}_{n-1}^2(\lambda /\sqrt{pq})\right\}\\ =\frac{2(1-{\lambda }^2)S_{n-1}}{q}\end{array}$$

The eigen space of the time evolution operator, U⁽²ⁿ⁾, is described by that of J_2n(p) (Lemma 2 of [18]) as follows:

Lemma 4.3

Let λ_k (k = 1, . . . , 2n) be the eigenvalues of J_2n(p) and v_λk (k = 1, . . . , 2n) be the corresponding eigenvectors. We set λ₁ = 1 and λ_2n = −1. Then, the eigenvalues μ_k (k = 1,±2, . . . ,±(2n − 1), 2n) and corresponding eigenvectors u_k (k = 1,±2, . . . ,±(2n − 1), 2n) of U⁽²ⁿ⁾ are obtained as follows:

Let Ṽ_λ = v_λ/||v_λ|| and for k = 1, . . . 2n,

$$\begin{array}{l}{\mathbf{a}}_{{\lambda }_k}={\tilde{\mathbf{v}}}_{{\lambda }_k}(1)\mid 1,R\rangle \\ +\sum _{i=2}^n{\tilde{\mathbf{v}}}_{{\lambda }_k}(i)\mid i\rangle \otimes (\sqrt{p}\mid L)+\sqrt{q}\mid R\rangle )+\sum _{i=n+1}^{2n-1}{\tilde{\mathbf{v}}}_{{\lambda }_k}(i)\mid i\rangle \otimes (\sqrt{q}\mid L\rangle +\sqrt{p}\mid R\rangle )\\ +{\tilde{\mathbf{v}}}_{{\lambda }_k}(2n)\mid 2n,L\rangle \\ {\mathbf{b}}_{{\lambda }_k}=S^{(2n)}{\mathbf{a}}_{{\lambda }_k}\end{array}$$

Then, we have:

$$\begin{array}{ll}{\mu }_1=1,\hfill & {\mathbf{u}}_1={\mathbf{a}}_{{\lambda }_1}={\mathbf{a}}_1,\hfill \\ {\mu }_{\pm k}=\text{exp}(\pm i{\varphi }_{{\lambda }_k}),\hfill & {\mathbf{u}}_{\pm k}={\mathbf{a}}_{{\lambda }_k}-\text{exp}(\pm i{\varphi }_{{\lambda }_k}){\mathbf{b}}_{{\lambda }_k},\hspace{0.17em}where\hspace{0.17em}\text{cos\hspace{0.17em}}{\varphi }_{{\lambda }_k}={\lambda }_k,\hspace{0.17em}for\hspace{0.17em}k=2,\dots ,2n-1,\hfill \\ {\mu }_{2n}=-1,\hfill & {\mathbf{u}}_{2n}={\mathbf{a}}_{{\lambda }_{2n}}={\mathbf{a}}_{-1}.\hfill \end{array}$$

Now, we estimate the distribution ${\overline{p}}_i^{(2n)}$. By the assumption of the choice of the initial state, we have:

$${\overline{p}}_i^{(2n)}(x)=\{\begin{array}{ll}\underset{T\to \infty }{\text{lim}}\frac{1}{T}\sum _{t=0}^{T-1}{\Vert (\mid x\rangle \hspace{0.17em}\langle x\mid \otimes I_2)\hspace{0.17em}{(U^{(2n)})}^t\hspace{0.17em}(\mid 0\rangle \otimes \mid R\rangle )\Vert }^2,\hfill & \text{if\hspace{0.17em}}i=1\hfill \\ \underset{T\to \infty }{\text{lim}}\frac{1}{T}\sum _{t=0}^{T-1}\left\{\frac{1}{2}\sum _{J=L,R}{\Vert (\mid x\rangle \hspace{0.17em}\langle x\mid \otimes I_2)\hspace{0.17em}{(U^{(2n)})}^t\hspace{0.17em}(\mid i\rangle \otimes \mid J\rangle )\Vert }^2\right\},\hfill & \text{if\hspace{0.17em}}2\le i\le 2n-1\hfill \\ \underset{T\to \infty }{\text{lim}}\frac{1}{T}\sum _{t=0}^{T-1}{\Vert (\mid x\rangle \hspace{0.17em}\langle x\mid \otimes I_2)\hspace{0.17em}{(U^{(2n)})}^t\hspace{0.17em}(\mid n+1\rangle \otimes \mid L\rangle )\Vert }^2,\hfill & \text{if\hspace{0.17em}}i=2n\hfill \end{array}$$

Using the spectral decomposition ${(U^{(2n)})}^t={\sum }_k{\mu }_k^t{\mathbf{u}}_k{\mathbf{u}}_k^{†}$ and ${\text{lim}}_{T\to \infty }(1/T){\sum }_{t=0}^{T-1}{e}^{i\theta t}={\delta }_0(\theta )\hspace{0.17em}(\text{mod\hspace{0.17em}}2\pi )$, we obtain:

$${\overline{p}}_i^{(2n)}(x)=\{\begin{array}{ll}\sum _k\left\{(\mid u_{x,L}^{(k)}{\mid }^2+\mid u_{x,R}^{(k)}{\mid }^2)\times \mid u_{1,R}^{(k)}{\mid }^2\right\},\hfill & \text{if\hspace{0.17em}}i=1\hfill \\ \frac{1}{2}\sum _k\left\{(\mid u_{x,L}^{(k)}{\mid }^2+\mid u_{x,R}^{(k)}{\mid }^2)\times (\mid u_{i,L}^{(k)}{\mid }^2+\mid u_{i,R}^{(k)}{\mid }^2)\right\},\hfill & \text{if\hspace{0.17em}}2\le i\le 2n-1\hfill \\ \sum _k\left\{(\mid u_{x,L}^{(k)}{\mid }^2+\mid u_{x,R}^{(k)}{\mid }^2)\times \mid u_{2n,L}^{(k)}{\mid }^2\right\},\hfill & \text{if\hspace{0.17em}}i=2n\hfill \end{array}$$

with ${\mathbf{u}}_k={\sum }_{j=1}^{2n}\mid j\rangle \otimes \left(u_{x,L}^{(k)}\mid L\rangle +u_{x,R}^{(k)}\mid R\rangle \right)$, because all eigenvalues of U⁽²ⁿ⁾ are nondegenerate (this comes from nondegenerateness of J_2n(p); see, e.g., [22]). Using this fact and Lemmas 4.2 and 4.3, we have the symmetric property of the time averaged distribution. Moreover, we also obtain:

$$\mid u_{i,L}^{(1)}{\mid }^2+\mid u_{i,R}^{(1)}{\mid }^2=\mid u_{i,L}^{(2n)}{\mid }^2+\mid u_{i,R}^{(2n)}{\mid }^2=\mid {\tilde{\mathbf{v}}}_{\pm 1}(i){\mid }^2=\frac{(p-q)\hspace{0.17em}[{\delta }_1(i)+\{1-{\delta }_1(i)\}/q]\hspace{0.17em}{(q/p)}^{i-1}}{2\{2p-{(q/p)}^{n-1}\}}$$

for i = 1, . . . n. On the other hand, it is obvious that:

$${\overline{p}}_i^{(2n)}(x)\ge \{\begin{array}{ll}\sum _{k=1,2n}\left\{(\mid u_{x,L}^{(k)}{\mid }^2+\mid u_{x,R}^{(k)}{\mid }^2)\times \mid u_{1,R}^{(k)}{\mid }^2\right\},\hfill & \text{if\hspace{0.17em}}i=1\hfill \\ \frac{1}{2}\sum _{k=1,2n}\left\{\mid u_{x,L}^{(k)}{\mid }^2+\mid u_{x,R}^{(k)}{\mid }^2\times (\mid u_{i,L}^{(k)}{\mid }^2+\mid u_{i,R}^{(k)}{\mid }^2)\right\},\hfill & \text{if\hspace{0.17em}}2\le i\le n\hfill \end{array}$$

As a consequence, we have the desired lower bound.

$${\overline{p}}_i^{(2n)}(x)\ge \frac{{(p-q)}^2{(q/p)}^{i-1}}{2\hspace{0.17em}[{\delta }_1(i)+\{1-{\delta }_1(i)\}\hspace{0.17em}2q]\hspace{0.17em}{\{2p-{(q/p)}^{n-1}\}}^2}\left[{\delta }_1(x)+\{1-{\delta }_1(x)\}\frac{{(q/p)}^{x-1}}{q}\right]$$

Taking suitable limits, the remaining parts of Theorem 3.1 are obtained by this lower bound.

The eigenvectors, u_±k, with k = 2, . . . , 2n − 1 are not obtained explicitly in the present stage. It is expected that the remaining part of the time averaged distribution converges to the uniform distribution after suitable normalization, because the remaining eigenvectors are similar to that of the time evolution operator of DTQW on the path graphs [18]. It is interesting future work to make clear whether this conjecture is true or not.