Using quantum mechanics to find your way through a maze

A quantum walk is a quantum version of a classical random walk. It can take place on a line or on a more complicated graph. Quantum walks can be used to find a distinguished vertex of a graph or anomalous structural elements, such as an extra edge or loop, with a quantum speedup. In recent work we have shown they can also find paths. We discuss two kinds of graphs, linked stars and trees, and show that a quantum walk can find a path between a vertex labeled START and one labeled FINISH with a quantum speedup.