Graph kernels are often used in bioinformatics and network applications to measure the similarity between graphs; therefore, they may be used to construct efficient graph classifiers. Many graph kernels have been developed thus far, but to the best of our knowledge there is no existing graph kernel that uses some features explicitly extracted from all subgraphs to measure similarity. We propose a novel graph kernel that applies a quantum computer to measure the similarity obtained from all subgraphs by fully exploiting the power of quantum superposition to encode every subgraph into a feature of particular form. For the construction of the quantum kernel, we develop an efficient protocol that clears the index information of the subgraphs encoded in the quantum state. We also prove that the quantum computer requires less query complexity to construct the feature vector than the classical sampler used to approximate the same vector. A detailed numerical simulation of a bioinformatics problem is presented to demonstrate that, in many cases, the proposed quantum kernel achieves better classification accuracy than existing graph kernels.
Graph kernels are often used in bioinformatics and network applications to measure the similarity between graphs; therefore, they may be used to construct efficient graph classifiers. Many graph kernels have been developed thus far, but to the best of our knowledge there is no existing graph kernel that uses some features explicitly extracted from all subgraphs to measure similarity. We propose a novel graph kernel that applies a quantum computer to measure the similarity obtained from all subgraphs by fully exploiting the power of quantum superposition to encode every subgraph into a feature of particular form. For the construction of the quantum kernel, we develop an efficient protocol that clears the index information of the subgraphs encoded in the quantum state. We also prove that the quantum computer requires less query complexity to construct the feature vector than the classical sampler used to approximate the same vector. A detailed numerical simulation of a bioinformatics problem is presented to demonstrate that, in many cases, the proposed quantum kernel achieves better classification accuracy than existing graph kernels.
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.
Quantum computing has been a prominent research area for decades, inspiring transformative fields such as quantum simulation, quantum teleportation, and quantum machine learning (QML), which are undergoing rapid development. Within QML, hybrid classical-quantum algorithms like Quantum Neural Networks (QNNs) and Variational Quantum Classifiers (VQCs) have shown promise in leveraging quantum circuits and classical optimizers to classify classical data efficiently. Simultaneously, classical machine learning has made significant strides in graph classification, employing Graph Neural Networks (GNNs) to analyze systems ranging from large-scale structures like the Large Hadron Collider to molecular and biological systems like proteins and DNA. Combining the advancements in quantum computing and graph classification presents a unique opportunity to develop quantum algorithms capable of extracting features from graphs and performing their classification effectively. In this paper, we propose a novel quantum encoding framework for graph classification using VQCs. Unlike existing approaches such as PCA-VQC, which rely on dimensionality reduction techniques like Principal Component Analysis (PCA) and may lead to information loss, our method preserves the integrity of graph data. Furthermore, our encoding approach is optimized for Noise-Intermediate Scale Quantum (NISQ) devices, requiring a limited number of qubits while achieving comparable or superior classification performance to PCA-VQC. By constructing slightly more complex circuits tailored for graph encoding, we demonstrate that VQCs can effectively classify graphs within the constraints of current quantum hardware.
Graph kernels are essential for learning the properties of graph data, a fundamental task in the analysis of such data. However, a major limitation of current graph kernel methods is their high computational cost, which becomes prohibitive when dealing with large-scale graphs. In order to address this bottleneck, we propose a quantum algorithm designed to analyze the intrinsic structural information within graph data through an efficient quantum kernel method. The core idea of our kernel method involves encoding pertinent information from graphs into quantum states, utilizing quantum kernel functions to represent the similarities among various graphs. This process is facilitated through the application of quantum walks and quantum signal processing techniques. Building upon this framework, we propose a quantum kernel ridge regression algorithm that consists of two key steps. First, we employ our quantum kernel method to prepare a quantum state, in which the amplitudes encode the kernel functions. Second, we implement quantum feature mapping in parallel to encode the corresponding kernel matrix into the quantum circuit. Crucially, we demonstrate that the computational complexity of our regression algorithm scales primarily as O(M3/2) with respect to the size of the graph set M. This suggests that our quantum kernel method could process graph data with resource requirements scaling approximately as O(polylog(N)), where N denotes the number of nodes in the graph. Accordingly, this underscores the advantage of our approach over classical methods in the context of large-scale graph analysis. To validate our approach, we conduct numerical experiments on chemical molecular datasets, demonstrating the method's effectiveness and advantages. In summary, this work represents a significant advancement in quantum graph learning, enhancing its potential for analyzing large-scale graph data.
In terms of the logical structure of data in machine learning (ML), we apply a novel graphical encoding method in quantum computing to build the mapping between feature space of sample data and two-level nested graph state that presents a kind of multi-partite entanglement state. By implementing swap-test circuit on the graphical training states, a binary quantum classifier to large-scale test states is effectively realized in this paper. In addition, for the error classification caused by noise, we further explored the subsequent processing scheme by adjusting the weights so that a strong classifier is formed and its accuracy is greatly boosted. In this paper, the proposed boosting algorithm demonstrates superiority in certain aspects as demonstrated via experimental investigation. This work further enriches the theoretical foundation of quantum graph theory and quantum machine learning, which may be exploited to assist the classification of massive-data networks by entangling subgraphs.
Quantum kernel methods are a promising branch of quantum machine learning, but their per- formance across data types and encoding choices remains incompletely understood. To address this gap, we developed an algorithmic framework for variational quantum kernels utilizing resource- efficient ansätze for complex classification tasks and introduced a parameter scaling technique to accelerate convergence. We conducted a comprehensive benchmark of this framework on eight chal- lenging, real-world and high-dimensional datasets covering tabular, image, time series, and graph data. Our results show that the proposed quantum kernel demonstrated competitive classification accuracy compared to standard classical kernels in classical simulation, such as the radial basis function (RBF) kernel. This work demonstrates that properly designed quantum kernels can func- tion as versatile, high-performance tools, laying a foundation for quantum-enhanced applications in machine learning. Further research is needed to fully assess the practical performance of quantum methods.
Quantum and classical machine learning have been naturally connected through kernel methods, which have also served as proof-of-concept for quantum advantage. Quantum embeddings encode classical data into quantum feature states, enabling the construction of embedding quantum kernels (EQKs) by measuring vector similarities and projected quantum kernels (PQKs) through projections of these states. However, in both approaches, the model is influenced by the choice of the embedding. In this work, we propose using the training of a quantum neural network (QNN) to construct neural quantum kernels, specifically neural EQKs and neural PQKs—problem-inspired kernel functions. Unlike previous approaches, our method requires the kernel matrix to be constructed only once, significantly reducing computational overhead. To achieve this, we introduce a scalable training method for an n -qubit data reuploading QNN. Furthermore, we demonstrate neural quantum kernels can alleviate exponential concentration and enhance generalization capabilities compared to problem-agnostic kernels, positioning them as a scalable and robust solution for quantum machine learning applications.