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

Rossi, Luca, Torsello, Andrea and Hancock, Edwin R. (2015). Measuring graph similarity through continuous-time quantum walks and the quantum Jensen-Shannon divergence. Physical Review E, 91 (2),

Abstract

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: https://doi.org/10.1103/PhysRevE.91.022815
Divisions: Engineering & Applied Sciences
Engineering & Applied Sciences > Systems analytics research institute (SARI)
Additional Information: 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)
Published Date: 2015-02
Authors: Rossi, Luca ( 0000-0002-6116-9761)
Torsello, Andrea
Hancock, Edwin R.

Export / Share Citation


Statistics

Additional statistics for this record