2024/02/28 by Ferber, Asaf, Hardiman, Liam
#Combinatorics (math.CO) #FOS: Mathematics #FOS: Physical sciences #Quantum Physics (quant-ph)
paper · doi:10.48550/arxiv.2402.18714
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 log 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(d2m3/4) quantum queries. This gives an upper bound of O(m3/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.