In many fields, such as chemistry, bioinformatics, social network analysis and computer vision, key information is encoded in terms of graphs. Thus, a large body of work in classical machine learning has been devoted to studying relationships between graphs, also known as graph kernels. The graph kernel approach is based on finding a way to associate any graph with a feature vector encapsulating its relevant characteristics (the feature map) and then computing the similarity between those vectors, e.g., via scalar products in the feature space. Despite some interesting results in recent years, the algorithmic complexity of the most valuable kernels makes them difficult to apply in the case of large graphs.
A versatile and easily scalable graph kernel method known as the Quantum Evolution Kernel (QEK) was introduced by PASQAL in 2021. The central idea of this method is to encode information about the graph in terms of the parameters of a Hamiltonian acting on an array of qubits, and defining the kernel as overlap between output states (or their properties) produced by two different graph cases; with quantum computer’s ability to efficiently produce complex output states and compute wavefunction overlaps naturally, this poses a potential advantage over known classical methods.
While QEK was specifically applied to classification and regression tasks, it could also be used for clustering and as subroutine in other algorithms. Furthermore, there are many parallels to Graph Neural Networks due to the kernel-neural network correspondence, opening up the potential to apply QEK-like algorithm paradigms also to more general graph learning problems.