Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Physical Review A

Quantum kernel method for learning graph data via quantum walk

Linyun Cao, Youle Wang

Published Sep 3, 2025• 3 citations
Publisher

Abstract

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({M}^{3/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(\text{poly}log(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.

DOI
10.1103/k2nx-d649

Related papers

Quantum-Inspired Kernel Learning for Sparse Data

Jincheng Zhang

Kernel methods have demonstrated remarkable success in various machine learning tasks, including classification and regression. However, a significant limitation of traditional kernel methods lies in their computational complexity, particularly when dealing with sparse datasets. The need to construct and invert dense kernel matrices, denoted as $K$, where $K_{ij} = k(s_i, s_j)$ with kernel function $k$, leads to a quadratic scaling problem, rendering these methods impractical for datasets with a large number of features or data points. This paper introduces a novel kernel learning algorithm, termed Quantum-Inspired Kernel Learning (QIKL), which addresses this challenge by mimicking quantum interference. QIKL leverages the inherent correlations within sparse datasets to efficiently learn kernel functions without explicitly constructing dense kernel matrices. The algorithm employs a probabilistic approach, represented by a set of quantum-inspired amplitudes, $(a_1, a_2, ..., a_K)$, where $K \approx \sum_{i=1}^{K} a_i^2$, to approximate the kernel matrix. The core idea is to utilize the interference patterns generated by these amplitudes to capture the relationships between data points. This approach significantly reduces the computational cost and memory requirements, making kernel methods viable for sparse data scenarios. We demonstrate the effectiveness of QIKL through theoretical analysis and a simplified numerical example, highlighting its potential for scaling to large-scale sparse data problems.

•Sep 3, 2026•0 citations

A Resource Efficient Quantum Kernel

Utkarsh Singh, Jean‐Frédéric Laprade, Aaron Z. Goldberg +1 more

Quantum processors may enhance machine learning by mapping high-dimensional data onto quantum systems for processing. Conventional feature maps, for encoding data onto a quantum circuit are currently impractical, as the number of entangling gates scales quadratically with the dimension of the dataset and the number of qubits. In this work, we introduce a quantum feature map designed to handle high-dimensional data with a significantly reduced number of qubits and entangling operations. Our approach preserves essential data characteristics while promoting computational efficiency, as evidenced by extensive experiments on benchmark datasets that demonstrate a marked improvement in both accuracy and resource utilization when using our feature map as a kernel for characterization, as compared to state-of-the-art quantum feature maps. Our noisy simulation results, combined with lower resource requirements, highlight our map's ability to function within the constraints of noisy intermediate-scale quantum devices. Through numerical simulations and small-scale implementation on a superconducting circuit quantum computing platform, we demonstrate that our scheme performs on par or better than a set of classical algorithms for classification. While quantum kernels are typically stymied by exponential concentration, our approach is affected with a slower rate with respect to both the number of qubits and features, which allows practical applications to remain within reach. Our findings herald a promising avenue for the practical implementation of quantum machine learning algorithms on near future quantum computing platforms.

arXiv:2507.03689•Jul 4, 2025•0 citations

A Versatile Variational Quantum Kernel Framework for Non-Trivial Classification

Jiang Yuhan, Matthew Otten

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.

cs.LGCross-listedarXiv:2511.10831•Nov 17, 2025•0 citations

Near-optimal quantum kernel principal component analysis

Youle Wang

Abstract Kernel principal component analysis (kernel PCA) is a nonlinear dimensionality reduction technique that employs kernel functions to map data into a high-dimensional feature space, thereby extending the applicability of linear PCA to nonlinear data and facilitating the extraction of informative principal components. However, kernel PCA necessitates the manipulation of large-scale matrices, leading to high computational complexity and posing challenges for efficient implementation in big data environments. Quantum computing has recently been integrated with kernel methods in machine learning, enabling effective analysis of input data within intractable feature spaces. Although existing quantum kernel PCA proposals promise exponential speedups, they impose stringent requirements on quantum hardware that are challenging to fulfill. In this work, we propose a quantum algorithm for kernel PCA by establishing a connection between quantum kernel methods and block encoding, thereby diagonalizing the centralized kernel matrix on a quantum computer. The query complexity is logarithmic with respect to the size of the data vector, D , and linear with respect to the size of the dataset. An exponential speedup could be achieved when the dataset consists of a few high-dimensional vectors, wherein the dataset size is polynomial in log ⁡ ( D ) , with D being significantly large. In contrast to existing work, our algorithm enhances the efficiency of quantum kernel PCA and reduces the requirements for quantum hardware. Furthermore, we have also demonstrated that the algorithm based on block encoding matches the lower bound of query complexity, indicating that our algorithm is nearly optimal. Our research has laid down new pathways for developing quantum machine learning algorithms aimed at addressing tangible real-world problems and demonstrating quantum advantages within machine learning.

Quantum Science and Technology•Nov 12, 2024•6 citations

Quantum-Inspired Kernel Methods for Kernel Matrix Computation

Jincheng Zhang

Kernel matrix computation lies at the heart of numerous machine learning algorithms, particularly those employing kernel methods like Support Vector Machines (SVMs) and Gaussian Processes. However, the computational complexity of calculating these matrices, scaling quadratically with the number of data points (O(n²)), presents a significant bottleneck, especially for large datasets. This paper proposes a novel approach to kernel matrix computation inspired by quantum algorithms, specifically utilizing concepts from quantum annealing and adiabatic quantum computation. We introduce a heuristic algorithm that mimics the iterative process of quantum annealing to approximate the kernel matrix. The algorithm employs a belief propagation-like strategy, iteratively refining estimates of the kernel elements based on local interactions, aiming to converge towards the true kernel matrix. We demonstrate that this quantum-inspired method can achieve significant reductions in computational time compared to traditional methods, particularly for high-dimensional datasets. The theoretical analysis suggests a convergence rate dependent on the problem's structure and the annealing schedule. We provide a detailed mathematical framework for the algorithm and discuss its limitations and potential extensions. The key contribution is a practical and computationally efficient method for approximating kernel matrix computation, paving the way for the wider adoption of kernel methods in resource-constrained environments.

•Aug 31, 2026•0 citations

Adaptive Quantum Kernel Learning

Jincheng Zhang

This paper proposes a novel adaptive quantum kernel learning framework designed to overcome the limitations of classical kernel methods when applied to quantum state analysis. The core challenge lies in effectively mapping the high-dimensional space of quantum states into a manageable, low-dimensional feature space for traditional kernel-based learning algorithms. Existing methods often fail to capture the intricate correlations inherent in quantum states, leading to suboptimal results. Our approach introduces a self-adaptive kernel learning algorithm that dynamically adjusts the kernel function based on the observed quantum state correlations. This adaptation is achieved through a quantum-inspired optimization process utilizing variational quantum circuits. The circuits evolve the kernel parameters, guided by quantum state tomography data, effectively learning a kernel function tailored to the specific quantum system being analyzed. The key innovation is the integration of quantum mechanics directly into the kernel learning process, offering a potentially significant improvement in feature extraction and classification accuracy for quantum data. This work addresses a critical bottleneck in quantum machine learning, paving the way for more powerful and accurate quantum algorithms.

•Sep 2, 2026•0 citations
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)O({M}^{3/2})O(M3/2) with respect to the size of the graph set MMM. This suggests that our quantum kernel method could process graph data with resource requirements scaling approximately as O(polylog(N))O(\text{poly}log(N))O(polylog(N)), where NNN 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.
Kernel methods have demonstrated remarkable success in various machine learning tasks, including classification and regression. However, a significant limitation of traditional kernel methods lies in their computational complexity, particularly when dealing with sparse datasets. The need to construct and invert dense kernel matrices, denoted as KKK, where Kij=k(si,sj)K_{ij} = k(s_i, s_j)Kij​=k(si​,sj​) with kernel function kkk, leads to a quadratic scaling problem, rendering these methods impractical for datasets with a large number of features or data points. This paper introduces a novel kernel learning algorithm, termed Quantum-Inspired Kernel Learning (QIKL), which addresses this challenge by mimicking quantum interference. QIKL leverages the inherent correlations within sparse datasets to efficiently learn kernel functions without explicitly constructing dense kernel matrices. The algorithm employs a probabilistic approach, represented by a set of quantum-inspired amplitudes, (a1,a2,...,aK)(a_1, a_2, ..., a_K)(a1​,a2​,...,aK​), where K≈∑i=1Kai2K \approx \sum_{i=1}^{K} a_i^2K≈∑i=1K​ai2​, to approximate the kernel matrix. The core idea is to utilize the interference patterns generated by these amplitudes to capture the relationships between data points. This approach significantly reduces the computational cost and memory requirements, making kernel methods viable for sparse data scenarios. We demonstrate the effectiveness of QIKL through theoretical analysis and a simplified numerical example, highlighting its potential for scaling to large-scale sparse data problems.
Quantum processors may enhance machine learning by mapping high-dimensional data onto quantum systems for processing. Conventional feature maps, for encoding data onto a quantum circuit are currently impractical, as the number of entangling gates scales quadratically with the dimension of the dataset and the number of qubits. In this work, we introduce a quantum feature map designed to handle high-dimensional data with a significantly reduced number of qubits and entangling operations. Our approach preserves essential data characteristics while promoting computational efficiency, as evidenced by extensive experiments on benchmark datasets that demonstrate a marked improvement in both accuracy and resource utilization when using our feature map as a kernel for characterization, as compared to state-of-the-art quantum feature maps. Our noisy simulation results, combined with lower resource requirements, highlight our map's ability to function within the constraints of noisy intermediate-scale quantum devices. Through numerical simulations and small-scale implementation on a superconducting circuit quantum computing platform, we demonstrate that our scheme performs on par or better than a set of classical algorithms for classification. While quantum kernels are typically stymied by exponential concentration, our approach is affected with a slower rate with respect to both the number of qubits and features, which allows practical applications to remain within reach. Our findings herald a promising avenue for the practical implementation of quantum machine learning algorithms on near future quantum computing platforms.
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.
Abstract Kernel principal component analysis (kernel PCA) is a nonlinear dimensionality reduction technique that employs kernel functions to map data into a high-dimensional feature space, thereby extending the applicability of linear PCA to nonlinear data and facilitating the extraction of informative principal components. However, kernel PCA necessitates the manipulation of large-scale matrices, leading to high computational complexity and posing challenges for efficient implementation in big data environments. Quantum computing has recently been integrated with kernel methods in machine learning, enabling effective analysis of input data within intractable feature spaces. Although existing quantum kernel PCA proposals promise exponential speedups, they impose stringent requirements on quantum hardware that are challenging to fulfill. In this work, we propose a quantum algorithm for kernel PCA by establishing a connection between quantum kernel methods and block encoding, thereby diagonalizing the centralized kernel matrix on a quantum computer. The query complexity is logarithmic with respect to the size of the data vector, D , and linear with respect to the size of the dataset. An exponential speedup could be achieved when the dataset consists of a few high-dimensional vectors, wherein the dataset size is polynomial in log ⁡ ( D ) , with D being significantly large. In contrast to existing work, our algorithm enhances the efficiency of quantum kernel PCA and reduces the requirements for quantum hardware. Furthermore, we have also demonstrated that the algorithm based on block encoding matches the lower bound of query complexity, indicating that our algorithm is nearly optimal. Our research has laid down new pathways for developing quantum machine learning algorithms aimed at addressing tangible real-world problems and demonstrating quantum advantages within machine learning.
Kernel matrix computation lies at the heart of numerous machine learning algorithms, particularly those employing kernel methods like Support Vector Machines (SVMs) and Gaussian Processes. However, the computational complexity of calculating these matrices, scaling quadratically with the number of data points (O(n²)), presents a significant bottleneck, especially for large datasets. This paper proposes a novel approach to kernel matrix computation inspired by quantum algorithms, specifically utilizing concepts from quantum annealing and adiabatic quantum computation. We introduce a heuristic algorithm that mimics the iterative process of quantum annealing to approximate the kernel matrix. The algorithm employs a belief propagation-like strategy, iteratively refining estimates of the kernel elements based on local interactions, aiming to converge towards the true kernel matrix. We demonstrate that this quantum-inspired method can achieve significant reductions in computational time compared to traditional methods, particularly for high-dimensional datasets. The theoretical analysis suggests a convergence rate dependent on the problem's structure and the annealing schedule. We provide a detailed mathematical framework for the algorithm and discuss its limitations and potential extensions. The key contribution is a practical and computationally efficient method for approximating kernel matrix computation, paving the way for the wider adoption of kernel methods in resource-constrained environments.
This paper proposes a novel adaptive quantum kernel learning framework designed to overcome the limitations of classical kernel methods when applied to quantum state analysis. The core challenge lies in effectively mapping the high-dimensional space of quantum states into a manageable, low-dimensional feature space for traditional kernel-based learning algorithms. Existing methods often fail to capture the intricate correlations inherent in quantum states, leading to suboptimal results. Our approach introduces a self-adaptive kernel learning algorithm that dynamically adjusts the kernel function based on the observed quantum state correlations. This adaptation is achieved through a quantum-inspired optimization process utilizing variational quantum circuits. The circuits evolve the kernel parameters, guided by quantum state tomography data, effectively learning a kernel function tailored to the specific quantum system being analyzed. The key innovation is the integration of quantum mechanics directly into the kernel learning process, offering a potentially significant improvement in feature extraction and classification accuracy for quantum data. This work addresses a critical bottleneck in quantum machine learning, paving the way for more powerful and accurate quantum algorithms.