Finding paths in tree graphs with a quantum walk

We analyze the potential for different types of searches using the formalism of scattering random walks on quantum computers. Given a particular type of graph consisting of nodes and connections, a “tree maze,” we would like to find a selected final node as quickly as possible, faster than any classical search algorithm. We show that this can be done using a quantum random walk, both through numerical calculations as well as by using the eigenvectors and eigenvalues of the quantum system.

Figure 1

An $N$-tree maze, where $N=2$ (also referred to as a “binary tree”) and $M=4$. $F$ is always located at an end node at the deepest layer.

Figure 2

$(N=2,M=3)$ The probability of successfully locating $F$ as a function of steps, using a classical depth-first search. Each time an end node is checked, the result is a spike in probability.

Figure 3

$(N=3,M=10)$ The concentration of probability on states representing the edge connected to $F$ (solid line) and the sum of the probabilities of the states representing the edges connecting $S$ to $F$ (except the two states directly connected to $S$) (dashed line).

Figure 4

Peak probabilities for measuring a state represented by the edge connected to $F$.

Figure 5

Peak probabilities for measuring a state along the correct path, which are states along the path connecting $S$ to $F$.

Figure 6

$(N=2,M=15)$ Plotted are the probabilities of the eight closest edges (two states per edge) to $F$ as a function of unitary steps. The states bunched together at the top are closest to $F$. The three lines with the lowest peaks represent the sixth, seventh, and eighth furthest edges from $F$. Thus we can see that edges further away from $F$ start to contribute significantly less than edges closest to $F$, as quickly as the halfway point in the path.

Figure 7

$(N=2,M=15)$ Probability of success as a function of steps for a classical depth-first search (dashed line) and probability of success as a function of steps using a quantum system to search for $F$ directly (solid line). The dashes along the $x$ axis mark the point for the average number of steps of the two searches, respectively.

Figure 8

$(N=2)$ The speedups of quantum over classical searches as a function $M$. These speedups are the result of using the “search for $F$ directly” algorithm, analogous to a Grover search.

Figure 9

$(N=2)$ The probabilities of measuring $F$ when the system is prepared to maximize the probability of $F$ (circles), and the probabilities of measuring $F$ when the system is prepared to maximize the probability of measuring a state along the correct path (triangles).

Figure 10

Following a measurement (marked by the star), we then turn a single node “off” and consequently freeze-out edges and nodes behind it (gray dashed lines). These frozen-out edges and nodes no longer affect the active quantum system (black solid lines) and are no longer in the Hilbert space $\mathcal{H}$ or unitary operator.

Figure 11

$(N=2)$ The average speed by which the algorithm measures a final node and effectively exits the dead tree.

Figure 12

$(N=2)$ Plotted are the average speeds for finding the correct final node $F$, for all the algorithms discussed: jumping (circles with dashed lines), search for $F$ directly (triangles with dashed lines), classical (squares with solid lines).

Figure 13

$(N=2,M=10)$ Probability of the path states using the approximation in Eq. (19) (dashed line) and actual probability of the path, generated numerically (solid line).

Figure 14

Eigenangles ${\theta }_{\lambda }$ plotted as a function of $N$ (dots) and power-fit curve of the form $y={Ax}^B$ (red line).