A Mathematical Framework for Maze Solving Using Quantum Walks

Let $G_{o}=(V_{o},A_{o})$ be a finite connected and symmetric digraph such that an arc $a\in A_{o}$ if and only if its inverse arc $\bar{a}\in A_{o}$. The origin and terminal vertices of $a\in A_{o}$ are denoted by $o(a)\in V_{o}$ and $t(a)\in V_{o}$, respectively. We assume that $G_{o}$ has no multiple arcs and self-loops. This symmetric digraph $G_{o}$ is called the underlying graph.

In this paper, we consider the problem of solving a maze by using a quantum walk. The maze is regarded as the underlying graph $G_{o}$. To let the quantum walk solve the maze, we slightly deform the underlying graph as follows. The start and goal of the maze can be placed at any vertex in $V_{o}$, and they are indexed by $s$ and $g$, respectively. To find a route from $s$ to $g$, we add one self-loop each to vertices $s$ and $g$, which are also indexed by $s$ and $g$. We also add a vertex which is called sink and indexed by $d$. The sink is connected only to the start vertex $s$. The arc which connects $s$ and $d$ is also indexed by $d$, where $o(d)=s$ and $t(d)=d$. In the following, the graph induced by the underlying graph $G_{o}$ is denoted by $G=(V,A)$; the digraph $G$ contains these self-loops, the sink vertex and arcs connecting to the start and the sink vertices. (See Figure 1). The degree of $v\in V$ is given by

$${\rm deg}(v)=|\{a\in A\,|\,t(a)=v\}|.$$

By the symmetry of the digraph, the equation ${\rm deg}(v)=|\{a\in A\,|\,o(a)=v\}|$ holds.

The Hilbert space w.r.t. arcs is defined by

$${\mathcal{H}}_{A}=\left\{\xi\colon A\to{\mathbb{C}}\right\}.$$

We use the Grover walk $U$ on ${\mathcal{H}}_{A}$ defined by

$$(U\xi)(a)=-\xi(\bar{a})+\frac{2}{{\rm deg}(o(a))}\sum_{t(b)=o(a)}\xi(b)$$

for any $\xi\in{\mathcal{H}}_{A}$. The initial state is

$$\zeta(a)=\begin{cases}1&(a=s)\\ 0&(a\neq s)\end{cases}.$$

We want to assume that the quantum walker at the sink goes away and never comes back. To represent this, we use the projection $P$ given by

$$(P\xi)(a)=\begin{cases}\xi(a)&a\neq d,\bar{d}\\ 0&a=d,\bar{d}\end{cases}.$$

(2.1)

For $n=0,1,2,\ldots$, the $n$-th iteration of the Grover walk with the sink is defined by

$$\zeta_{n}(a)=\left((PU)^{n}\zeta\right)(a)\quad(a\in A).$$

Then, the finding probability at vertex $v\in V\backslash\{d\}$ and at time $n$ can be defined by

$$\mu_{n}(v)=\sum_{t(a)=v}|\zeta_{n}(a)|^{2}.$$

Remark that our assumption is also represented by using an infinite dimensional environmental Hilbert space ${\mathcal{H}}_{E}$ and an appropriately extended unitary $\tilde{U}$ on ${\mathcal{H}}_{A}\oplus{\mathcal{H}}_{E}$ [25]. However, since

$$(\tilde{U}^{n}\tilde{\zeta})(a)=\left((PU)^{n}\zeta\right)(a)$$

for any $a\in A\backslash\{d,\bar{d}\}$, we will adopt the RHS represented by the finite system in this paper. Here $\tilde{\zeta}$ is the extension of the initial state $\zeta\in\mathcal{H}_{A}$ to $\mathcal{H}_{A}\oplus\mathcal{H}_{E}$.

To solve the maze, it is important to know the eigenvalues and eigenvectors of the Grover walk $U$. In particular, we focus on the eigenvectors of $U$ which are invariant under the action of the projection $P$; as we will see, the contribution of the eigenvectors which are not invariant under the action of $P$ reduces exponentially to $0$ as the time step goes to infinity.

We give the following simple lemma which will be useful for the considerations of its remaining statements. Remark that the eigenvalue $\lambda$ of $U$ satisfies $|\lambda|=1$.

Since our interest is the time iteration of the truncated Grover walk with respect to $A\setminus\{d,\bar{d}\}$, that is, $PU$, and the support of the initial state is the self-loop $s\in A$ of the start vertex, we will decompose the Grover walk $U$ through the consideration of the overlap between an eigenvector and $\{d,\bar{d},s\}$. The final form of the spectral decomposition can be seen in (2.2). Then, we consider the eigenvectors of $U$. For an eigenvector $\xi$ of $U$, there are the following four cases:

(1) $\xi(s)\neq 0,\xi(d)=0,$   (2) $\xi(s)\neq 0,\xi(d)\neq 0$,

(3) $\xi(s)=0,\xi(d)\neq 0$,   (4) $\xi(s)=0,\xi(d)=0$.
Note that by Lemma 2.1, $\xi(d)=0$ implies $\xi(\bar{d})=0$, and $\xi(d)\neq 0$ implies $\xi(\bar{d})\neq 0$. When a vector $\xi$ satisfies the case $(i)$ $(i\in\{1,2,3,4\})$, we say “$\xi$ is in $(i)$”, for simplicity.

The eigenspace associated with the eigenvalue $\lambda$ is denoted by $V(\lambda)$. Note that the eigenvectors in (1) or (4) have the contribution to give the iteration of the truncated Grover walk $PU$, because $d,\bar{d}\notin\mathrm{supp}(\xi)$ for any $\xi$ in (1) or (4). First, we consider the eigenspace $V(-1)$ because of the following strong statement.

The statement of Lemma 2.2 is strong but not ensures the existence of such an eigenvector. However, the following lemma not only ensures such an eigenvector in Lemma 2.2 but also gives an explicit expression by using a path between the self-loops $s$ and $g$. Figure 2 illustrates this eigenvector.

Lemmas 2.2 and 2.3 imply that every eigenvector in (1) is included in $V(-1)$. Then, we are interested in whether $V(-1)$ includes eigenvectors in (2), (3) or (4). Let us see that the following lemma removes the possibilities that $\xi\in V(-1)$ is in (2) or (3).

Now we are ready to construct an ONB for $V(-1)$ as follows.

The reason for choosing such an ONB of $V(-1)$ is as follows. To describe the Fourier expansion of the initial state $\zeta$, we use the inner products of each vector in an ONB and $\zeta$. Note that the first $\mathrm{dim}V(-1)-1$ bases of $V(-1)$ in Proposition 2.5, $\psi_{j}^{(-1)}$ ($1\leq j\leq\mathrm{dim}V(-1)-1$), have no overlap to the initial state $\zeta$, that is, $\langle\psi_{j}^{(-1)},\zeta\rangle=0$ for any $j=1,\dots,\mathrm{dim}V(-1)-1$. The only base which has the overlap with $\zeta$ is the last base $\varphi$. Thus the overlap of the initial state with the subspace $V(-1)\subset\mathcal{H}_{A}$ is obtained by just one inner product of $\varphi$ and $\zeta$ by this expression of ONB. As we will see, the contribution of $V(\lambda)$ with $\lambda\neq-1$ to the survival probability $\|(PU)^{n}\zeta\|^{2}$ exponentially reduces. Thus the vector $\varphi$ is the key to navigates the quantum walker to the stationary state.

Next, we are interested in the contribution of the eigenspace of $U$ having the overlap with the initial state for the eigenvalue $\lambda\neq-1$ to the survival probability. To this end, we construct an ONB of $V(\lambda)$ with $\lambda\neq-1$ step by step; the final form of the decomposition of $U$ for the survival probability is described in (2.2). First, we show that every eigenvector with the eigenvalue $\lambda\neq-1$ is not in (2), or is not in (3) as follows.

Using Lemma 2.6, we can construct the following ONB for $\lambda\neq-1$ concerning to the overlap with $d$ and $\bar{d}$.

If there is a vector in (2) or (3), we can use the same method in the proof of Proposition 2.5. Assume that there is a vector in (2). Let $k={\rm dim}V(\lambda)$, and let $\{\xi_{1},\ldots,\xi_{k}\}$ be a basis of $V(\lambda)$ with $\xi_{k}(s)\neq 0$ and $\xi_{k}(d)\neq 0$. Define a vector $\eta_{i}$ by

$$\eta_{i}=\begin{cases}\displaystyle\xi_{i}-\frac{\xi_{i}(d)}{\xi_{k}(d)}\xi_{k}&(1\leq i\leq k-1)\\ \xi_{k}&(i=k)\end{cases}.$$

Remark that $\eta_{i}$ is in (4) for $1\leq i\leq k-1$, because $\eta_{i}(d)=0$ and there is no vector in (1). We apply the Gram-Schmidt process to $\{\eta_{i}\}_{i=1}^{k}$, and denote the constructed vectors by $\{\psi_{1}^{(\lambda)},\ldots,\psi_{k}^{(\lambda)}\}$. This is the desired ONB.

When there is a vector in (3), we can construct the desired ONB, similarly. $\square$

We denote $k^{(\lambda)}$ by the number of vectors in (4) in the above ONB, and put $k^{(-1)}={\rm dim}V(-1)-1$. When the above ONB contains a vector in (2) or (3), we denote the vector by $\eta^{(\lambda)}$. This means $\psi_{k^{(\lambda)}+1}=\eta^{(\lambda)}$.

Here, we consider the spectrum decomposition of $U$, that is,

$$U=-|\varphi\rangle\langle\varphi|+\sum_{\lambda\in\sigma(U)}\lambda\left(|\eta^{(\lambda)}\rangle\langle\eta^{(\lambda)}|+\sum_{i=1}^{k^{(\lambda)}}|\psi^{(\lambda)}_{i}\rangle\langle\psi_{i}^{(\lambda)}|\right),$$

(2.2)

where $\sigma(U)$ is the set of all eigenvalues of $U$, and $\eta^{(\lambda)}=0$ when $V(\lambda)$ does not contain a vector in (2) or (3). Define ${\mathcal{K}}={\rm span}\{\eta^{(\lambda)}\,|\,\lambda\in\sigma(U)\}$. We see that this subspace is invariant under $P$ defined in (2.1).

This Lemma implies that the contribution of the subspace $\mathcal{K}\subset\mathcal{H}_{A}$ to the survival probability reduces exponentially to zero as time goes to infinity as follows.

Assume that $\lambda$ is an eigenvalue of $PU|_{{\mathcal{K}}}$ with $|\lambda|=1$, and $\eta$ is a unit eigenvector associated with the eigenvalue $\lambda$. The equation

$$\|PU\eta\|=\|\lambda\eta\|=\|\eta\|=\|U\eta\|$$

implies $(U\eta)(d)=(U\eta)(\bar{d})=0$, and therefore, $PU\eta=U\eta$. Hence, we have

$$U\eta=PU\eta=\lambda\eta,$$

which means that $\eta$ is an eigenvector of $U$. Moreover, $\eta(d)=0$.

Since $\eta$ has the eigenvalue $\lambda$, $\eta$ is in $V(\lambda)$. On the other hand, $\eta$ is in ${\mathcal{K}}$. Hence, $\eta$ is equal to $e^{{\rm i}t}\eta^{(\lambda)}$ for some $t\in{\mathbb{R}}$. However, this contradicts $\eta(d)=0$. $\square$

The initial state $\zeta$ is written as

$$\zeta=\langle\varphi,\zeta\rangle\varphi+\sum_{\lambda\in\sigma(U)}\langle\eta^{(\lambda)},\zeta\rangle\eta^{(\lambda)}=\overline{\varphi(s)}\varphi+\sum_{\lambda\in\sigma(U)}\overline{\eta^{(\lambda)}(s)}\eta^{(\lambda)}.$$

So,

$$\lim_{n\to\infty}(-1)^{n}(PU)^{n}\zeta=\overline{\varphi(s)}\varphi.$$

We will call this vector $\varphi$ the navigation vector. Recall that the navigation vector is the unique base of $V(-1)$ which has an overlap to $s$, see Proposition 2.5. We use this navigation vector to solve the maze because the survival probability can be simply described by only the overlap of the initial state and the navigation vector:

Therefore, finding the ONB in Proposition 2.5 so that the navigation vector appears is the key to obtain the survival probability. We demonstrate the construction of the ONB and the navigation vector for a tree case and a ladder case in the next section.

When the graph is a tree, we can determine the navigation vector.

When the underlying graph is a tree, the shortest route from the start to the goal is uniquely determined which is denoted by $\{a_{i}\}_{i=1}^{n}$. We set $a_{0}=s$ and $a_{n+1}=g$. Let $\varphi$ be navigation vector, and let $r=|\varphi(s)|$. Then, the navigation vector satisfies

$$|\varphi(a)|=\begin{cases}r&a=a_{i}\ {\rm or}\ \bar{a}=a_{i}\\ 0&{\rm otherwise}\end{cases}.$$

This means that the amplitudes of the navigation vector are only on the shortest route. Therefore, the position of the quantum walker tells us the shortest route.

Note that a tree has the unique simple path between the start and goal vertices, and this becomes the shortest path. Here, a simple path is a walk in which all vertices and also all edges are distinct. We have seen in Section 3.1 that the shortest path of arbitrary tree is only the place where a quantum walker “clings” in the long time limit. On the other hand, once there is a cycle, there are several choices of the non-backtracking path. As a natural question, we are interested in the tendency of a quantum walker in this case. In this section, we consider a ladder graph as an example of the graph which has cycles so that there are $k+1$ kinds of “detours” among the shortest path. See Figure 4. Before describing the setting, we prove the next lemma.

Now, we consider a ladder graph. As in Figure 4, the ladder graph contains $k+1$ cycles which are indexed by $\gamma_{i}$. Each cycle $\gamma_{i}$ is a rectangle of length $m$ and width $l$. The lower left vertex of the cycle $\gamma_{0}$ and the start vertex are adjacent.

The normalized eigenvector with respect to the cycle $\gamma_{n}$ constructed in Lemma 3.2 is also denoted by $\gamma_{n}$ $(0\leq n\leq k)$, and the normalized eigenvector with respect to the shortest route defined in Lemma 2.3 is denoted by $\xi$. Without loss of generality, we can assume $\langle\gamma_{n},\gamma_{n+1}\rangle\geq 0$ and $\langle\gamma_{0},\xi\rangle\geq 0$. It is known that the eigenvector of $U$ associated with the eigenvalue $-1$ is described as a linear combination of $\gamma_{n}$ and $\xi$ [25]. Indeed, it holds that $\mathrm{span}\{\gamma_{0}\dots,\gamma_{k}\}=\mathrm{span}\{\psi_{1}^{(-1)},\dots,\psi_{k^{(-1)}}^{(-1)}\}$, where $\psi_{i}^{(-1)}$’s are the eigenvectors of the eigenvalue $-1$ in (2.2) whose supports have no intersection to $\{d,\bar{d}\}$. To obtain the navigation vector $\varphi$ in (2.2), from now on, we construct the ONB of $V(-1)$ in Proposition 2.5 by applying the Gram-Schmidt process to $\{\gamma_{0},\dots,\gamma_{k},\xi\}$ step by step.

Let $\kappa=\frac{m}{2(l+m)}$. We apply the Gram-Schmidt process to $\{\gamma_{0},\ldots,\gamma_{k},\xi\}$. Since $\gamma_{n}$ is in (4) and $\xi$ is in (1), the constructed ONB is the ONB in Proposition 2.5. We denote this by $\{\psi_{0},\ldots,\psi_{k},\varphi\}$. Then, $\varphi$ is the navigate vector.

First, we consider about $\gamma_{n}$ and $\psi_{n}$. Let $U_{n}(x)$ be the second kind of Chebyshev polynomial, and define $u_{n}=U_{n}\left(\frac{1}{2\kappa}\right)$.

By this fact and $\gamma_{n}=a_{n}\psi_{n-1}+b_{n}\psi_{n}$, we have

	$\displaystyle\psi_{n}$	$\displaystyle=\frac{1}{b_{n}}(\gamma_{n}-a_{n}\psi_{n-1})=\frac{1}{b_{n}}\left(\gamma_{n}-\frac{a_{n}}{b_{n-1}}(\gamma_{n-1}-a_{n-1}\psi_{n-2})\right)=\cdots$
		$\displaystyle=\frac{1}{b_{n}}\sum_{s=0}^{n}(-1)^{n-s}\prod_{j=s+1}^{n}\frac{a_{j}}{b_{j-1}}\gamma_{s}=\frac{1}{\sqrt{\kappa u_{n}u_{n+1}}}\sum_{s=0}^{n}(-1)^{n-s}u_{s}\gamma_{s}$

which is the assertion. $\square$

Next, we consider about $\xi$ and $\varphi$. Define a projection $\Pi_{k}$ by

$$\Pi_{k}=\sum_{n=0}^{k}|\psi_{n}\rangle\langle\psi_{n}|.$$

$\Pi_{k}$ is also the projection onto ${\rm span}\{\gamma_{0},\ldots,\gamma_{k}\}$. Here, $\varphi$ is written as

$$\varphi=\frac{(I-\Pi_{k})\xi}{\|(I-\Pi_{k})\xi\|}.$$

By this proposition, we can calculate $\varphi(a)$ for an arc $a$, explicitly. Let $a$ be an arc on the left side of the cycle $\gamma_{0}$. If $\gamma_{0}(a)>0$, $\gamma_{0}(a)=\frac{1}{2\sqrt{m+l}}$. Moreover, by the assumption $\langle\gamma_{0},\xi\rangle\geq 0$, $\xi(a)>0$. Hence, when $\gamma_{0}(a)>0$, we have

	$\displaystyle\|(I-\Pi_{k})\xi\|\cdot\varphi(a)$	$\displaystyle=\xi(a)-\frac{\sqrt{2(l+m)}}{\sqrt{m+3}}\sum_{n=0}^{k}\frac{1}{u_{n}u_{n+1}}\sum_{s=0}^{n}(-1)^{s}u_{s}\gamma_{s}(a)$
		$\displaystyle=\frac{1}{\sqrt{2(m+3)}}-\frac{\sqrt{2(l+m)}}{\sqrt{m+3}}\sum_{n=0}^{k}\frac{1}{u_{n}u_{n+1}}\frac{1}{2\sqrt{l+m}}$
		$\displaystyle=\frac{1}{\sqrt{2(m+3)}}\left(1-\sum_{n=0}^{k}\frac{1}{u_{n}u_{n+1}}\right).$

When $\gamma_{0}(a)<0$, just multiply the above equation by $-1$. Similarly, when $a$ is an arc on the left side of the cycle $\gamma_{i}$ for $1\leq i\leq k$ and $\gamma_{i}(a)>0$,

	$\displaystyle\|(I-\Pi_{k})\xi\|\cdot\varphi(a)=\xi(a)-\frac{\sqrt{2(l+m)}}{\sqrt{m+3}}\sum_{n=0}^{k}\frac{1}{u_{n}u_{n+1}}\sum_{s=0}^{n}(-1)^{s}u_{s}\gamma_{s}(a)$
	$\displaystyle\quad=-\frac{1}{\sqrt{2(m+3)}}\left(\frac{1}{u_{i-1}u_{i}}(-1)^{i-1}u_{i-1}+\sum_{n=i}^{k}\frac{1}{u_{n}u_{n+1}}((-1)^{i-1}u_{i-1}+(-1)^{i}u_{i})\right).$

When $\gamma_{i}(a)<0$, just multiply the above equation by $-1$.