A Quantum Approach to Complex Networks’ Structure

When: Friday, October 12, 2012 at 4:30 pm
Where: DA 5th fl
Speaker: Silvano Garnerone, PhD
Organization: University of Waterloo, Canada
Sponsor: CCNR

I will discuss two recent works about the application of quantum information tools in the context of complex networks. In the first part of the talk I will present a quantum algorithm generating a quantum state encoding of the PageRank vector. Extensive numerical simulations provide evidences that this algorithm can prepare the quantum PageRank state in a time which typically scales polylogarithmically in the number of web pages, allowing for a polynomial quantum speed-up in the estimation of the most important entries of the PageRank.  We argue that the main topological feature of the underlying web graph allowing for such a scaling is the out-degree distribution. [This part is based on Phys. Rev. Lett. 108, 230506 (2012)].

In the second part of the talk I will consider quantum walks on directed graphs. Using a large deviation approach I show how to construct a thermodynamic formalism allowing us to define a dynamical order parameter, and to identify transitions between dynamical regimes. For a particular class of dissipative quantum walks I propose a new quantum generalization of the classical pagerank vector. [This part is based on arXiv:1205.5744].

Host: Assistant Professor Ginestra Bianconi