Centrality measure based on continuous-time quantum walks and experimental realization
arXiv:1702.03493 · doi:10.1103/PhysRevA.95.032318
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 (30)
- Emergence of scaling in random networks
- Statistical mechanics of complex networks
- Self-similarity of complex networks
- Quantum random walks - an introductory overview
- Quantum Computation and Decision Trees
- Universal computation by quantum walk
- Quantum walks: a comprehensive review
- Exponential algorithmic speedup by quantum walk
- Environment-Assisted Quantum Transport
- Spatial search by quantum walk
- Quantum entanglement in photosynthetic light harvesting complexes
- Universal quantum computation using the discrete time quantum walk
- Universal computation by multi-particle quantum walk
- On the relationship between continuous- and discrete-time quantum walk
- Hamiltonian simulation with nearly optimal dependence on all parameters
- Ranking the spreading influence in complex networks
- Understanding the spreading power of all nodes in a network: a continuous-time perspective
- Connecting the discrete and continuous-time quantum walks
- Quantum stochastic walks: A generalization of classical random walks and quantum walks
- Google in a Quantum Network
- Classical approach to the graph isomorphism problem using quantum walks
- Efficient Quantum Walk on a Quantum Processor
- Quantum Google in a Complex Network
- Quantum walk-based search and centrality
- Laplacian versus Adjacency Matrix in Quantum Walk Search
- Realization of arbitrary discrete unitary transformations using spatial and internal modes of light
- Implementation of multidimensional quantum walks using linear optics and classical light
- Open Quantum Walks: a short introduction
- Highly noise resistant multipartite quantum correlations
- Seeded PageRank Solution Paths
Cited by in corpus (18)
- The prospects of quantum computing in computational molecular biology
- Observation of critical phenomena in parity-time-symmetric quantum dynamics
- Review on Quantum Walk Computing: Theory, Implementation, and Application
- A quantum walk assisted approximate algorithm for bounded NP optimisation problems
- Higher winding number in a non-unitary photonic quantum walk
- Complex Quantum Networks: a Topical Review
- From classical to quantum walks with stochastic resetting on networks
- Experimental parity-time symmetry quantum walks on a directed graph
- Experimental realization of a quantum image classifier via tensor-network-based machine learning
- Classical and quantum random-walk centrality measures in multilayer networks
- Quantum centrality testing on directed graphs via PT-symmetric quantum walks
- Continuous-time quantum walks for MAX-CUT are hot
- Quantum hub and authority centrality measures for directed networks based on continuous-time quantum walks
- Discrete-Time Open Quantum Walks for Vertex Ranking in Graphs
- Quantum walk on a chimera graph
- On the physical realizability of quantum stochastic walks
- Scoring Anomalous Vertices Through Quantum Walks
- Clustering-induced localization of quantum walks on networks