Centrality measure based on continuous-time quantum walks and experimental realization

Abstract

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ős-Rényi networks. As a proof of concept, the algorithm is detailed on a 4-vertex star graph and physically implemented via linear optics, using spatial and polarization degrees of freedoms of single photons. This paper reports the first successful physical demonstration of a quantum centrality algorithm.

To appear in Physical Review A

References in corpus (8)

• Universal computation by quantum walk
• Exponential algorithmic speedup by quantum walk
• Environment-Assisted Quantum Transport
• Spatial search by quantum walk
• Universal computation by multi-particle quantum walk
• Ranking the spreading influence in complex networks
• Connecting the discrete and continuous-time quantum walks
• Classical approach to the graph isomorphism problem using quantum walks