Abstract: Quantum walks provide a natural framework to approach graph and network problems with quantum computers, exhibiting speedups over their classical counterparts. For examplex 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.
Seminar: "Quantum computation for complex network problems" by B. Coutinho, Lisbon Uni.
23 feb 2023 ,15.00 - Venue: room 212, Department of Physics and Astronomy