Quantum link prediction in complex networks
João P. Moutinho (Universidade Técnica de Lisboa, Instituto de Telecomunicações)
André Melo (Kavli institute of nanoscience Delft, TU Delft - QN/Akhmerov Group)
Bruno Coutinho (Instituto de Telecomunicações)
István A. Kovács (CEU: Central European University, Northwestern University)
Yasser Omar (Centro de Física e Engenharia de Materiais Avançados, Lisboa, Universidade Técnica de Lisboa)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
Predicting new links in physical, biological, social, or technological networks has a significant scientific and societal impact. Path-based link prediction methods utilize the explicit counting of even- and odd-length paths between nodes to quantify a score function and infer new or unobserved links. Here, we propose a quantum algorithm for path-based link prediction using a controlled continuous-time quantum walk to encode even and odd path-based prediction scores. Through classical simulations on a few real networks, we confirm that the quantum walk scoring function performs similarly to other path-based link predictors. In a brief complexity analysis we identify the potential of our approach in uncovering a quantum speedup for path-based link prediction.