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

Luca Rossi, Andrea Torsello, Edwin R. Hancock

Research output: Journal article publicationJournal articleAcademic researchpeer-review

32 Citations (Scopus)

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.

Original languageEnglish
Article number022815
JournalPhysical Review E - Statistical, Nonlinear, and Soft Matter Physics
Volume91
Issue number2
DOIs
Publication statusPublished - 23 Feb 2015
Externally publishedYes

ASJC Scopus subject areas

  • Statistical and Nonlinear Physics
  • Statistics and Probability
  • Condensed Matter Physics

Fingerprint

Dive into the research topics of 'Measuring graph similarity through continuous-time quantum walks and the quantum Jensen-Shannon divergence'. Together they form a unique fingerprint.

Cite this