Can a quantumwalk tell which is which? A study of quantum walk-based graph similarity

Giorgia Minello, Luca Rossi, Andrea Torsello

Research output: Journal article publicationJournal articleAcademic researchpeer-review

11 Citations (Scopus)


We consider the problem of measuring the similarity between two graphs using continuous-time quantum walks and comparing their time-evolution by means of the quantum Jensen-Shannon divergence. Contrary to previous works that focused solely on undirected graphs, here we consider the case of both directed and undirected graphs. We also consider the use of alternative Hamiltonians as well as the possibility of integrating additional node-level topological information into the proposed framework. We set up a graph classification task and we provide empirical evidence that: (1) our similarity measure can effectively incorporate the edge directionality information, leading to a significant improvement in classification accuracy; (2) the choice of the quantum walk Hamiltonian does not have a significant effect on the classification accuracy; (3) the addition of node-level topological information improves the classification accuracy in some but not all cases. We also theoretically prove that under certain constraints, the proposed similarity measure is positive definite and thus a valid kernel measure. Finally, we describe a fully quantum procedure to compute the kernel.

Original languageEnglish
Article number328
Pages (from-to)1-17
Issue number3
Publication statusPublished - 1 Mar 2019
Externally publishedYes


  • Directed graphs
  • Graph kernels
  • Graph similarity
  • Quantum walks

ASJC Scopus subject areas

  • General Physics and Astronomy


Dive into the research topics of 'Can a quantumwalk tell which is which? A study of quantum walk-based graph similarity'. Together they form a unique fingerprint.

Cite this