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

arXiv:2512.20588

Certified Lower Bounds and Efficient Estimation of Minimum Accuracy in Quantum Kernel Methods

Demerson N. Gonçalves, Tharso D. Fernandes, Andrias M. M. Cordeiro, Pedro H. G. Lugao, João T. Dias

quant-phcs.DSSubmitted Dec 23, 2025• Announced Dec 24, 2025• 0 citations
arXivHTMLPDF

Abstract

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.

Comments
16 pages, 2 figures

Related papers

Training-Free Certified Bounds for Quantum Regression: A Scalable Framework

Demerson N. Gonçalves, Tharso D. Fernandes, Pedro H. G. Lugao +1 more

We present a training-free, certified error bound for quantum regression derived directly from Pauli expectation values. Generalizing the heuristic of minimum accuracy from classification to regression, we evaluate axis-aligned predictors within the Pauli feature space. We formally prove that the optimal axis-aligned predictor constitutes a rigorous upper bound on the minimum training Mean Squared Error (MSE) attainable by any linear or kernel-based regressor defined on the same quantum feature map. Since computing this exact bound requires an intractable scan of the full Pauli basis, we introduce a Monte Carlo framework to efficiently estimate it using a tractable subset of measurement axes. We further provide non-asymptotic statistical guarantees to certify performance within a practical measurement budget. This method enables rapid comparison of quantum feature maps and early diagnosis of expressivity, allowing for the informed selection of architectures before deploying higher-complexity models.

quant-pharXiv:2601.00745•Jan 5, 2026•0 citations

Training-Free Certified Bounds for Quantum Regression: A Scalable Framework

Demerson N. Gonçalves, Tharso D. Fernandes, Pedro H. G. Lugão +1 more

Abstract We present a training-free, certified error bound for quantum regression derived directly from Pauli expectation values. Generalizing the heuristic of minimum accuracy from classification to regression, we evaluate axis-aligned predictors within the Pauli feature space. We formally prove that the optimal axis-aligned predictor yields a rigorous upper bound on the minimum training Mean Squared Error (MSE) attainable by any linear or kernel-based regressor defined on the same quantum feature map. Since computing this bound exactly requires an intractable scan over the full Pauli basis, we introduce an adaptive Monte Carlo framework that estimates it from a tractable subset of axes and provides non-asymptotic statistical guarantees under a finite measurement budget. The resulting procedure enables rapid, training-free comparison of quantum feature maps and early diagnosis of feature-map capacity through the observed density of high-quality Pauli axes, supporting informed architecture selection prior to deploying higher-complexity models.

•Mar 13, 2026•0 citations

Benchmarking Quantum Kernel Support Vector Machines Against Classical Baselines on Tabular Data: A Rigorous Empirical Study with Hardware Validation

Siavash Kakavand, Christoph Strohmeyer, Michael Schlotter

Quantum kernel methods have been proposed as a promising approach for leveraging near-term quantum computers for supervised learning, yet rigorous benchmarks against strong classical baselines remain scarce. We present a comprehensive empirical study of quantum kernel support vector machines (QSVMs) across nine binary classification datasets, four quantum feature maps, three classical kernels, and multiple noise models, totalling 970 experiments with strict nested cross-validation. Our analysis spans four phases: (i) statistical significance testing, revealing that none of 29 pairwise quantum-classical comparisons reach significance at $α= 0.05$; (ii) learning curve analysis over six training fractions, showing steeper quantum slopes on six of eight datasets that nonetheless fail to close the gap to the best classical baseline; (iii) hardware validation on IBM ibm_fez (Heron r2), demonstrating kernel fidelity $r \geq 0.976$ across six experiments; and (iv) seed sensitivity analysis confirming reproducibility (mean CV 1.4%). A Kruskal-Wallis factorial analysis reveals that dataset choice dominates performance variance ($\varepsilon^2 = 0.73$), while kernel type accounts for only 9%. Spectral analysis offers a mechanistic explanation: current quantum feature maps produce eigenspectra that are either too flat or too concentrated, missing the intermediate profile of the best classical kernel, the radial basis function (RBF). Quantum kernel training (QKT) via kernel-target alignment yields the single competitive result -- balanced accuracy 0.968 on breast cancer -- but with ~2,000x computational overhead. Our findings provide actionable guidelines for quantum kernel research. The complete benchmark suite is publicly available to facilitate reproduction and extension.

quant-pharXiv:2604.18837•Apr 22, 2026•0 citations

OptiPauli: An algorithm to find a near-optimal Pauli Feature Map for Quantum Support Vector Classifiers

Annika Daspal

Quantum Support Vector Classifiers have been gaining traction in solving classification problems as it enables efficient kernel estimation and potential improvement in accuracy. To estimate the kernel matrices, a quantum kernel needs a Pauli Feature Map which encodes the classical data into the quantum state space. For a given dataset and dimension, we can have an exorbitant number of Pauli Feature Maps. Hence, finding a Pauli Feature Map that maximizes model accuracy is a research challenge. To address this optimization problem, we propose an algorithm that finds a near-optimal Pauli Feature Map by solving several sub-problems with varying numbers of decision variables and their constraints. Each sub-problem aims to find the Pauli Feature Map that maximizes the model accuracy. We use genetic algorithm to solve each sub-problem, and then select the best out of all the near-optimal Pauli Feature Maps. Instead of formulating a single optimization problem, we use this divide-and-conquer approach (of breaking down the problem into multiple sub-problems) to reduce the overall search space. To evaluate the efficiency of our algorithm, we compare it against solving each sub-problem through exhaustive approach. The latter yields the optimal Pauli Feature Map by exploring the full state space. For the scikit-learn Breast Cancer dataset with dimension 5, our algorithm converges to the optimal Pauli Feature Map in about 804 seconds which is over 4 times faster than the exhaustive approach.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 1, 2022•4 citations

Empirical Evidence of Quantum Kernel Concentration in Few-Shot Keyword Spotting

Richard Caleb, Jagalingam Pushparaj

Quantum kernel methods utilize high-dimensional quantum feature spaces as a theoretically motivated strategy to address data scarcity in supervised classification. However, theoretical analyses predict exponential concentration of quantum kernel similarity values as qubit count increases. This study presents the first statistically controlled empirical evaluation of fixed-feature-map quantum support vector machines (QSVMs) for few-shot keyword spotting. The ZZFeatureMap and PauliFeatureMap circuits (2 to 3 qubits, PCA-compressed MFCC features, ~51% variance retained) were evaluated across 24 configurations and four low-resource regimes (5–30 samples per class) on the Google Speech Commands dataset, using ten independent seeds with Wilcoxon signed-rank tests and Bonferroni correction. Across all configurations and sample sizes, QSVM accuracy remained close to the five-class random baseline (19.3% at 30 samples per class; random baseline 20%), while RBF SVM achieved 38.7% and a compact CNN achieved 65.3%. Direct kernel similarity measurement confirmed severe concentration, where the 3-qubit QSVM produced near-identical same-class and different-class similarity means (both approximately 0.192), with 94.1% overlap. Under matched MFCC+PCA features, all classical kernels outperformed QSVM, including linear SVM (Cliff’s $\delta = -0.98$ , $p = 0.002$ ) and RBF SVM ( $\delta = -0.82$ , $p = 0.002$ , Bonferroni-corrected $\alpha = 0.003$ ), with CNN achieving complete stochastic dominance ( $\delta = -1.00$ ). These results empirically validate quantum kernel concentration in structured acoustic classification within evaluated NISQ constraints, and apply specifically to the fixed-feature-map paradigm, not quantum kernel methods in general. The identified failure modes, namely exponential concentration, geometric misalignment, and limited circuit expressivity, provide concrete directions for future research into trainable quantum feature maps and hybrid quantum-classical architectures.

IEEE Access•Jan 1, 2026•0 citations

Investigating Quantum Feature Maps in Quantum Support Vector Machines for Lung Cancer Classification

Achraf Toufah, MA Kadim, Moulay Youssef El Hafidi

Background: Classical algorithms often struggle with the high dimensionality of medical data critical for early lung cancer diagnosis. While Quantum Machine Learning (QML) offers enhanced pattern recognition capabilities, the impact of specific quantum feature encoding strategies on diagnostic accuracy remains underexplored.Methods: We evaluated Quantum Support Vector Machines (QSVM) using a dataset of 309 lung cancer patients, divided into six balanced subsets to mitigate class imbalance. Models were implemented on a qasm simulator, comparing three encoding strategies: ZFeatureMap, ZZFeatureMap, and PauliFeatureMap. Performance was assessed using standard classification metrics.Results: The choice of feature map significantly influenced model efficacy. The PauliFeatureMap outperformed other kernels, achieving 100% classification accuracy in three of the six subsets, whereas ZFeatureMap and ZZFeatureMap yielded lower predictive consistency.Conclusion: Quantum feature map selection is a decisive factor in QSVM performance. Specifically, the PauliFeatureMap demonstrates high separability for medical data, highlighting the potential of optimized quantum kernels to improve diagnostic precision.

Journal of Artificial Intelligence Research and Innovation•Dec 29, 2025•6 citations
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.
We present a training-free, certified error bound for quantum regression derived directly from Pauli expectation values. Generalizing the heuristic of minimum accuracy from classification to regression, we evaluate axis-aligned predictors within the Pauli feature space. We formally prove that the optimal axis-aligned predictor constitutes a rigorous upper bound on the minimum training Mean Squared Error (MSE) attainable by any linear or kernel-based regressor defined on the same quantum feature map. Since computing this exact bound requires an intractable scan of the full Pauli basis, we introduce a Monte Carlo framework to efficiently estimate it using a tractable subset of measurement axes. We further provide non-asymptotic statistical guarantees to certify performance within a practical measurement budget. This method enables rapid comparison of quantum feature maps and early diagnosis of expressivity, allowing for the informed selection of architectures before deploying higher-complexity models.
Abstract We present a training-free, certified error bound for quantum regression derived directly from Pauli expectation values. Generalizing the heuristic of minimum accuracy from classification to regression, we evaluate axis-aligned predictors within the Pauli feature space. We formally prove that the optimal axis-aligned predictor yields a rigorous upper bound on the minimum training Mean Squared Error (MSE) attainable by any linear or kernel-based regressor defined on the same quantum feature map. Since computing this bound exactly requires an intractable scan over the full Pauli basis, we introduce an adaptive Monte Carlo framework that estimates it from a tractable subset of axes and provides non-asymptotic statistical guarantees under a finite measurement budget. The resulting procedure enables rapid, training-free comparison of quantum feature maps and early diagnosis of feature-map capacity through the observed density of high-quality Pauli axes, supporting informed architecture selection prior to deploying higher-complexity models.
Quantum kernel methods have been proposed as a promising approach for leveraging near-term quantum computers for supervised learning, yet rigorous benchmarks against strong classical baselines remain scarce. We present a comprehensive empirical study of quantum kernel support vector machines (QSVMs) across nine binary classification datasets, four quantum feature maps, three classical kernels, and multiple noise models, totalling 970 experiments with strict nested cross-validation. Our analysis spans four phases: (i) statistical significance testing, revealing that none of 29 pairwise quantum-classical comparisons reach significance at α=0.05α= 0.05α=0.05; (ii) learning curve analysis over six training fractions, showing steeper quantum slopes on six of eight datasets that nonetheless fail to close the gap to the best classical baseline; (iii) hardware validation on IBM ibm_fez (Heron r2), demonstrating kernel fidelity r≥0.976r \geq 0.976r≥0.976 across six experiments; and (iv) seed sensitivity analysis confirming reproducibility (mean CV 1.4%). A Kruskal-Wallis factorial analysis reveals that dataset choice dominates performance variance (ε2=0.73\varepsilon^2 = 0.73ε2=0.73), while kernel type accounts for only 9%. Spectral analysis offers a mechanistic explanation: current quantum feature maps produce eigenspectra that are either too flat or too concentrated, missing the intermediate profile of the best classical kernel, the radial basis function (RBF). Quantum kernel training (QKT) via kernel-target alignment yields the single competitive result -- balanced accuracy 0.968 on breast cancer -- but with ~2,000x computational overhead. Our findings provide actionable guidelines for quantum kernel research. The complete benchmark suite is publicly available to facilitate reproduction and extension.
Quantum Support Vector Classifiers have been gaining traction in solving classification problems as it enables efficient kernel estimation and potential improvement in accuracy. To estimate the kernel matrices, a quantum kernel needs a Pauli Feature Map which encodes the classical data into the quantum state space. For a given dataset and dimension, we can have an exorbitant number of Pauli Feature Maps. Hence, finding a Pauli Feature Map that maximizes model accuracy is a research challenge. To address this optimization problem, we propose an algorithm that finds a near-optimal Pauli Feature Map by solving several sub-problems with varying numbers of decision variables and their constraints. Each sub-problem aims to find the Pauli Feature Map that maximizes the model accuracy. We use genetic algorithm to solve each sub-problem, and then select the best out of all the near-optimal Pauli Feature Maps. Instead of formulating a single optimization problem, we use this divide-and-conquer approach (of breaking down the problem into multiple sub-problems) to reduce the overall search space. To evaluate the efficiency of our algorithm, we compare it against solving each sub-problem through exhaustive approach. The latter yields the optimal Pauli Feature Map by exploring the full state space. For the scikit-learn Breast Cancer dataset with dimension 5, our algorithm converges to the optimal Pauli Feature Map in about 804 seconds which is over 4 times faster than the exhaustive approach.
Quantum kernel methods utilize high-dimensional quantum feature spaces as a theoretically motivated strategy to address data scarcity in supervised classification. However, theoretical analyses predict exponential concentration of quantum kernel similarity values as qubit count increases. This study presents the first statistically controlled empirical evaluation of fixed-feature-map quantum support vector machines (QSVMs) for few-shot keyword spotting. The ZZFeatureMap and PauliFeatureMap circuits (2 to 3 qubits, PCA-compressed MFCC features, ~51% variance retained) were evaluated across 24 configurations and four low-resource regimes (5–30 samples per class) on the Google Speech Commands dataset, using ten independent seeds with Wilcoxon signed-rank tests and Bonferroni correction. Across all configurations and sample sizes, QSVM accuracy remained close to the five-class random baseline (19.3% at 30 samples per class; random baseline 20%), while RBF SVM achieved 38.7% and a compact CNN achieved 65.3%. Direct kernel similarity measurement confirmed severe concentration, where the 3-qubit QSVM produced near-identical same-class and different-class similarity means (both approximately 0.192), with 94.1% overlap. Under matched MFCC+PCA features, all classical kernels outperformed QSVM, including linear SVM (Cliff’s δ=−0.98\delta = -0.98δ=−0.98 , p=0.002p = 0.002p=0.002 ) and RBF SVM ( δ=−0.82\delta = -0.82δ=−0.82 , p=0.002p = 0.002p=0.002 , Bonferroni-corrected α=0.003\alpha = 0.003α=0.003 ), with CNN achieving complete stochastic dominance ( δ=−1.00\delta = -1.00δ=−1.00 ). These results empirically validate quantum kernel concentration in structured acoustic classification within evaluated NISQ constraints, and apply specifically to the fixed-feature-map paradigm, not quantum kernel methods in general. The identified failure modes, namely exponential concentration, geometric misalignment, and limited circuit expressivity, provide concrete directions for future research into trainable quantum feature maps and hybrid quantum-classical architectures.
Background: Classical algorithms often struggle with the high dimensionality of medical data critical for early lung cancer diagnosis. While Quantum Machine Learning (QML) offers enhanced pattern recognition capabilities, the impact of specific quantum feature encoding strategies on diagnostic accuracy remains underexplored.Methods: We evaluated Quantum Support Vector Machines (QSVM) using a dataset of 309 lung cancer patients, divided into six balanced subsets to mitigate class imbalance. Models were implemented on a qasm simulator, comparing three encoding strategies: ZFeatureMap, ZZFeatureMap, and PauliFeatureMap. Performance was assessed using standard classification metrics.Results: The choice of feature map significantly influenced model efficacy. The PauliFeatureMap outperformed other kernels, achieving 100% classification accuracy in three of the six subsets, whereas ZFeatureMap and ZZFeatureMap yielded lower predictive consistency.Conclusion: Quantum feature map selection is a decisive factor in QSVM performance. Specifically, the PauliFeatureMap demonstrates high separability for medical data, highlighting the potential of optimized quantum kernels to improve diagnostic precision.