  Link prediction methods use patterns in known network data to infer which
connections may be missing. Previous work has shown that continuous-time
quantum walks can be used to represent path-based link prediction, which we
further study here to develop a more optimized quantum algorithm. Using a
sampling framework for link prediction, we analyze the query access to the
input network required to produce a certain number of prediction samples.
Considering both well-known classical path-based algorithms using powers of the
adjacency matrix as well as our proposed quantum algorithm for path-based link
prediction, we argue that there is a polynomial quantum advantage on the
dependence on $N$, the number of nodes in the network. We further argue that
the complexity of our algorithm, although sub-linear in $N$, is limited by the
complexity of performing a quantum simulation of the network's adjacency
matrix, which may prove to be an important problem in the development of
quantum algorithms for network science in general.
