By the same authors

From the same journal

From the same journal

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

Research output: Contribution to journalArticle

Full text download(s)

  • main

    367 KB, PDF-document

Published copy (DOI)



Publication details

Journal Physical Review E
DatePublished - 23 Feb 2015
Issue number2
Original languageEnglish


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.

Bibliographical note

© 2015, American Physical Society. This is an author-produced version of the published paper. Uploaded in accordance with the publisher’s self-archiving policy. Further copying may not be permitted; contact the publisher for details

Discover related content

Find related publications, people, projects, datasets and more using interactive charts.

View graph of relations