BEGIN:VCALENDAR VERSION:2.0 PRODID:-//linuxsoftware.nz//NONSGML Joyous v1.4//EN BEGIN:VEVENT SUMMARY:Quantum Walk Methods for Link Prediction in Complex Networks DTSTART:20230713T140000Z DTEND:20230713T160000Z DTSTAMP:20260623T171301Z UID:ed8ec14d-61a1-46aa-a032-b57c04e389e6 SEQUENCE:1 CREATED:20230712T081512Z DESCRIPTION: Abstract: The problem of link prediction is to identify missi ng or future connections in a complex network through the structural patte rns that emerge in their topology. A common approach uses path structures between nodes\, quantifying direct and neighbouring node similarities thro ugh a scoring function. Computing the scoring function for every possible node combination can be computationally hard. We design a quantum link pre diction algorithm based on continuous-time quantum walks (CTQW)\, showing that is encodes a scoring function similar to classical path-based link pr edictions methods. A CTQW is a simple model for quantum dynamics and quant um computation on a graph. Finding applications of quantum computing in co mplex networks can help speedup network science problems. We further impro ve our algorithm and describe a sampling-based framework for link predicti on. We use a oracle-query access model to the input network and show that the complexity of implementing our quantum algorithm is limited by perform ing quantum simulation of the network’s adjacency matrix. Considering th e 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 quant um speedup compared to classical sampling algorithms for a fixed number of samples. Despite this speedup\, the quantum simulation of d-sparse matric es is not efficient for complex networks due to the existence of some node s that are densely connected. As a first step towards the efficient quantu m simulation of complex networks\, we show that a toy network model with m ostly sparsely connected nodes and a few densely connected ones can be eff iciently simulated. Performing efficient quantum simulation of complex net works could be an important routine for quantum algorithms applied to netw ork science problems in general. Furthermore\, in a different research dir ection\, we explore how quantum dynamics may be used for eneregy-efficient classical computation. We design a 1-bit full adder operating with a quan tum representation of classical bits using electrons confined in quantum d ots\, and discuss how the energetic costs of computation could potentially be reduced. In our estimates we find that the energetic cost of cooling w ould be the main bottleneck of this technology. LAST-MODIFIED:20230712T081512Z LOCATION:Online URL:http://df.vps.tecnico.ulisboa.pt/pt/eventos/quantum-walk-methods-for-l ink-prediction-in-complex-networks/ X-ALT-DESC;FMTTYPE=text/html:

Abstract: < /p>

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 struc tures between nodes\, quantifying direct and neighbouring node similaritie s through a scoring function. Computing the scoring function for every pos sible 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 pa th-based link predictions methods. A CTQW is a simple model for quantum dy namics 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 f ramework for link prediction. We use a oracle-query access model to the in put network and show that the complexity of implementing our quantum algor ithm is limited by performing quantum simulation of the network’s adjace ncy matrix. Considering the quantum simulation of d-sparse matrices\, wher e d is the maximum number of entries in any row or column\, we show that t here is a polynomial quantum speedup compared to classical sampling algori thms for a fixed number of samples.

Despite this speedup\, the q uantum simulation of d-sparse matrices is not efficient for complex networ ks due to the existence of some nodes that are densely connected. As a fir st step towards the efficient quantum simulation of complex networks\, we show that a toy network model with mostly sparsely connected nodes and a f ew densely connected ones can be efficiently simulated. Performing efficie nt quantum simulation of complex networks could be an important routine fo r quantum algorithms applied to network science problems in general.
< br/> Furthermore\, in a different research direction\, we explore how quan tum dynamics may be used for eneregy-efficient classical computation. We d esign a 1-bit full adder operating with a quantum representation of classi cal bits using electrons confined in quantum dots\, and discuss how the en ergetic costs of computation could potentially be reduced. In our estimate s we find that the energetic cost of cooling would be the main bottleneck of this technology.

END:VEVENT END:VCALENDAR