Measuring the similarity of graphs with a Gaussian boson sampler

Gaussian boson samplers (GBSs) have initially been proposed as a near-term demonstration of classically intractable quantum computation. We show here that they have a potential practical application: Samples from these devices can be used to construct a feature vector that embeds a graph in Euclidean space, where similarity measures between graphs-so-called graph kernels-can be naturally defined. This is crucial for machine learning with graph-structured data, and we show that the GBS-induced kernel performs remarkably well in classification benchmark tasks. We provide a theoretical motivation for this success, linking the extracted features to the number of r matchings in subgraphs. Our results contribute to a new way of thinking about kernels as a quantum hardware-efficient feature mapping, and lead to a promising application for near-term quantum computing.