A quantum algorithm for learning a graph of bounded degree

Asaf Ferber, Liam Hardiman

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. Wh…