{
  "id": "2211.16331",
  "version": "v1",
  "published": "2022-11-29T16:13:24.000Z",
  "updated": "2022-11-29T16:13:24.000Z",
  "title": "On the complexity of quantum link prediction in complex networks",
  "authors": [
    "João P. Moutinho",
    "Duarte Magano",
    "Bruno Coutinho"
  ],
  "comment": "Keywords: Continuous-Time Quantum Walks, Quantum Algorithms, Complex Networks, Link Prediction",
  "categories": [
    "quant-ph"
  ],
  "abstract": "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 analyse the 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 quantum complexity of our quantum link prediction 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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-11-29T16:13:24.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "complex networks",
      "complexity",
      "quantum algorithm",
      "quantum link prediction algorithm",
      "link prediction methods"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}