Finding edge permutations in a graph using quantum walks

The problem of graph structure discovery is important in many fields of science. Quantum walks are expected to bring significant algorithmic improvements to quantum computing. More generally, random walks (Markov chains on graphs) can be very useful as a different approach to problems. We use a specific quantum walk to address unknown permutations in a graph. Consider two matching graphs, with unknown permutations of edges that connect them. For example: a vertex on the left is connected to a set of vertices to its right; on the far right is another vertex, connected to another set of nodes, to its left. These two sets of nodes are connected in the middle, but we do not know which left nodes connect to which right ones. We construct a quantum walk on such a graph structure that allows us to gain a surprising amount of information, or completely determine permutations, often in a single pass over the graph. We detect classes of interesting properties of our walk on such unknown graphs. Classical walks cannot resolve some cases at all, implying a formally ``infinite'' speed up. This walk is an example of use of our recent framework for building quantum walks, based on classical walks with memory. The framework contains all major known walks, while it can also build walks on structures prohibitively difficult for current techniques.