Quantum walk based algorithm on scale free networks

Stefan Boettcher, Stefan Falkner, Renato Portugal

Josh Izaac, Xiang Zhan, Zhihao Bian +4 more

Network centrality has important implications well beyond its role in physical and information transport analysis; as such, various quantum-walk-based algorithms have been proposed for measuring network vertex centrality. In this work, we propose a continuous-time quantum walk algorithm for determining vertex centrality, and show that it generalizes to arbitrary graphs via a statistical analysis of randomly generated scale-free and Erd\ifmmode \mbox{\H{o}}\else \H{o}\fi{}s-R\'enyi networks. As a proof of concept, the algorithm is detailed on a four-vertex star graph and physically implemented via linear optics, using spatial and polarization degrees of freedoms of single photons. This paper reports a successful physical demonstration of a quantum centrality algorithm.

de Jan Vos

Supriyo Dutta

This article presents a new quantum PageRank algorithm on graphs using discrete-time open quantum walks. Google's PageRank is a widely used algorithm for ranking the web pages on the world wide web in classical computation. From a broader perspective, it is also a fundamental measure for quantifying the importance of vertices in a network. Similarly, the new quantum PageRank also serves to quantify the significance of a network's vertices. In this work, we extend the concept of discrete-time open quantum walk on arbitrary directed and undirected graphs by utilizing the Weyl operators as Kraus operators. This new model of quantum walk is useful for building up the quantum PageRank algorithm, discussed in this article. We compare the classical PageRank and the newly defined quantum PageRank for different types of complex networks, such as the scale-free network, Erdős-Rényi random network, Watts-Strogatz network, spatial network, Zachary Karate club network, GNC, GN, GNR networks, Barabási and Albert network, etc. In addition, we study the convergence of the quantum PageRank process and its dependency on the damping factor α. We observe that this quantum PageRank procedure is faster than many other proposals reported in the literature.

Miklós Sántha

Nisarg Vyas, M. S. Santhanam

Extreme events are the ones for which the magnitude of the event is much larger than its typical values. They have been extensively investigated on classical dynamical and stochastic processes on networks. In this work, in analogy with well-studied extreme events of random walks, the extreme events of quantum walks on regular lattices, a scale-free network, and Erdős-Rényi network are studied. Due to unitary quantum evolution, the quantum walk dynamics usually differs from that of the classical random walks, and hence we expect extreme event properties to be different in classical and quantum settings. In contrast to this expectation, we report that extreme events of phase coherent quantum walks are qualitatively similar to that of classical random walks. We show that this counterintuitive behavior originates from the dominance of nodal fluctuations over internode correlations in disordered network structures. In particular, the occurrence probability for extreme events on scale-free and Erdős-Rényi networks displays a decaying power law with the degree of nodes. That is, the extreme event probability is larger for small degree nodes compared to the hubs on the network, in qualitative agreement with corresponding classical random walk results. Further, it is shown that extreme event probability scales with the threshold used to define extreme events.