The article presents a groundbreaking mathematical framework for solving maze problems using quantum walks, a quantum analog of classical random walks. It highlights the superior efficiency of quantum walks in exploring networks, leveraging probability amplitude interference and faster propagation speeds. The study introduces a novel approach by incorporating self-loops at the start and goal vertices, along with sinks that absorb probability amplitudes, to guide the quantum walker along the shortest path. The paper delves into the spectral properties of the Grover walk, demonstrating how the probability distribution in the long-time limit is determined by the navigation vector, which is induced by fundamental cycles and shortest paths. The authors provide detailed analyses for tree structures and ladder graphs, showcasing the versatility and robustness of their method. Furthermore, the article discusses the implications of placing sinks at different vertices, illustrating how this affects the stability and convergence of the quantum walk. The findings suggest potential applications in various fields, including network optimization and quantum computing, where efficient pathfinding is crucial.
AI Generated
This summary of the content was generated with the help of AI.
Abstract
We provide a mathematical framework for identifying the shortest path in a maze using a Grover walk, which becomes non-unitary by introducing absorbing holes. In this study, we define the maze as a network with vertices connected by unweighted edges. Our analysis of the stationary state of the truncated Grover walk on finite graphs, where we strategically place absorbing holes and self-loops on specific vertices, demonstrates that this approach can effectively solve mazes. By setting arbitrary start and goal vertices in the underlying graph, we obtain the following long-time results: (i) in tree structures, the probability amplitude is concentrated exclusively along the shortest path between start and goal; (ii) in ladder-like structures with additional paths, the probability amplitude is maximized near the shortest path.
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
1 Introduction
The development of algorithms for finding the shortest path in networks has a rich history [7, 12] and plays an important role in a wide array of practical applications in our daily lives, such as in car navigation systems. The term ‘networks’ includes various forms, from physical structures like roads and power lines to more abstract ideas. From the study of networks, a larger field known as complex networks has emerged [5, 34], which has recently expanded its focus to include quantum mechanics [4]. The maze-solving problem can be viewed as a fundamental case of the shortest path problem in networks. Here, we define a maze as a network consisting of unweighted edges that represent distance parameters. Consequently, maze-solving techniques are regarded as a subset of the shortest path problem, with various algorithms, including breadth-first search [9], Dijkstra’s algorithm [11], and the Bellman–Ford algorithm [3], having been developed in classical settings.
The challenge of solving mazes has become an important area of research in the field of natural computing. Various natural phenomena, such as slime molds [27, 35], the Belousov–Zhabotinsky (BZ) reaction [33], electrical discharges [30], and the propagation of light in waveguides [6], have mechanisms that can effectively navigate mazes. While humans typically rely on intelligence to solve such problems, nature’s ability to accomplish the same task highlights that intelligence is not strictly necessary; instead, the key lies in algorithms governed by simple rules.
Advertisement
In exploring networks like mazes, the movement of a probabilistic walker throughout the network represents a specific type of algorithm. In classical exploration methods, the walker corresponds to probability density, while in quantum exploration methods, it relates to probability amplitude. The basic approach to classical exploration is the random walk. Quantum walks have been introduced as the quantum version of random walks and are expected to improve effectiveness in exploration problems because their probability propagation speed is directly proportional to time, unlike random walks, where it is proportional to the square root of time [2, 16]. Furthermore, quantum walks can utilize the interference of probability amplitudes, providing another advantage in exploration tasks.
The maze-solving approach utilizing quantum walks is derived from quantum search [1, 8, 28, 32]. Investigating specific points in a network using quantum walks is similar to implementing Grover’s algorithm on structured networks [17]. Koch et al. extended their research on identifying structural anomalies in networks [10, 15, 22] and demonstrated that executing a Grover walk in a maze—where the vertices at the start and goal undergo phase inversion—can result in the temporary identification of the shortest path [21, 23, 24, 29]. In contrast, Matsuoka et al. advanced the study of quantum walks by accounting for both inflow and outflow [13, 14, 18‐20, 25, 31], creating a more robust and versatile approach [26]. In our paper, by integrating self-loop structures at the maze’s start and goal, along with incorporating holes that absorb probability amplitudes, we introduce the navigation vector which is induced by the fundamental cycles and the shortest path between the pair of the vertices having the self-loop of the underlying graph. Our mathematical results tell us that a quantum walker takes a time to find autonomously the navigation vector, and as a result, it clings along the shortest path between the start and goal of some mazes in the stationary state. Although Matsuoka et al.’s method is not suitable for mazes with cycles that have an odd number of nodes, it has been shown to extend to tree structures and ladder configurations featuring multiple paths. Furthermore, since all time evolution can be expressed as the problem of matrix exponentiation defined by the network structure, this approach enables efficient computations using GPUs, independent of the number of steps or vertices, suggesting its potential as a classical algorithm inspired by quantum mechanics.
In this paper, we present a mathematical reconstruction of the maze-solving method utilizing Grover walk, leading to an explicit derivation of its limit distribution. In Sect. 2, we outline the detailed structure of the graph that represents the maze and discuss the time evolution of the Grover walk. We also examine the spectral properties of the Grover walk in this context, demonstrating that the probability distribution in the long-time limit is determined by the overlap between the initial state and the eigenspace associated with the eigenvalue \(-1\), known as the navigation vector. In Sect. 3, we detail the limit distribution of the Grover walk specifically for tree structures and ladder graphs.
2 Settings and properties of Grover walk
2.1 Settings
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.
Advertisement
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 Fig. 1). The degree of \(v \in V\) is given by
for any \(\xi \in {{\mathcal {H}}}_A\). The first term of the right-hand side of the above definition is given by the state reflected from \(\bar{a}\) with the sign flip, and the second term is given by the twice of the average of the incoming states to o(a). For example (see Fig. 2), let the degree of a vertex be 3, and let the incoming values be \(\alpha \), \(\beta \) and \(\gamma \). Then, the outgoing values after mapping by the Grover walk are
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
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\).
2.2 Spectral decomposition of U for maze solving
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\).
Lemma 2.1
Let \(\xi \in {{\mathcal {H}}}_A\) be an eigenvector of U associated with the eigenvalue \(\lambda \). Then, \(\xi (d) = \lambda \xi (\bar{d})\).
Proof
By the definition of Grover walk, we have
$$\begin{aligned} (U \xi )(\bar{d}) = \xi (d). \end{aligned}$$
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) \ne 0, \xi (d)=0,\) (2) \(\xi (s) \ne 0, \xi (d) \ne 0\),
Note that by Lemma 2.1, \(\xi (d)=0\) implies \(\xi (\bar{d})=0\), and \(\xi (d)\ne 0\) implies \(\xi (\bar{d})\ne 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 \textrm{supp}(\xi )\) for any \(\xi \) in (1) or (4). First, we consider the eigenspace \(V(-1)\) because of the following strong statement.
Lemma 2.2
Assume that the eigenvector \(\xi \) is in (1). Then, \(\xi \) must be an eigenvector of the eigenvalue \(-1\).
Proof
Let \(\{a_i\}_{i=1}^n\) be the set of all arcs which satisfy \(t(a_i) = s\), where \(a_1=\bar{d}\) and \(a_2 = s\). Let \(\xi \) have the eigenvalue \(\lambda \). Since \(\xi (d)=\xi (\bar{d})=0\) and
we have \(\sum _{i=1}^n \xi (a_i) =0\). Therefore,
$$\begin{aligned} \lambda \xi (s) = (U\xi )(s) =-\xi (s) + \frac{2}{n} \sum _{i=1}^n \xi (a_i) = -\xi (s). \end{aligned}$$
By the assumption \(\xi (s) \ne 0\), we have \(\lambda =-1\). \(\square \)
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 5 illustrates this eigenvector.
Lemma 2.3
There exists an eigenvector \(\xi \in V(-1)\) such that \(\xi \) is in (1).
Proof
Let \(\{a_i\}_{i=1}^n\) be a path which satisfies \(t(a_i)=o(a_{i+1})\), \(o(a_1)=s\), \(t(a_n)=g\), \(o(a_i)\ne o(a_j)\)\((i\ne j)\), and \(t(a_i)\ne t(a_j)\)\((i\ne j)\), and let \(a_0 =s\) and \(a_{n+1}= g\). Define a vector \(\xi \in {{\mathcal {H}}}_A\) by
Then, it is easy to check that \(\xi \) is an eigenvector in \(V(-1)\). (See Fig. 5.) \(\square \)
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).
Lemma 2.4
Every eigenvector \(\xi \) in \(V(-1)\) satisfies \(\xi (d)=0\), that is, \(\xi \) is in (1) or (4).
Proof
Let \(\xi \) be an eigenvector in \(V(-1)\). We use the same setting as in the proof of Lemma 2.2. Similar to the proof of Lemma 2.2,
$$\begin{aligned} -\xi (s) = (U\xi )(s) = -\xi (s) +\frac{2}{n}\sum _{i=1}^n \xi (a_i). \end{aligned}$$
Hence, \(\sum _{i=1}^n \xi (a_i) =0\). Since \(\xi (d) = -\xi (\bar{d})\) by Lemma 2.1,
Now we are ready to construct an ONB for \(V(-1)\) as follows.
Proposition 2.5
There exists an ONB \(\{ \psi ^{(-1)}_1, \ldots , \psi ^{(-1)}_{\dim V(-1) -1},\varphi \}\) of \(V(-1)\) such that \(\varphi \) is in (1) and \(\psi _i^{(-1)}\) is in \(\mathrm{(4)}\).
Proof
Let \(k = {\dim V(-1)}\), and let \(\{\xi _1, \ldots , \xi _k\}\) be a bases of \(V(-1)\) with \(\xi _k(s)\ne 0\). We can take such a basis by setting \(\xi _k\) to be in (1). Define a vector \(\eta _i\) by
Remark that \(\eta _i\) is in (4) for \(1\le i \le k-1\). We apply the Gram–Schmidt process to \(\{\eta _i\}_{i=1}^k\) and denote the constructed vectors by \(\{\psi _1^{(-1)}, \ldots , \psi _{k-1}^{(-1)}, \varphi \}\). This is the desired ONB. \(\square \)
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 \(\textrm{dim} V(-1)-1\) bases of \(V(-1)\) in Proposition 2.5, \(\psi _j^{(-1)}\) (\(1\le j \le \textrm{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 ,\textrm{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 \ne -1\) to the survival probability \(\Vert (PU)^n \zeta \Vert ^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 \ne -1\) to the survival probability. To this end, we construct an ONB of \(V(\lambda )\) with \(\lambda \ne -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 \ne -1\) is not in (2), or is not in (3) as follows.
Lemma 2.6
Suppose \(\lambda \ne -1\). \(V(\lambda )\) does not contain both of vectors in (2) and (3).
Proof
When \(\xi _2 \in V(\lambda )\) is in (2) and \(\xi _3 \in V(\lambda )\) is in (3), we can construct an eigenvector \(\xi _1 \in V(\lambda )\) in (1) using a linear combination. Then, \(\lambda =-1\) by Lemma 2.2, which is contradiction. \(\square \)
Using Lemma 2.6, we can construct the following ONB for \(\lambda \ne -1\) concerning to the overlap with d and \(\bar{d}\).
Proposition 2.7
There exists an ONB \(\{\psi ^{(\lambda )}_1, \ldots , \psi _{\dim V(\lambda )}^{(\lambda )}\}\) of \(V(\lambda )\) such that at most one vector in the ONB is in (2) or (3).
Proof
If there is no vector in (2) or (3) in \(V(\lambda )\), then all vectors in \(V(\lambda )\) are in (4), and we can construct the desired ONB, easily.
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 = \textrm{dim}V(\lambda )\), and let \(\{\xi _1,\ldots , \xi _k\}\) be a basis of \(V(\lambda )\) with \(\xi _k (s) \ne 0\) and \(\xi _k(d) \ne 0\). Define a vector \(\eta _i\) by
Remark that \(\eta _i\) is in (4) for \(1\le i \le 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)} = \textrm{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,
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}}} = \textrm{span} \{ \eta ^{(\lambda )} \, | \, \lambda \in \sigma (U) \}\). We see that this subspace is invariant under P defined in (2.1).
Lemma 2.8
\({{\mathcal {K}}}\) is invariant under P, that is, \(P{{\mathcal {K}}} \subset {{\mathcal {K}}}\).
Proof
Remark that \(P\varphi =\varphi \) and \(P\psi _i^{(\lambda )} = \psi _i^{(\lambda )}\)\((1\le i \le k^{(\lambda )})\). It is sufficient to prove that \(P{{\mathcal {K}}}\) is orthogonal to \(\varphi \) and \(\psi _i^{(\lambda )}\). For \(\xi \in {{\mathcal {K}}}\), we have
Similarly, we can check that \(P\xi \) is orthogonal to \(\psi _i^{(\lambda )}\). \(\square \)
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.
Since \({{\mathcal {K}}}\) is invariant under PU by Lemma 2.8, it is enough to prove that the absolute value of the eigenvalue of \(PU|_{{{\mathcal {K}}}}\) is less than 1.
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
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^{\textrm{i}t} \eta ^{(\lambda )}\) for some \(t \in {\mathbb R}\). However, this contradicts \(\eta (d)=0\). \(\square \)
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:
Proposition 2.10
Let \(\mu _n(v)\) be the probability at position v at time n, and \(\varphi \) be the navigation vector defined the above. Then we have
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.
We note that the limits in Proposition 2.10 and (2.3) converge exponentially, because of Proposition 2.9. However, the rate of convergence is not known at the moment. This problem was also considered in [26]. It was shown that the minimal time for convergence depends intricately on the structure of the maze and is not simply related to the size of the maze.
3 Maze solving
3.1 Tree case
When the graph is a tree, we can determine the navigation vector.
Theorem 3.1
When the underlying graph is a tree, the navigation vector is constant multiple of the vector defined in the proof of Lemma 2.3.
Proof
When the underlying graph \(G_o=(V_o,E_o)\) is bipartite, the dimension of \(V(-1)\) is given by \((|E_o|-|V_o|+1)+1\) [25, Proposition 6 for Case (C)]. Note that for tree case, the Betti number \(|E_o|-|V_o|+1\) becomes 0. Then \(\dim V(-1)=1\). On the other hand, the navigation vector and the vector defined in Lemma 2.3 are both in \(V(-1)\). These imply the assertion of this theorem. \(\square \)
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
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.
3.2 The case the graph has cycles
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 Sect. 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 Fig. 7. Before describing the setting, we prove the next lemma.
Lemma 3.2
For a cycle \(\gamma \in G\) of length 2n\((n \in {\mathbb N})\), there exists an eigenvector of the Grover walk U associated with the eigenvalue \(-1\).
Proof
Let \(\{a_i\}_{i=1}^{2n}\) be a cycle of length 2n, that is, \(t(a_i)=o(a_{i+1})\), \(o(a_1) = t(a_{2n})\) and \(t(a_i) \ne t(a_j)\)\((i\ne j)\). Define a vector \(\xi \in {{\mathcal {H}}}_A\) by
The ladder graph with the self-loops and the sink. The left figure illustrates the graph treated in Sect. 3.2. This graph is constructed by \(k+1\) cycles \(\gamma _i\) (\(i=0,1,\dots ,k\)) depicted by the right figure. Each cycle whose length is m and width is \(\ell \) has the eigenvector of the eigenvalue \(-1\), \(\gamma _i\) (\(i=0,\dots ,k\)). (The notations for the cycle and the induced eigenvector are same.)
Now, we consider a ladder graph. As in Fig. 7, 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 \le n \le 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 \ge 0\) and \(\langle \gamma _0, \xi \rangle \ge 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 \(\textrm{span}\{\gamma _0\dots ,\gamma _{k}\}=\textrm{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.
The first and second equations are obvious by the definition of \(\gamma _s\) and \(\xi \). The inner product in the third equation can be calculated as
because of the assumption \(\langle \gamma _s, \gamma _{s+1}\rangle \ge 0\)\(\square \)
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) \).
where \(a_0=0\). Remark that \(b_0=1\) and \(a_n, b_n \in {\mathbb R}\). Since \(\psi _n\) is the normalization of \(\gamma _n - \sum _{s=0}^{n-1} \langle \psi _s, \gamma _n\rangle \psi _s\) and \(\langle \psi _n, \gamma _n\rangle = b_n \), \(b_n\) is positive. Moreover,
implies \(a_{n+1}b_n = \kappa \), and \(\Vert \gamma _n\Vert =1\) implies \(a_n^2+b_n^2=1\). The equation \(a_{n+1}b_n =\kappa \) means that \(a_{n+1}\) and \(b_n\) have the same sign, and therefore, \(a_n\) is positive for \(n \ge 1\). To calculate \(a_n^2\) and \(b_n^2\), we use Chebyshev polynomial. We claim that
where \(u_{-1}=0\). Indeed, we can prove this using a similar method to the proof in [31], or we can check that these \(a_n^2\) and \(b_n^2\) satisfy the above recurrence relations.
By this fact and \(\gamma _n = a_n\psi _{n-1} + b_n\psi _{n}\), we have
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 \ge 0\), \(\xi (a) >0\). Hence, when \(\gamma _0(a) >0\), we have
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\le i \le k\) and \(\gamma _i(a) >0\),
Let \(x = \frac{1}{2\kappa }\). When \(n=0\), \(u_0 = U_0(x) = 1\) and \(u_1 =U_1(x) = 2x\). Since \(x >1\), we have \(u_1 \ge u_0+1\). If the inequality is true for i, we have
The next proposition shows that the probability \(p_i\) of finding the quantum walker at the left-hand side of \(\gamma _i\) is monotonically decrease.
Theorem 3.8
Let \(a_i\) be an arc on the left side of the cycle \(\gamma _i\) for \(0\le i \le k\). Then, the inequality
When \(\gamma _i(a)<0\), just multiply the above equation by \(-1\). The next proposition shows that the probability \(q_i\) of finding the quantum walker at the top side of \(\gamma _i\) is also monotonically decrease.
Theorem 3.9
Let \(a_i\) be an arc on the top side of cycle \(\gamma _i\) for \(0\le i \le k\). Then, the inequality
Proposition 3.6 says that the amplitude of the navigation vector may not be zero even at a point outside of the shortest route from the start to the goal. On the other hand, Theorems 3.8 and 3.9 show that the quantum walker is more likely to be at a point on a shorter route. Hence, in the case of ladder graph, the position of the quantum walker tells us a shorter route, although not as much as in the case of tree graph.
3.3 Comparison with the digraph with a sink at the goal
A method of maze solving was considered by adding the sink at the goal in [26]. In this subsection, we discuss differences between the method in [26] and ours.
Example 3.10
The digraph in the left-hand side of Figure 8 is considered in [26]. When we put the sink at the goal, the state \((PU)^n \zeta \) does not converge. The reason why this happens is that there exists an eigenvector in (1) whose eigenvalue is not \(-1\). Let \(\lambda = e^{\frac{2\pi \textrm{i}}{3}}\) and \(t=-\frac{\sqrt{3}}{2} \textrm{i}\). Then, the vector defined as in the right-hand side of Figure 8 is the eigenvector associated with the eigenvalue \(\lambda \). This eigenvector is the cause of oscillations of amplitudes (See [25, 26]).
Fig. 8
Digraph considered in [26] and an eigenvector in (1)
On the other hand, when we put the sink at the start, the state \((-1)^n (PU)^n \zeta \) definitely converges. (See also Sect. 3.2.)
Example 3.11
When the sink is at the goal, we can make an example where the amplitudes of the state \((PU)^n \zeta \) appear at points other than the start-to-goal path. Let \(\lambda =e^{\frac{\pi \textrm{i}}{3}}\) and \(k=6\,l+3\)\((l \in {\mathbb N})\). Then, the vector defined as in Fig. 9 is in (1) whose eigenvalue is not \(-1\).
Therefore, \((PU)^n \zeta \) always has nonzero coefficients on the cycle of length k. This means that the position of the quantum walker does not tell us the shortest route. Probably, it misleads us.
4 Summary
We have established a mathematical framework for maze solving using quantum walks and explicitly derived the limit distribution. Our method resembles the placement of food at the start and goal in slime mold maze solving by incorporating self-loops at these vertices, which enables the emergence of the shortest path within the quantum walk structure. Moreover, we found that adding the sink at the start rather than at the goal effectively prevents the emergence of unstable states. These phenomena are based on the spectral properties of the Grover walk, characterized by a birth space defined by fundamental cycles, self-loops, and sinks. Although this eigenspace has not been utilized in existing quantum search algorithms, it plays an important role in our maze-solving methodology.
Acknowledgements
E.S. is supported by JSPS KAKENHI Grant Number 24K06863.
H.O. is supported by JSPS KAKENHI Grant Number 23K03147.
Declarations
Conflict of interest
The authors have no conflict of interest to declare that are relevant to the content of this article.
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Aaronson, S., Ambainis, A.: Quantum search of spatial regions. Theory Comput. 1(4), 47–79 (2005)MathSciNetMATH
2.
Ambainis, A. Bach, E., Nayak, A., Vishwanath, A., Watrous, J.: One-dimensional quantum walks. In: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, pp. 37–49 (2001)
3.
Bellman, R.: On a routing problem. Q. Appl. Math. 16, 87–90 (1958)MATH
4.
Biamonte, J., Faccin, M., Domenico, M.D.: Complex networks from classical to quantum. Commun. Phys. 2, 53 (2019)MATH
5.
Boccaletti, S., Latora, V., Moreno, Y., Chavez, M., Hwang, D.-U.: Complex networks: structure and dynamics. Phys. Rep. 424(4), 175–308 (2006)ADSMathSciNetMATH
6.
Caruso, F., Crespi, A., Ciriolo, A., Sciarrino, F., Osellame, R.: Fast escape of a quantum walker from an integrated photonic maze. Nat. Commun. 7, 11682 (2016)ADSMATH
7.
Cherkassky, B.V., Goldberg, A.V., Radzik, T.: Shortest paths algorithms: theory and experimental evaluation. Math. Program. 73, 129–174 (1996)MathSciNetMATH
8.
Childs, A.M., Goldstone, J.: Spatial search by quantum walk. Phys. Rev. A 70, 022314 (2004)ADSMATH
9.
Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms 3rd ed. (2009)
10.
Cottrell, S., Hillery, M.: Finding structural anomalies in star graphs using quantum walks. Phys. Rev. Lett. 112, 030501 (2014)ADSMATH
11.
Dijkstra, E.: A note on two problems in connexion with graphs. Numer. Math. 1, 269–271 (1959)MathSciNetMATH
12.
Dreyfus, S.: An appraisal of some shortest path algorithm. Oper. Res. 17, 395–412 (1969)MATH
13.
Feldman, E., Hillery, M.: Quantum walks on graphs and quantum scattering theory. Contemp. Math. 381, 71–96 (2005)MathSciNetMATH
14.
Feldman, E., Hillery, M.: Modifying quantum walks: a scattering theory approach. J. Phys. A: Math. Theor. 40, 11319 (2007)MathSciNetMATH
15.
Feldman, E., Hillery, M., Lee, H.-W., Reitzner, D., Zheng, H., Bužek, V.: Finding structural anomalies in graphs by means of quantum walks. Phys. Rev. A 82, 040301 (2010)ADSMathSciNetMATH
16.
Feynman, R.P., Hibbs, A.R.: Quantum Mechanics and Path Integrals. (2010)
17.
Grover, L.K.: Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett. 79, 325–328 (1997)ADSMATH
18.
Higuchi, Y., Sabri, M., Segawa, E.: Electric circuit induced by quantum walk. J. Stat. Phys. 181, 603–617 (2020)ADSMathSciNetMATH
19.
Higuchi, Y., Segawa, E.: Circuit equation of Grover walk. Annales Henri Poincaré in Pess, arXiv:2211.00920
20.
Higuchi, Y., Segawa, E.: Dynamical system induced by quantum walks. J. Phys. A: Math. Theoret. 52, 39520 (2019)MathSciNetMATH
21.
Hillery, M.: Finding more than one path through a simple maze with a quantum walk. J. Phys. A: Math. Theoret. 54(9), 095301 (2021)ADSMathSciNetMATH
22.
Hillery, M., Zheng, H., Feldman, E., Reitzner, D., Bužek, V.: Quantum walks as a probe of structural anomalies in graphs. Phys. Rev. A 85, 062325 (2012)ADSMATH
23.
Koch, D.: Scattering quantum random walks on square grids and randomly generated mazes. Phys. Rev. A 99, 012330 (2019)ADS
24.
Koch, D., Hillery, M.: Finding paths in tree graphs with a quantum walk. Phys. Rev. A 97, 012308 (2018)ADSMathSciNetMATH
25.
Konno, N., Segawa, E., Stefanak, M.: Relation between quantum walks with tails and quantum walks with sinks on finite graphs. Symmetry 13, 1169 (2021)ADSMATH
26.
Matsuoka, L., Yuki, K., Lavička, H., Segawa, E.: Maze solving by a quantum walk with sinks and self-loops: numerical analysis. Symmetry 13, 2263 (2021)ADSMATH
27.
Nakagaki, T., Yamada, H., T’oth, A.: Maze-solving by an amoeboid organism. Nature 407, 470 (2000)ADSMATH
28.
Portugal, R.: Quantum Walk and Search Algorithm, 2nd Ed. Springer Nature Switzerland (2018)
29.
Reitzner, D., Hillery, M., Koch, D.: Finding paths with quantum walks or quantum walking through a maze. Phys. Rev. A 96, 032323 (2017)ADSMathSciNetMATH
30.
Reyes, D.R., Ghanem, M.M., Whitesides, G.M., Manz, A.: Glow discharge in microfluidic chips for visible analog computing. Lab Chip 2, 113–116 (2002)
31.
Segawa, E., Koyama, S., Konno, N., Štefaňák, M.: Survival probability of the grover walk on the ladder graph. J. Phys. A: Math. Theoret. 56, 215301 (2023)ADSMathSciNetMATH
Teroa, A., Kobayashia, R., Nakagaki, T.: A mathematical model for adaptive transport network in path finding by true slime mold. J. Theoret. Biol. 244, 553–564 (2007)ADSMathSciNetMATH
