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.
| Original language | English (US) |
|---|---|
| Article number | 032605 |
| Journal | Physical Review A |
| Volume | 107 |
| Issue number | 3 |
| DOIs | |
| State | Published - Mar 2023 |
Funding
The authors thank Albert-L\u00E1szl\u00F3 Barab\u00E1si for the useful discussion and acknowledge the support from the JTF project The Nature of Quantum Networks (Project No. 60478). J.P.M., B.C., and Y.O. thank the support from Funda\u00E7\u00E3o para a Ci\u00EAncia e a Tecnologia (FCT, Portugal), namely through Projects No. UIDB/50008/2020 and No. UIDB/04540/2020, as well as from projects TheBlinQC and QuantHEP supported by the EU H2020 QuantERA ERA-NET Cofund in Quantum Technologies and by FCT (QuantERA/0001/2017 and QuantERA/0001/2019, respectively), and from the EU H2020 Quantum Flagship project QMiCS (820505). J.P.M. acknowledges the support of FCT through scholarship SFRH/BD/144151/2019, and B.C. acknowledges the support of FCT through Project No. CEECINST/00117/2018/CP1495/CT0001.
ASJC Scopus subject areas
- Atomic and Molecular Physics, and Optics