Quantum Walk Methods for Link Prediction in Complex Networks

Abstract:

The problem of link prediction is to identify missing or future connections in a complex network through the structural patterns that emerge in their topology. A common approach uses path structures between nodes, quantifying direct and neighbouring node similarities through a scoring function. Computing the scoring function for every possible node combination can be computationally hard.

We design a quantum link prediction algorithm based on continuous-time quantum walks (CTQW), showing that is encodes a scoring function similar to classical path-based link predictions methods. A CTQW is a simple model for quantum dynamics and quantum computation on a graph. Finding applications of quantum computing in complex networks can help speedup network science problems.

We further improve our algorithm and describe a sampling-based framework for link prediction. We use a oracle-query access model to the input network and show that the complexity of implementing our quantum algorithm is limited by performing quantum simulation of the network’s adjacency matrix. Considering the quantum simulation of d-sparse matrices, where d is the maximum number of entries in any row or column, we show that there is a polynomial quantum speedup compared to classical sampling algorithms for a fixed number of samples.

Despite this speedup, the quantum simulation of d-sparse matrices is not efficient for complex networks due to the existence of some nodes that are densely connected. As a first step towards the efficient quantum simulation of complex networks, we show that a toy network model with mostly sparsely connected nodes and a few densely connected ones can be efficiently simulated. Performing efficient quantum simulation of complex networks could be an important routine for quantum algorithms applied to network science problems in general.

Furthermore, in a different research direction, we explore how quantum dynamics may be used for eneregy-efficient classical computation. We design a 1-bit full adder operating with a quantum representation of classical bits using electrons confined in quantum dots, and discuss how the energetic costs of computation could potentially be reduced. In our estimates we find that the energetic cost of cooling would be the main bottleneck of this technology.