Quantum centrality testing on directed graphs via PT-symmetric quantum walks
arXiv:1607.02673 · doi:10.1103/PhysRevA.96.032305
Abstract
Various quantum-walk based algorithms have been proposed to analyse and rank the centrality of graph vertices. However, issues arise when working with directed graphs --- the resulting non-Hermitian Hamiltonian leads to non-unitary dynamics, and the total probability of the quantum walker is no longer conserved. In this paper, we discuss a method for simulating directed graphs using PT-symmetric quantum walks, allowing probability conserving non-unitary evolution. This method is equivalent to mapping the directed graph to an undirected, yet weighted, complete graph over the same vertex set, and can be extended to cover interdependent networks of directed graphs. Previous work has shown centrality measures based on the CTQW provide an eigenvector-like quantum centrality; using the PT-symmetric framework, we extend these centrality algorithms to directed graphs with a significantly reduced Hilbert space compared to previous proposals. In certain cases, this centrality measure provides an advantage over classical algorithms used in network analysis, for example by breaking vertex rank degeneracy. Finally, we perform a statistical analysis over ensembles of random graphs, and show strong agreement with the classical PageRank measure on directed acyclic graphs.
References in corpus (39)
- Emergence of scaling in random networks
- Statistical mechanics of complex networks
- Real Spectra in Non-Hermitian Hamiltonians Having PT Symmetry
- Nonreciprocal light transmission in parity-time-symmetric whispering-gallery microcavities
- Pseudo-Hermiticity versus PT Symmetry: The necessary condition for the reality of the spectrum of a non-Hermitian Hamiltonian
- Self-similarity of complex networks
- Environment-Assisted Quantum Walks in Photosynthetic Energy Transfer
- Universal computation by quantum walk
- Pseudo-Hermiticity versus PT-Symmetry II: A complete characterizatio n of non-Hermitian Hamiltonians with a real spectrum
- Exponential algorithmic speedup by quantum walk
- Environment-Assisted Quantum Transport
- Pseudo-Hermiticity versus PT-Symmetry III: Equivalence of pseudo-Her miticity and the presence of antilinear symmetries
- Spatial search by quantum walk
- Quantum entanglement in photosynthetic light harvesting complexes
- Universal computation by multi-particle quantum walk
- Localization and centrality in networks
- Ranking the spreading influence in complex networks
- Understanding the spreading power of all nodes in a network: a continuous-time perspective
- Spectral centrality measures in complex networks
- A family of complex potentials with real spectrum
- Pseudo Parity-Time Symmetry in Optical Systems
- Dual PT-Symmetric Quantum Field Theories
- Distinct types of eigenvector localization in networks
- Time evolution of non-Hermitian Hamiltonian systems
- Classical approach to the graph isomorphism problem using quantum walks
- PT symmetry and necessary and sufficient conditions for the reality of energy eigenvalues
- Weak pseudo-Hermiticity and antilinear commutant
- Quantum Google in a Complex Network
- Explicit definition of symmetry for non-unitary quantum walks with gain and loss
- Quantum walk-based search and centrality
- Centrality measure based on continuous-time quantum walks and experimental realization
- On the pseudo-Hermitian nondiagonalizable Hamiltonians
- Exact solution of Calogero model with competing long-range interactions
- Open Quantum Walks: a short introduction
- PT-symmetry and its spontaneous breakdown explained by anti-linearity
- Comparing algorithms for graph isomorphism using discrete- and continuous-time quantum random walks
- A possible method for non-Hermitian and non--symmetric Hamiltonian systems
- Pseudo-Hermitian continuous-time quantum walks
- A 'Dysonization' Scheme for Identifying Particles and Quasi-Particles Using Non-Hermitian Quantum Mechanics
Cited by in corpus (5)
- Review on Quantum Walk Computing: Theory, Implementation, and Application
- Combinatorial optimisation via highly efficient quantum walks
- Experimental parity-time symmetry quantum walks on a directed graph
- Quantum hub and authority centrality measures for directed networks based on continuous-time quantum walks
- Universal scaling hypothesis of quantum spatial search in complex networks