Quantum evolution kernel: Machine learning on graphs with programmable arrays of qubits

The rapid development of reliable quantum processing units opens up novel computational opportunities for machine learning. Here, we introduce a procedure for measuring the similarity between graph-structured data, based on the time evolution of a quantum system. By encoding the topology of the input graph in the Hamiltonian of the system, the evolution produces measurement samples that retain key features of the data. We study analytically the procedure and illustrate its versatility in providing links to standard classical approaches. We then show numerically that this scheme performs well compared to standard graph kernels on typical benchmark datasets. Finally, we study the possibility of a concrete implementation on a realistic neutral-atom quantum processor.

Figure 1

Schematics of the feature map at the heart of the QE kernel. One first encodes an input graph $\mathcal{G}$ into a Hamiltonian ${\widehat{\mathcal{H}}}_{\mathcal{G}}$, which is used in a parametrized sequence, alternating evolution with ${\widehat{\mathcal{H}}}_{\mathcal{G}}$ and pulses with Hamiltonian ${\widehat{\mathcal{H}}}_{{\theta }_i}$. An observable is measured at the end of the pulse sequence, yielding a bit string. From this bit string (or a list of bit strings resulting from repeated iterations of this pulse sequence), a probability distribution ${\mathcal{P}}_{\mathrm{\Lambda }}\left(\mathcal{G}\right)$ is extracted, out of which the graph kernel is computed, as a distance $\mathrm{\Delta }$ on probability distributions. The precise form of the pulse sequence is determined through training on a graph dataset

Figure 2

Illustration of the Ising QE kernel at depth $p=1$, for eight random Erdős-Renyi graphs of $N=60$ nodes, with edge probability, respectively, $\rho =0.35$ (${\mathcal{G}}_0,...,{\mathcal{G}}_3$) and $\rho =0.65$ (${\mathcal{G}}_4,...,{\mathcal{G}}_7$), and $\vartheta =\pi /4$. (a) One period of the time dependence of the density as expressed in (20); the color of each graph is the same as the corresponding plot. (b) Probability distribution extracted from this procedure. The lines are the Fourier transform of $n_{\theta }\left(t\right)$ (with a finite value of the total time $T$), while the dots are given by (22). Two types of distributions are clearly emerging, corresponding to the two classes of graphs. (c) The Jensen-Shannon divergence computed from $p_k$. The color represents the value of the Jensen-Shannon divergence between the two corresponding graphs (it is 0 on the diagonal, by definition). Bright colors correspond to similar graphs, while darker (red) colors correspond to larger values of the divergence (and therefore dissimilar graphs). This nicely groups the graphs of the same class.

Figure 3

The sequence of occupation graphs ${\mathcal{G}}_n$ from a loop (top row) and random (bottom row) initial graph $\mathcal{G}\equiv {\mathcal{G}}_1$. As the occupation is increased, both the number of vertices and the number of edges grow exponentially. In the case of the periodic chain, the ${\mathcal{G}}_n$'s retain the rotational or permutation symmetry of $\mathcal{G}$

Figure 4

Implementation of quantum spin models with neutral atoms. (a) In the Ising case, the spin states $|0\rangle$ and $|1\rangle$ correspond to a ground state $|g\rangle$ and a Rydberg state $|r\rangle$ of the atom. The amplitude $\mathrm{\Omega }$ of the pumping laser determines the transverse-field term in the Ising model, and the detuning to resonance $\delta$ induces a longitudinal-field term. (b) In the XY case, the spin states correspond to two dipolar Rydberg states $|nP\rangle$ and $|nD\rangle$. The atoms are first brought from a ground state $|g\rangle$ to $|nD\rangle$. A microwave driving between $|nP\rangle$ and $|nD\rangle$ can additionally generate tunable ${\sigma }^x$ and ${\sigma }^z$ terms.

Figure 5

(a) Accuracy of the quantum graph kernel, in the case of the Ising Graph Hamiltonian, with $p=2$ layers, as a function of the number of bayesian optimization, with a false positive and false negative detection error of $\epsilon =0.05$ and ${\epsilon }^{\prime }=0.05$ respectively. The blue (dark) curve is the accuracy obtained from the parameters set at each iteration, while the orange (light) curve represents the best accuracy obtained up to each iteration. After $\sim 20$ iterations, the accuracy of the kernel goes from $\sim .55$ to $\sim .64$, its maximal value reached in this case. Further iterations don't lead to any improvement. (b) The corresponding values of the parameters $\mathrm{\Lambda }$ of the pulse. Faint lines are the values at each iteration while the solid lines are the values reaching the best accuracy. The values keep fluctuating, suggesting that it may be possible to further train the kernel. (c) Optimal amplitude $\mathrm{\Omega }$ of the pulse sequence obtained after training on Fingerprint*.

Figure 6

Cumulative distribution of the relative change of the values of the kernel in the presence of detection error (set to $\epsilon ={\epsilon }^{\prime }=.05$), as defined in (34) (note the logarithmic scale of the y axis). The average is performed over 100 estimations of the set of feature vectors, with each one estimated with 10 000 measurements. The dashed vertical lines represent the 0.5, 0.9, and 0.999 quantiles.

Figure 7

Accuracy obtained after multiple kernel learning as a function of the number of individual kernels. Each panel corresponds to a different dataset. In each one, the solid curves are obtained by combining either the $R$ best-performing kernels in the Ising ($XY$) scheme, or $R$ random kernels in the Ising ($XY$) scheme. For each of these curves, a dotted line of the same color and symbol represents the accuracy of the best-performing kernel among the ones that are combined.