Finding paths with quantum walks or quantum walking through a maze

We show that it is possible to use a quantum walk to find a path from one marked vertex to another. In the specific case of $M$ stars connected in a chain, one can find the path from the first star to the last one in $O\left(M\sqrt{N}\right)$ steps, where $N$ is the number of spokes of each star. First we provide an analytical result showing that by starting in a phase-modulated highly superposed initial state we can find the path in $O(M\sqrt{N}logM)$ steps. Next, we improve this efficiency by showing that the recovery of the path can also be performed by a series of successive searches when we start at the last known position and search for the next connection in $O\left(\sqrt{N}\right)$ steps leading to the overall efficiency of $O\left(M\sqrt{N}\right)$. For this result we use the analytical solution that can be obtained for a ring of stars of double the length of the chain.

Figure 1

In the chain of stars $\mathcal{G}$ the task is to find the whole path from a known start vertex to an unknown end vertex.

Figure 2

Typical evolutions of the success probability to find the next connection in the chain of stars for different starting stars connections with $M=11, N=450$—dark when starting near the start vertex, medium gray when starting at the first connection, and light when starting in the connection of some middle (fifth and sixth) stars, or without correcting terms from reflections. Dots represent exact solution from Eq. (20), while the lines are approximations by Eq. (33).

Figure 3

The correspondence between the chain of stars of length $M$ (here $M=4$) and the ring of stars of length $2M$. The state on the normal part of the ring (black) is complemented by a mirroring part (gray) of the same size but opposite sign to simulate the reflections on vertices $B_{01}$ and $B_{M1}$.