Measuring graph similarity through continuous-time quantum walks and the quantum Jensen-Shannon divergence


In this paper we propose a quantum algorithm to measure the similarity between a pair of unattributed graphs. We design an experiment where the two graphs are merged by establishing a complete set of connections between their nodes and the resulting structure is probed through the evolution of continuous-time quantum walks. In order to analyze the behavior of the walks without causing wave function collapse, we base our analysis on the recently introduced quantum Jensen-Shannon divergence. In particular, we show that the divergence between the evolution of two suitably initialized quantum walks over this structure is maximum when the original pair of graphs is isomorphic. We also prove that under special conditions the divergence is minimum when the sets of eigenvalues of the Hamiltonians associated with the two original graphs have an empty intersection.

Publication DOI:
Divisions: College of Engineering & Physical Sciences
College of Engineering & Physical Sciences > Systems analytics research institute (SARI)
Additional Information: ©2015 American Physical Society Funding: UK’s Royal Society (ref: WRMA09R2/HLL)
Uncontrolled Keywords: Condensed Matter Physics,Statistical and Nonlinear Physics,Statistics and Probability
Full Text Link: http://eprints. ... 6512/1/main.pdf
Related URLs: http://www.scop ... tnerID=8YFLogxK (Scopus URL)
PURE Output Type: Article
Published Date: 2015-02
Authors: Rossi, Luca (ORCID Profile 0000-0002-6116-9761)
Torsello, Andrea
Hancock, Edwin R.



Version: Published Version

| Preview

Export / Share Citation


Additional statistics for this record