Measuring the similarity of graphs with a Gaussian boson sampler
Maria Schuld, Kamil Brádler, Robert J. Israel, Daiqin Su, Brajesh Gupt
Abstract
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.