Quantum machine learning with quantum kernels for classification problems is a growing area of research. Recently, quantum kernel alignment techniques that parameterise the kernel have been developed, allowing the kernel to be trained and therefore aligned with a specific dataset. While quantum kernel alignment is a promising technique, it has been hampered by considerable training costs because the full kernel matrix must be constructed at every training iteration. Addressing this challenge, we introduce a novel method that seeks to balance efficiency and performance. We present a sub-sampling training approach that uses a subset of the kernel matrix at each training step, thereby reducing the overall computational cost of the training. In this work, we apply the sub-sampling method to synthetic datasets and a real-world breast cancer dataset and demonstrate considerable reductions in the number of circuits required to train the quantum kernel while maintaining classification accuracy.
Quantum machine learning with quantum kernels for classification problems is a growing area of research. Recently, quantum kernel alignment techniques that parameterise the kernel have been developed, allowing the kernel to be trained and therefore aligned with a specific dataset. While quantum kernel alignment is a promising technique, it has been hampered by considerable training costs because the full kernel matrix must be constructed at every training iteration. Addressing this challenge, we introduce a novel method that seeks to balance efficiency and performance. We present a sub-sampling training approach that uses a subset of the kernel matrix at each training step, thereby reducing the overall computational cost of the training. In this work, we apply the sub-sampling method to synthetic datasets and a real-world breast cancer dataset and demonstrate considerable reductions in the number of circuits required to train the quantum kernel while maintaining classification accuracy.
In recent years, quantum computers have emerged as promising candidates for implementing kernels. Quantum Embedding Kernels embed data points into quantum states and calculate their inner product in a high-dimensional Hilbert Space by computing the overlap between the resulting quantum states. Variational Quantum Circuits (VQCs) are typically used for this end, with Kernel Target Alignment (KTA) as cost function. The optimized kernels can then be deployed in Support Vector Machines (SVMs) for classification tasks. However, both classical and quantum SVMs scale poorly with increasing dataset sizes. This issue is exacerbated in quantum kernel methods, as each inner product requires a quantum circuit execution. In this paper, we investigate KTA-trained quantum embedding kernels and employ a low-rank matrix approximation, the Nyström method, to reduce the quantum circuit executions needed to construct the Kernel Matrix. We empirically evaluate the performance of our approach across various datasets, focusing on the accuracy of the resulting SVM and the reduction in quantum circuit executions. Additionally, we examine and compare the robustness of our model under different noise types, particularly coherent and depolarizing noise.
Kernel methods are a cornerstone of classical machine learning. The idea of using quantum computers to compute kernels has recently attracted attention. Quantum embedding kernels (QEKs), constructed by embedding data into the Hilbert space of a quantum computer, are a particular quantum kernel technique that is particularly suitable for noisy intermediate-scale quantum devices. Unfortunately, kernel methods face three major problems: Constructing the kernel matrix has quadratic computational complexity in the number of training samples, choosing the right kernel function is nontrivial, and the effects of noise are unknown. In this work, we addressed the latter two. In particular, we introduced the notion of trainable QEKs, based on the idea of classical model optimization methods. To train the parameters of the QEK, we proposed the use of kernel-target alignment. We verified the feasibility of this method, and showed that for our experimental setup we could reduce the training error significantly. Furthermore, we investigated the effects of device and finite sampling noise, and we evaluated various mitigation techniques numerically on classical hardware. We took the best performing strategy and evaluated it on data from a real quantum processing unit. We found that using this mitigation strategy demonstrated an increased kernel matrix quality.
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 computing (QC) seems to show potential for application in machine learning (ML). In particular quantum kernel methods (QKM) exhibit promising properties for use in supervised ML tasks. However, a major disadvantage of kernel methods is their unfavorable quadratic scaling with the number of training samples. Together with the limits imposed by currently available quantum hardware (NISQ devices) with their low qubit coherence times, small number of qubits, and high error rates, the use of QC in ML at an industrially relevant scale is currently impossible. As a small step in improving the potential applications of QKMs, we introduce QUACK, a quantum kernel algorithm whose time complexity scales linear with the number of samples during training, and independent of the number of training samples in the inference stage. In the training process, only the kernel entries for the samples and the centers of the classes are calculated, i.e. the maximum shape of the kernel for n samples and c classes is (n, c). During training, the parameters of the quantum kernel and the positions of the centroids are optimized iteratively. In the inference stage, for every new sample the circuit is only evaluated for every centroid, i.e. c times. We show that the QUACK algorithm nevertheless provides satisfactory results and can perform at a similar level as classical kernel methods with quadratic scaling during training. In addition, our (simulated) algorithm is able to handle high-dimensional datasets such as MNIST with 784 features without any dimensionality reduction.
Quantum kernel methods are promising for near-term quantum machine learning, but their training costs are driven by the quadratic scaling of Gram-matrix construction and the measurement cost of estimating individual kernel values. In this work, we investigate one-class anomaly detection as a resource-efficient operating regime for training non-variational quantum kernel models. Using the ULB Credit Card Fraud Detection dataset, we evaluate three quantum feature maps across training-set sizes and qubit counts. Power-law saturation models reveal strong diminishing returns with increasing training data, with 500-sample models retaining approximately 90--93\% of their fitted asymptotic average precision (AP). We further observe no severe exponential concentration among the evaluated feature maps over the investigated qubit range, thereby avoiding the exponentially increasing measurement requirements associated with that regime. Finally, Nyström approximation reduces kernel construction from O(N2) to O(Nm) evaluations, with QSVR retaining 94--97\% of its exact-kernel AP using only five landmarks. For ZZ-QSVR, downsampling from 4,000 to 500 training samples and applying a five-landmark approximation decreases the number of required kernel evaluations from approximately 8.0 million to 2,485, a reduction of more than 3,200-fold, while AP decreases from 0.812 to 0.737. Under the minimum IonQ pricing assumption considered here, this corresponds to an illustrative reduction in quantum kernel training cost from approximately $1.34 billion to $417{,}480. These results demonstrate that training-set reduction and low-rank approximation can substantially reduce the resources required to train non-variational quantum kernel anomaly detectors while retaining meaningful anomaly-discrimination performance.
Abstract Quantum Machine Learning (QML) is an emerging field at the intersection of quantum computing and artificial intelligence, offering high potential for extracting complex nonlinear patterns from high-dimensional data. However, many quantum kernel-based methods suffer from high computational costs, the requirement for numerous quantum circuit executions, and the limitations of current Noisy Intermediate-Scale Quantum (NISQ) hardware. These challenges, particularly when dealing with large datasets, represent a major barrier to the widespread adoption of these methods in practical applications. In this paper, a hybrid quantum machine learning framework based on Nyström approximation is proposed to effectively reduce the computational complexity of quantum kernels and enhance their scalability. In the proposed framework, classical data is first mapped to the quantum Hilbert space via parameterized quantum circuits, and the quantum kernel is defined based on the overlap of quantum states. Then, utilizing the Nyström approximation technique, the full kernel calculation is restricted to a representative subset of data, and the final learning process is conducted in the classical space. This approach reduces computational complexity from O(N2) to O(Nm), where N is the number of samples and m is the size of the selected subset. Analytical results and simulations on the Breast Cancer Wisconsin dataset demonstrate that the proposed framework reduces computational costs by over 60% while maintaining the geometric structure of the quantum feature space, with a classification accuracy loss of less than 3%. These results suggest that the proposed method can serve as a practical, scalable, and noise-resilient solution for applying quantum machine learning to real-world data-driven problems.