A quantum algorithm for learning a graph of bounded degree

We are presented with a graph, G, on n vertices with m edges whose edge set is unknown. Our goal is to learn the edges of G with as few queries to an oracle as possible. When we submit a set S of vertices to the oracle, it tells us whether or not S induces at least one edge in G. This so-called OR-query model has been well studied, with Angluin and Chen giving an upper bound on the number of queries needed of O (m n) for a general graph G with m edges. When we allow ourselves to make *quantum* queries (we may query subsets in superposition), then we can achieve speedups over the best possible classical algorithms. In the case where G has maximum degree d and is O (1) -colorable, Montanaro and Shao presented an algorithm that learns the edges of G in at most O (d²m^3/4) quantum queries. This gives an upper bound of O (m^3/4) quantum queries when G is a matching or a Hamiltonian cycle, which is far away from the lower bound of (m) queries given by Ambainis and Montanaro. We improve on the work of Montanaro and Shao in the case where G has bounded degree. In particular, we present a randomized algorithm that, with high probability, learns cycles and matchings in O (m) quantum queries, matching the theoretical lower bound up to logarithmic factors.