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.

Figure 1

Given two graphs $G_1(V_1,E_1)$ and $G_2(V_2,E_2)$ we construct a new graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ where $\mathcal{V}=V_1\cup V_2,\mathcal{E}=E_1\cup E_2$, and we add a new edge $(u,v)$ between each pair of nodes $u\in V_1$ and $v\in V_2$.

Figure 2

Two-dimensional MDS embeddings of the synthetic data, where the elements of the three classes are indicated by blue circles, red up triangles, and green down triangles, respectively. Here the axes correspond to the embedding dimensions given by the two largest eigenvalues of the similarity matrix $M=-\frac{1}{2}HDH$, where the distance matrix $D$ denotes (a) the edit distance, (b) the distance between the graph spectra, and (c) the QJSD kernel, respectively.

Figure 3

The average classification accuracy ($\pm$ standard error, dashed line) as a function of the stopping time $T$. Here the dark gray and light gray lines refer to the cases in which the Hamiltonians are the adjacency and Laplacian matrix, respectively, and the horizontal line shows the classification accuracy when $T\to \infty$.