Quantum Link Prediction in Complex Networks

Password: 392699

Meeting ID: 836 1514 8258

Predicting new links in physical, biological, social, or technological networks has a significant scientific and societal impact. Network based link prediction methods utilize topological patterns in a network to infer new or unobserved links. Here, we propose a quantum algorithm for link prediction, QLP, which uses quantum walks to infer unknown links based on even and odd length paths. By sampling new links from quantum measurements, QLP avoids the need to explicitly calculate all pairwise scores in the network. We study the complexity of QLP and discuss in which cases one may achieve a polynomial speedup over classical link prediction methods. Furthermore, tests with real-world datasets show that QLP is at least as precise as state-of-the-art classical link prediction methods, both in cross-validation tests and in the prediction of experimentally verified protein-protein interactions.