Quantum kernel methods are a candidate for quantum speed-ups in supervised machine learning. The number of quantum measurements N required for a reasonable kernel estimate is a critical resource, both from complexity considerations and because of the constraints of near-term quantum hardware. We emphasize that for classification tasks, the aim is reliable classification and not precise kernel evaluation, and demonstrate that the former is far more resource efficient. Furthermore, it is shown that the accuracy of classification is not a suitable performance metric in the presence of noise and we motivate a new metric that characterizes the reliability of classification. We then obtain a bound for N which ensures, with high probability, that classification errors over a dataset are bounded by the margin errors of an idealized quantum kernel classifier. Using chance constraint programming and the subgaussian bounds of quantum kernel distributions, we derive several Shot-frugal and Robust (ShofaR) programs starting from the primal formulation of the Support Vector Machine. This significantly reduces the number of quantum measurements needed and is robust to noise by construction. Our strategy is applicable to uncertainty in quantum kernels arising from any source of unbiased noise.
Quantum kernel methods are a candidate for quantum speed-ups in supervised machine learning. The number of quantum measurements N required for a reasonable kernel estimate is a critical resource, both from complexity considerations and because of the constraints of near-term quantum hardware. We emphasize that for classification tasks, the aim is reliable classification and not precise kernel evaluation, and demonstrate that the former is far more resource efficient. Furthermore, it is shown that the accuracy of classification is not a suitable performance metric in the presence of noise and we motivate a new metric that characterizes the reliability of classification. We then obtain a bound for N which ensures, with high probability, that classification errors over a dataset are bounded by the margin errors of an idealized quantum kernel classifier. Using chance constraint programming and the subgaussian bounds of quantum kernel distributions, we derive several Shot-frugal and Robust (ShofaR) programs starting from the primal formulation of the Support Vector Machine. This significantly reduces the number of quantum measurements needed and is robust to noise by construction. Our strategy is applicable to uncertainty in quantum kernels arising from any source of unbiased noise.
Quantum kernel estimation (QKE) lets a quantum computer supply the similarity values a classical support vector machine needs, but the original hardware demonstration is hard to reproduce and gives little guidance on the number of shots a usable kernel requires. This study implements QKE on a two-qubit simulator and quantifies its shot and noise requirements. A second-order ZZ feature map encodes each data point, kernel entries are measured from an overlap circuit, and a classical support vector machine is trained on the resulting matrix. An artificial dataset of 40 training and 40 test points was generated with a separation gap of 0.3, the shot count was varied from 128 to 50,000, and a depolarising and readout noise model was applied; classical kernels and a variational classifier served as baselines. With an exactly computed kernel the classifier labels every training and test point correctly using 12 support vectors. Perfect test accuracy is reached at 1,024 shots per pair, far below the 50,000 used on hardware, and the deviation from the exact kernel decays with a fitted exponent of -0.52. The weight of negative eigenvalues falls from 2.019 to 0.096 as shots increase, making it a practical warning sign of too few shots. Under noise the kernel values drop by 0.014 on average, yet accuracy stays at 100% because the drop is nearly uniform. Classical kernels reach at most 70% test accuracy and the variational classifier 98.3%. The work contributes a reproducible open-source procedure and shot-budget guidance for quantum kernel experiments.
Quantum machine learning has emerged as a promising frontier, leveraging the principles of quantum computing to enhance classical algorithms. This paper proposes an optimized Quantum Support Vector Classifier (QSVC) for the classification of the MNIST dataset (a benchmark in handwritten digit recognition). We employ a Chebyshev Parameterized Quantum Circuit (PQC) with an increased number of qubits and layers, and utilize an existing projected quantum kernel method to effectively capture the complex patterns in the data. To enhance model robustness, data augmentation techniques are applied, and dimensionality reduction is performed using Principal Component Analysis (PCA). The proposed QSVC demonstrates competitive accuracy on both the training and testing datasets, highlighting the potential of quantum kernel methods in practical machine learning applications. A comparative analysis with classical Support Vector Machines (SVM) demonstrates the feasibility of quantum methods for high-dimensional classification tasks. Additionally, we investigate the impact of varying the number of qubits in the quantum circuit, providing in-depth insights into the scalability and performance trade-offs of quantum kernel methods.
To witness quantum advantages in practical settings, substantial efforts are required not only at the hardware level but also on theoretical research to reduce the computational cost of a given protocol. Quantum computation has the potential to significantly enhance existing classical machine learning methods, and several quantum algorithms for binary classification based on the kernel method have been proposed. These algorithms rely on estimating an expectation value, which in turn requires an expensive quantum data encoding procedure to be repeated many times. In this work, we calculate explicitly the number of repetition necessary for acquiring a fixed success probability and show that the Hadamard-test and the swap-test circuits achieve the optimal variance in terms of the quantum circuit parameters. The variance, and hence the number of repetition, can be further reduced only via optimization over data-related parameters. We also show that the kernel-based binary classification can be performed with a single-qubit measurement regardless of the number and the dimension of the data. Finally, we show that for a number of relevant noise models the classification can be performed reliably without quantum error correction. Our findings are useful for designing quantum classification experiments under limited resources, which is the common challenge in the noisy intermediate-scale quantum era.
Quantum devices in the current Noisy Intermediate-Scale Quantum (NISQ) era are inherently affected by noise, which can degrade the predictive performance of quantum machine learning models. In this work, we introduce a new margin-based robustness measure for Quantum Kernel-Assisted Support Vector Machines (QSVMs), termed the cross-kernel margin. This measure quantifies the stability of a classifier learned under a perturbed kernel relative to the ideal feature space. We derive a posteriori stability bounds for the corresponding cross-kernel inverse squared-margin under kernel perturbations using the Tikhonov-stabilised SVM dual formulation. The local depolarising noise model is then applied to this framework to induce perturbations in the kernel. The resulting bounds are numerically checked using simulations across multiple datasets and further tested using kernel matrices obtained from real quantum hardware and a noisy backend simulator. Furthermore, we empirically compare the degradation of test accuracy under local depolarising noise with the commonly used global depolarising noise model in order to motivate its use in our study. Finally, we present empirical results linking margin-based quantities with the generalisation performance of QSVMs, providing additional motivation for our margin-based robustness analysis.
The minimum accuracy heuristic evaluates quantum feature maps without requiring full quantum support vector machine (QSVM) training. However, the original formulation is computationally expensive, restricted to balanced datasets, and lacks theoretical backing. This work generalizes the metric to arbitrary binary datasets and formally proves it constitutes a certified lower bound on the optimal empirical accuracy of any linear classifier in the same feature space. Furthermore, we introduce Monte Carlo strategies to efficiently estimate this bound using a random subset of Pauli directions, accompanied by rigorous probabilistic guarantees. These contributions establish minimum accuracy as a scalable, theoretically sound tool for pre-screening feature maps on near-term quantum devices.
Support vector machines are powerful and frequently used machine learning methods for classification and regression tasks, which rely on the construction of kernel matrices. While crucial for the performance of this machine learning approach, choosing the most suitable kernel is highly problem-dependent. The emergence of quantum computers and quantum machine learning techniques provides new possibilities for generating powerful quantum kernels. Within this work, we solve a real-world price forecasting problem using fidelity and projected quantum kernels, which are promising candidates for the utility of near-term quantum computing. In our analysis, we examine and validate the most auspicious quantum kernels from literature and compare their performance with an optimized classical kernel. Unlike previous work on quantum support vector machines, our dataset includes categorical features that need to be encoded as numerical features, which we realize by using the one-hot-encoding scheme. One-hot-encoding, however, increases the dimensionality of the dataset significantly, which collides with the current limitations of noisy intermediate scale quantum computers. To overcome these limitations, we use autoencoders to learn a low-dimensional representation of the feature space that still maintains the most important information of the original data. To examine the impact of autoencoding, we compare the results of the encoded date with the results of the original, unencoded dataset. We could demonstrate that quantum kernels are comparable to or even better than the classical support vector machine kernels regarding the mean absolute percentage error scores for both encoded and unencoded datasets.