Continuous-Time Quantum Walks — Examples

For the two-vertex graph with one edge, in basis $(e_0,e_1)$ the adjacency swaps the basis vectors, $A{e}_0=e_1$ and $A{e}_1=e_0$, and $D=I$. Thus $L_{+}=I-A$, $L_{-}=-L_{+}$, and $A_{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}}=A$. Put $u_{+}=(e_0+e_1)\mathrm{/}\sqrt{2}$, $u_{-}=(e_0-e_1)\mathrm{/}\sqrt{2}$, and $\psi =(e_0+i{e}_1)\mathrm{/}\sqrt{2}$. Direct inner-product calculations using [F9] give $\mathrm{\parallel }{u}_{+}\mathrm{\parallel }=\mathrm{\parallel }{u}_{-}\mathrm{\parallel }=\mathrm{\parallel }\psi \mathrm{\parallel }=1$ and $⟨u_{+},u_{-}⟩=0$; direct application of $A$ gives $A{u}_{+}=u_{+}$ and $A{u}_{-}=-u_{-}$. Thus $(u_{+},u_{-})$ is an orthonormal eigenbasis.

For the three-vertex path with ordered vertices $0,1,2$, the degrees are $(1,2,1)$ and $A{e}_0=e_1$, $A{e}_1=e_0+e_2$, $A{e}_2=e_1$. Thus $A=\left(\begin{array}{ccc}0& 1& 0\\ 1& 0& 1\\ 0& 1& 0\end{array}\right),D=\left(\begin{array}{ccc}1& 0& 0\\ 0& 2& 0\\ 0& 0& 1\end{array}\right),A_{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}}=D^{-1\mathrm{/}2}A{D}^{-1\mathrm{/}2}=A\mathrm{/}\sqrt{2},L_{+}=D-A,L_{-}=A-D=-L_{+}\mathrm{.}$ All degrees are positive, so [F1] defines $A_{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}}$. Put $u_0=(e_0-e_2)\mathrm{/}\sqrt{2}$, $u_{+}=(e_0+\sqrt{2}{e}_1+e_2)\mathrm{/}2$, and $u_{-}=(e_0-\sqrt{2}{e}_1+e_2)\mathrm{/}2$. By direct coordinate inner products in the standard orthonormal basis [F9], $(u_0,u_{+},u_{-})$ is an orthonormal basis; direct multiplication gives $A{u}_0=0$, $A{u}_{+}=\sqrt{2}{u}_{+}$, and $A{u}_{-}=-\sqrt{2}{u}_{-}$. The vectors $c=(e_0+e_1+e_2)\mathrm{/}\sqrt{3}$, $u_0$, and $v=(e_0-2e_1+e_2)\mathrm{/}\sqrt{6}$ also have unit norm and pairwise zero inner products. Direct multiplication gives $L_{+}c=0$, $L_{+}{u}_0=u_0$, and $L_{+}v=3v$. Hence the four generator spectra are $\sigma (A)=\{0,\pm \sqrt{2}\}$, $\sigma (A_{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}})=\{0,\pm 1\}$, $\sigma (L_{+})=\{0,1,3\}$, and $\sigma (L_{-})=\{0,-1,-3\}$. This directly compares adjacency, normalized adjacency, and both Laplacian signs on the irregular graph.

The spectral definition [F2] gives eigenphases $1,e^{-2i}$ for $U_{L_{+}}(1)$ on $(u_{+},u_{-})$ and $1,e^{2i}$ for $U_{L_{-}}(1)$. By [F3]–[F4], these are equivalently $e^{-i}(\cos 1I+i\sin 1A)$ and $e^i(\cos 1I-i\sin 1A)$: on $u_{+}$ and $u_{-}$, respectively, the coefficients are $1,e^{-2i}$ and $1,e^{2i}$. The $e_1$ coordinate after $U_{L_{+}}(1)$ is $e^{-i}i(\cos 1+\sin 1)\mathrm{/}\sqrt{2}$; after $U_{L_{-}}(1)$ it is $e^{i}i(\cos 1-\sin 1)\mathrm{/}\sqrt{2}$. Thus [F10] gives $p_{+}(1)=(\cos 1+\sin 1{)}^2\mathrm{/}2$ and $p_{-}(1)=(\cos 1-\sin 1{)}^2\mathrm{/}2$.

Put $\xi =(u_0+u_{+})\mathrm{/}\sqrt{2}$, which is unit by step 1.2, and fix the target ray $[\zeta ]:=[U_A(\pi \mathrm{/}\sqrt{2})\xi ]=[(u_0-u_{+})\mathrm{/}\sqrt{2}]$, since $e^{-i\pi }=-1$ by [F4], [F7]. For any real $t$, $U_A(t)\xi =(u_0+e^{-i\sqrt{2}t}{u}_{+})\mathrm{/}\sqrt{2}$ and $U_{A_{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}}}(t)\xi =(u_0+e^{-it}{u}_{+})\mathrm{/}\sqrt{2}$ by [F1]–[F2]. Since the $u_0$ coefficient is the same nonzero number in both target and output, equality of rays forces the scalar multiple to be $1$ and is equivalent to equality of the displayed relative phases.

At $1$, the cosine-series magnitudes $b_k=1\mathrm{/}(2k)!$ and sine-series magnitudes $c_k=1\mathrm{/}(2k+1)!$ decrease to zero: each next factorial multiplies the denominator by a factor at least $2$, so both sequences tend to zero. By [F5]–[F6], the cosine sum lies above its two-term partial sum $1-1\mathrm{/}2=1\mathrm{/}2$, and the sine sum lies above $1-1\mathrm{/}6=5\mathrm{/}6$. Therefore $p_{+}(1)-p_{-}(1)=2\sin 1\cos 1\ge 5\mathrm{/}6>0$. The two Laplacian signs give different same-time measurement laws.

If $[U_A(t)\xi ]=[\zeta ]$, then $e^{-i(\sqrt{2}t-\pi )}=1$. By [F3]–[F4], this forces $\sin (\sqrt{2}t-\pi )=0$ and $\cos (\sqrt{2}t-\pi )=1$; [F8] puts the angle at $k\pi$, and [F7] shows $k$ must be even. Thus $t=\pi \mathrm{/}\sqrt{2}+k\sqrt{2}\pi$. For $k\ge 0$ this is at least $\pi \mathrm{/}\sqrt{2}$; for $k\le -1$ it is at most $\pi \mathrm{/}\sqrt{2}-\sqrt{2}\pi <0$. Hence its least nonnegative value is $\pi \mathrm{/}\sqrt{2}$. The same argument for $A_{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}}$ gives $t=\pi +2k\pi$, whose least nonnegative value is $\pi$. For the second family, $k=0$ gives $t=\pi$, every $k\ge 1$ gives a larger time, and every $k\le -1$ gives a negative time. Thus the least nonnegative time is $\pi$. These runtimes differ because $\sqrt{2}>1$.

Put $f_{+}=(e_0+e_1)\mathrm{/}\sqrt{2}$ and $f_{-}=(e_0-e_1)\mathrm{/}\sqrt{2}$. By [F2]–[F4] they form an orthonormal basis, and direct multiplication gives $X{f}_{+}=f_{+}$ and $X{f}_{-}=-f_{-}$. By [F5], $U_X(t)$ acts on these vectors by $e^{-it}$ and $e^{it}$. On $f_{+}$, $\cos tI-i\sin tX$ acts by $\cos t-i\sin t=e^{-it}$; on $f_{-}$ it acts by $\cos t+i\sin t=e^{it}$, using [F6]–[F7]. Thus the two maps agree on a basis. At $t=\pi \mathrm{/}2$, [F8] yields $U_X(\pi \mathrm{/}2)=-iX$, so $U_X(\pi \mathrm{/}2)e_0=-i{e}_1$.

The displayed matrix for $A_2$ follows by applying $X\otimes I+I\otimes X$ to each of the four basis vectors in [F2] using the tensor-map action [F11]. The four vectors $f_{+}\otimes f_{+}$, $f_{+}\otimes f_{-}$, $f_{-}\otimes f_{+}$, and $f_{-}\otimes f_{-}$ form a basis by [F2]–[F3]. On $f_{ϵ}\otimes f_{\eta }$ with $ϵ,\eta \in \{1,-1\}$, $A_2$ has eigenvalue $ϵ+\eta$; [F5]–[F6] give evolution coefficient $e^{-i\pi (ϵ+\eta )\mathrm{/}2}=e^{-i\pi ϵ\mathrm{/}2}{e}^{-i\pi \eta \mathrm{/}2}$, which is exactly the coefficient of $U_X(\pi \mathrm{/}2)\otimes U_X(\pi \mathrm{/}2)$ by [F11]. The operators therefore agree on a basis, and step 1.1 gives $U_{A_2}(\pi \mathrm{/}2)=-X\otimes X$. Hence $U_{A_2}(\pi \mathrm{/}2)e_{00}=-e_{11}$.

In the $n=1$ case, step 1.1 gives outcome $1$ amplitude $-i$; in the $n=2$ case, step 2.1 gives outcome $11$ amplitude $-1$. Both have squared modulus $1$, so [F9] gives the opposite-corner outcome with probability one in each case. These calculations are the $n=1,2$ instances of [F10].

The $N-1$ unmarked encoded basis vectors are pairwise orthonormal by [F4], so $\mathrm{\mid }r⟩=(N-1{)}^{-1\mathrm{/}2}{\sum }_{x\mathrm{\ne }w}\mathrm{\mid }x⟩$ is unit and orthogonal to the unit vector $\mathrm{\mid }w⟩$. The uniform vector is $\mathrm{\mid }s⟩=N^{-1\mathrm{/}2}\mathrm{\mid }w⟩+\sqrt{(N-1)\mathrm{/}N}\mathrm{\mid }r⟩$, whose squared coefficient norms sum to $1$.

By [F1], $A\mathrm{\mid }w⟩={\sum }_{x\mathrm{\ne }w}\mathrm{\mid }x⟩=\sqrt{N-1}\mathrm{\mid }r⟩$. For $\mathrm{\mid }r⟩$, each summand $A\mathrm{\mid }x⟩$ contains $\mathrm{\mid }w⟩$ once, so its $\mathrm{\mid }w⟩$ coefficient is $\sqrt{N-1}$; for each unmarked $y$, the sum contains $\mathrm{\mid }y⟩$ once for each $x\mathrm{\ne }y,w$, hence $N-2$ times. Thus $A\mathrm{\mid }r⟩=\sqrt{N-1}\mathrm{\mid }w⟩+(N-2)\mathrm{\mid }r⟩$.

The two vectors span an invariant subspace for $A$ by step 2.1. By [F3], $P_w\mathrm{\mid }w⟩=\mathrm{\mid }w⟩$ and $P_w\mathrm{\mid }r⟩=0$, so $P_w$ also preserves this span. The symmetric adjacency is Hermitian by [F2], and the generator matrix is $H=\left(\begin{array}{cc}-1& -\sqrt{N-1}\mathrm{/}N\\ -\sqrt{N-1}\mathrm{/}N& -(N-2)\mathrm{/}N\end{array}\right)\mathrm{.}$

Put $K=H+(N-1)I\mathrm{/}N$. Direct multiplication gives $K^2=I\mathrm{/}N$, and $\mathrm{tr}K=0$. Equivalently, its characteristic polynomial is ${\lambda }^2-1\mathrm{/}N$, so its eigenvalues are $\pm 1\mathrm{/}\sqrt{N}$. Therefore the eigenvalues of $H$ are $-(N-1)\mathrm{/}N\pm 1\mathrm{/}\sqrt{N}$, and their gap is $2\mathrm{/}\sqrt{N}$.

At $N=2$, $\mathrm{\mid }r⟩$ is the single unmarked basis vector and the formula in step 3.1 becomes $H=\left(\begin{array}{cc}-1& -1\mathrm{/}2\\ -1\mathrm{/}2& 0\end{array}\right)$. The shifted matrix has eigenvalues $\pm 1\mathrm{/}\sqrt{2}$, so the gap is $\sqrt{2}$; all normalizations and denominators used above remain valid.

For the uniform input $\mathrm{\mid }s⟩$ in step 1.1, [F5] gives marked-label probability $1$ after exact evolution at $t=\pi \sqrt{N}\mathrm{/}2$. The invariant matrix and its gap were derived locally in steps 3.1–4.1.

Specialize to the standard binary encoding for $N=2$ and $N=4$. For $N=2$, the preparation is $H\mathrm{\mid }0⟩=(\mathrm{\mid }0⟩+\mathrm{\mid }1⟩)\mathrm{/}\sqrt{2}$, which is the required uniform state with one Hadamard gate. For $N=4$, applying the second factor gives $H^{\otimes 2}\mathrm{\mid }00⟩=(\mathrm{\mid }00⟩+\mathrm{\mid }01⟩+\mathrm{\mid }10⟩+\mathrm{\mid }11⟩)\mathrm{/}2$, the required uniform state with two Hadamard gates. These are the $n=1,2$ cases of [F6]; no preparation or gate cost is inferred from the search matrix.