Discrete Quantum Walks and Szegedy Theory — Examples

Each row of $P$ is a probability vector, and $\pi P=(1,0)=\pi$, so $\pi$ is stationary.

The second coordinate has ${\pi }_1=0$, so the diagonal matrix $\mathrm{diag}(1\mathrm{/}\sqrt{{\pi }_0},1\mathrm{/}\sqrt{{\pi }_1})$ is undefined over $\mathbb{R}$; hence the proposed full-state similarity matrix is not defined.

The proposed assertion identifies the full-state expression with the discriminant $D$ of [F3] and requires the displayed matrix to be defined for every stationary probability vector. Step 1.2 shows it is undefined for this valid stationary vector, so the universal assertion is false. A restriction to the positive support is a different statement.

Every row of $P$ has one entry equal to $1$, and each column also has one such entry, so $P$ is row-stochastic and $\pi P=\pi$.

Detailed balance fails at $(x,y)=(0,1)$ because ${\pi }_0{P}_{01}=1\mathrm{/}3$ but ${\pi }_1{P}_{10}=0$. Thus the chain is stationary but not reversible.

No pair of distinct states has transitions in both directions, and all diagonal entries are zero, so $P_{xy}{P}_{yx}=0$ for every $x,y$ and [F4] gives $D=0$. Since the stationary vector is uniform, its diagonal similarity transform is $\mathrm{diag}(\sqrt{\pi })P\mathrm{diag}(1\mathrm{/}\sqrt{\pi })=P\mathrm{\ne }0$. The claimed identity fails.

Both rows of $P$ sum to one, $\pi P=\pi$, and ${\pi }_0{P}_{01}={\pi }_1{P}_{10}=1\mathrm{/}2$; the diagonal detailed-balance equations are automatic. Hence $(X,P,\pi )$ is a finite reversible chain.

Starting from either state, a return occurs exactly at positive even times, so the return-time set is $\{2,4,6,\dots \}$ and its gcd is $2$. The chain is period two.

The constant vector $\mathbf{1}=(1,1)$ has eigenvalue $1$, while $h=(1,-1)$ spans $H_0$ and satisfies $Ph=-h$. Thus the restriction to $H_0$ has norm $1$, so [F3] gives ${\delta }_{\mathrm{a}\mathrm{b}\mathrm{s}}(P)=0$. The eigenvalues of $P$ are exactly $1$ and $-1$.

Both rows of $P_a$ sum to one, $\pi P_a=\pi$, and $P_a$ is symmetric, so ${\pi }_x(P_a{)}_{xy}={\pi }_y(P_a{)}_{yx}$ for all $x,y$. Thus $\pi$ is a positive stationary reversible law.

Since $P_a$ is symmetric and has nonnegative entries, [F2] gives $D=P_a$. The vectors $u_{+}=(1,1)$ and $u_{-}=(1,-1)$ form a basis with $D{u}_{+}=u_{+}$ and $D{u}_{-}=(1-2a)u_{-}$.

At $a=0$, $T\mathrm{\mid }0⟩=\mathrm{\mid }00⟩$ and $T\mathrm{\mid }1⟩=\mathrm{\mid }11⟩$, so $A=B=\mathrm{span}\{\mathrm{\mid }00⟩,\mathrm{\mid }11⟩\}$. On $A$, $R_A=2T{T}^{\ast }-I$ is $+I$ and $S=I$, so $U=+I$. On $K=\mathrm{span}\{\mathrm{\mid }01⟩,\mathrm{\mid }10⟩\}$, [F6] gives $U=-S$, whose eigenvectors $\mathrm{\mid }01⟩+\mathrm{\mid }10⟩$ and $\mathrm{\mid }01⟩-\mathrm{\mid }10⟩$ have eigenvalues $-1$ and $+1$. Hence ${\sigma }_{\mathrm{m}\mathrm{u}\mathrm{l}\mathrm{t}}(U)=\{1,1,1,-1\}$ and $W=I$ has four eigenvalues $+1$.

At $a=1$, $T\mathrm{\mid }0⟩=\mathrm{\mid }01⟩$ and $T\mathrm{\mid }1⟩=\mathrm{\mid }10⟩$, so $A=B=\mathrm{span}\{\mathrm{\mid }01⟩,\mathrm{\mid }10⟩\}$. On $A$, $R_A=+I$ and $U=S$, with eigenvalues $+1,-1$. On $K=\mathrm{span}\{\mathrm{\mid }00⟩,\mathrm{\mid }11⟩\}$, $S=I$, so [F6] gives $U=-I$. Thus ${\sigma }_{\mathrm{m}\mathrm{u}\mathrm{l}\mathrm{t}}(U)=\{1,-1,-1,-1\}$ and $W=I$ has four eigenvalues $+1$.

Suppose $0<a<1$ and set $\lambda =1-2a\in (-1,1)$ and $\theta =\arccos \lambda \in (0,\pi )$. By [F7], the $u_{+}$ endpoint line contributes $+1$ to $U$ and $W$, and the $u_{-}$ invariant plane contributes $e^{i\theta },e^{-i\theta }$ to $U$ and $e^{2i\theta },e^{-2i\theta }$ to $W$.

Under the hypothesis of step 2.1, put $r=\sqrt{1-a}$ and $s=\sqrt{a}$. Let $A=\mathrm{im}T$ and $B=\mathrm{im}(ST)$; these are subspaces by [F9]–[F10]. By [F3], their spanning vectors are $T\mathrm{\mid }0⟩=r\mathrm{\mid }00⟩+s\mathrm{\mid }01⟩$, $T\mathrm{\mid }1⟩=s\mathrm{\mid }10⟩+r\mathrm{\mid }11⟩$, $ST\mathrm{\mid }0⟩=r\mathrm{\mid }00⟩+s\mathrm{\mid }10⟩$, and $ST\mathrm{\mid }1⟩=s\mathrm{\mid }01⟩+r\mathrm{\mid }11⟩$. The vector $k=(s\mathrm{\mid }00⟩-r\mathrm{\mid }01⟩-r\mathrm{\mid }10⟩+s\mathrm{\mid }11⟩)\mathrm{/}\sqrt{2}$ has norm one because $r^2+s^2=1$ and is orthogonal to each spanning vector by cancellation of the two $rs$ terms. Hence [F11] gives $0\mathrm{\ne }k\in K:=(A+B{)}^{\perp }$; since the product register has dimension four, [F12] implies $\dim (A+B)\le 3$. By [F5], $ST{u}_{+}=T{u}_{+}$ gives a common nonzero vector in $A\cap B$, while $T{u}_{-}$ and $ST{u}_{-}$ are linearly independent because $-1<\lambda <1$. These two vectors are orthogonal to the common vector: $⟨T{u}_{+},T{u}_{-}⟩=⟨ST{u}_{+},ST{u}_{-}⟩=0$ by isometry of $T$ and unitarity of $S$, and $⟨T{u}_{+},ST{u}_{-}⟩=⟨u_{+},D{u}_{-}⟩=0$ by the distinct eigenvalues in step 1.2; the reverse cross-pairing vanishes by conjugate symmetry. Thus $\dim (A+B)\ge 3$, so it is exactly $3$ and $K$ is one-dimensional, hence $K=\mathrm{span}\{k\}$. The coefficients of $\mathrm{\mid }01⟩$ and $\mathrm{\mid }10⟩$ in $k$ are equal, so [F3] gives $Sk=k$. By [F6], $U=-S=-I$ on $K$. Combining this complement eigenvalue with the line and plane eigenvalues from step 2.1 yields ${\sigma }_{\mathrm{m}\mathrm{u}\mathrm{l}\mathrm{t}}(U)=\{1,-1,e^{i\theta },e^{-i\theta }\}$ and ${\sigma }_{\mathrm{m}\mathrm{u}\mathrm{l}\mathrm{t}}(W)=\{1,1,e^{2i\theta },e^{-2i\theta }\}$.