Moutinho João P, Magano Duarte, Coutinho Bruno
Instituto Superior Técnico, Universidade de Lisboa, Lisboa, Portugal.
Instituto de Telecomunicações, Lisboa, Portugal.
Sci Rep. 2024 Jan 10;14(1):1026. doi: 10.1038/s41598-023-49906-4.
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 analyze 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 complexity of our 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.
链接预测方法利用已知网络数据中的模式来推断哪些连接可能缺失。先前的工作表明，连续时间量子游走可用于表示基于路径的链接预测，我们在此进一步研究以开发更优化的量子算法。使用用于链接预测的采样框架，我们分析了生成一定数量的预测样本所需的对输入网络的查询访问。考虑到使用邻接矩阵幂的著名经典基于路径的算法以及我们提出的基于路径的链接预测量子算法，我们认为在对网络中节点数量(N)的依赖性上存在多项式量子优势。我们进一步认为，我们算法的复杂度虽然在(N)上是次线性的，但受到执行网络邻接矩阵量子模拟的复杂度的限制，这在一般网络科学量子算法的开发中可能被证明是一个重要问题。
