Quantum centrality testing on directed graphs via PT-symmetric quantum walks

J. A. Izaac, J. B. Wang, P. C. Abbott, and X. S. Ma
Phys. Rev. A 96, 032305 – Published 5 September 2017

Abstract

Various quantum-walk-based algorithms have been proposed to analyze and rank the centrality of graph vertices. However, issues arise when working with directed graphs: the resulting non-Hermitian Hamiltonian leads to nonunitary 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 nonunitary 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 continuous-time quantum walk provide an eigenvectorlike 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.

  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
7 More
  • Received 21 June 2016
  • Revised 24 July 2017

DOI:https://doi.org/10.1103/PhysRevA.96.032305

©2017 American Physical Society

Physics Subject Headings (PhySH)

Quantum Information, Science & Technology

Authors & Affiliations

J. A. Izaac1,*, J. B. Wang1,†, P. C. Abbott1, and X. S. Ma2

  • 1School of Physics, The University of Western Australia, Perth, Western Australia 6009, Australia
  • 2School of Physics, Collaborative Innovation Center of Advanced Microstructures, Nanjing University, Nanjing 210093, China

  • *josh.izaac@uwa.edu.au
  • jingbo.wang@uwa.edu.au

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 96, Iss. 3 — September 2017

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review A

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×