Seminari del Dipartimento di Matematica

Seminario del 2023

Paola Boito, Dipartimento di Matematica, Università di Pisa

Centrality measures for directed networks via continuous-time quantum walks

nell'ambito della serie: SEMINARI MAT/08 TEAM

analisi numerica

The widespread interest in quantum computation has motivated (among others) applications to network analysis, where quantum advantage may turn out to be especially beneficial for the treatment of large-scale problems. In the past years, several authors have proposed the use of quantum walks - as opposed to classical random walks - in the definition and analysis of centrality measures for graphs, which in turn are the basis for ranking algorithms. Here we focus on unitary continuous-time quantum walks (CTQW) applied to directed graphs and propose new quantum algorithms for hub and authority ranking of the nodes. In particular we explore - the choice of Hamiltonian operator that defines the time evolution of a CTQW, - the choice of the initial state of the system (which turns out to have a non-negligible effect on the final ranking), and perform numerical comparisons with well-known classical ranking algorithms such as HITS and PageRank.