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

Quantum Reports

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

Demerson Nunes Gonçalves, Tharso D. Fernandes, Andrias M. M. Cordeiro, Pedro H. G. Lugão, João Terêncio Dias, Fernando Manuel Araújo-Moreira

Published Jul 31, 2026• 0 citations
Publisher

Abstract

The minimum accuracy heuristic provides a training-free way to evaluate quantum feature maps, but its original formulation assumes balanced datasets, requires an exhaustive Pauli-axis scan, and lacks a formal lower-bound interpretation. In this work, we generalize the metric to arbitrary binary datasets and prove that the resulting generalized minimum accuracy, denoted Rmin, is a certified lower bound on the optimal empirical accuracy R* achievable by linear classifiers in the same feature space. To improve scalability, we introduce Monte Carlo axis-selection strategies that estimate Rmin from random subsets of Pauli-feature axes and derive quantile-coverage guarantees for sampling high-accuracy directions. We validate the framework using exact statevector simulations of an n=6 qubit quantum feature map, corresponding to d=46=4096 Pauli axes, over 30 independent runs on five synthetic datasets. The proposed methods sample as few as 60 axes, produce lower-bound estimates and achieve speedups of approximately 27× to 68× compared with exhaustive evaluation. The results support generalized minimum accuracy as a scalable and theoretically grounded tool for pre-screening quantum feature maps in simulated quantum-kernel workflows.

DOI
10.3390/quantum8030073

Related papers

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

Demerson N. Gonçalves, Tharso D. Fernandes, Andrias M. M. Cordeiro +2 more

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.

quant-pharXiv:2512.20588•Dec 24, 2025•0 citations

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

Large-Scale Quantum Kernels for Hyperspectral Data Classification

A. Delilbasic, A. Miroszewski, A. Wijata +4 more

Quantum kernel methods have emerged as a promising approach for leveraging high-dimensional feature spaces in machine learning, particularly in domains where classical kernel methods face scalability limitations. In this work, we present the first large-scale study of fidelity-quantum-kernel support vector machines for hyperspectral data classification without requiring heavy prior feature selection or dimensionality reduction. By simulating quantum kernels using tensor network contraction techniques and GPU acceleration, we overcome the computational bottlenecks traditionally associated with quantum models, achieving quadratic scaling O(n^2) in the number of qubits. Our approach enables the evaluation of quantum kernels on hyperspectral data with hundreds of spectral bands, aligning quantum feature spaces with real-world remote sensing applications. We provide an in-depth analysis of kernel bandwidth optimization, demonstrating its crucial role in mitigating exponential concentration effects and ensuring the model's ability to generalize. Experimental results on binary classification (Indian Pines and Methane Detection) and multiclass classification (Indian Pines) demonstrate that quantum kernels achieve competitive performance compared to a broad range of state-of-the-art classical baselines. As illustrative cases, on four 50-band splits selected from Indian Pines, the quantum model achieved a 78.0 pm6.2% accuracy for a binary classification task compared to 72.0 pm5.0% for the standard radial basis function (RBF) kernel. For a four-class classification task, the quantum kernel reached 83.3 pm3.1% accuracy, outperforming several state-of-the-art baselines. On five 75-band splits selected from the Methane Detection dataset, the quantum approach yielded 58.5\pm5.0% accuracy versus 55.1\pm2.5% for the classical counterpart...

quant-pharXiv:2605.17587•IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing•May 19, 2026•1 citation

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 Evaluation of Quantum Kernel Methods for Classification: A Comparative Study with Classical Kernels

Ronak Bhalgami

Quantum kernel methods are the most concrete near-term proposal for quantum machine learning on classical data, yet published benchmarks disagree on whether they outperform tuned classical kernels, and the disagreement cannot be resolved from the literature because the comparisons are not protocol-controlled. We argue that the obstacle is one of measurement, not theory: the usual setup fixes the quantum feature map's data scaling while grid-searching the classical kernel's hyperparameters, recomputes nothing per fold, and reports cost in simulator time. We therefore treat the comparison itself as the object of study and impose three controls. The bandwidth is tuned on the same grid budget as the classical $γ$, the kernel is recomputed inside every fold from fold-fitted preprocessing, and cost is counted in hardware circuit evaluations. On top of these we run a factorial design of 324 cells in which dimensionality, training size, class separability and data structure are explicit covariates, together with four standard datasets, a shots-versus-gate-noise ablation, and a cost sweep. The dominant effect we measure is not quantum: tuning the feature map's bandwidth is worth 0.120 accuracy on synthetic data and 0.339 on real data, exceeding every quantum-classical difference we observe. Tuned quantum kernels are then statistically indistinguishable from a tuned RBF on all four real datasets. The advantage on synthetic data is confined almost entirely to data generated by the feature map itself, and it shrinks with dimensionality (-0.0045 per qubit) while growing with sample size. Finite sampling costs an order of magnitude more accuracy than gate and readout noise, and a fidelity kernel needs $5\times10^{7}$ circuits at n = 10,000. Protocol variance is thus sufficient to explain the field's contradictory conclusions.

quant-pharXiv:2610.42029•Nov 2, 2026
The minimum accuracy heuristic provides a training-free way to evaluate quantum feature maps, but its original formulation assumes balanced datasets, requires an exhaustive Pauli-axis scan, and lacks a formal lower-bound interpretation. In this work, we generalize the metric to arbitrary binary datasets and prove that the resulting generalized minimum accuracy, denoted Rmin, is a certified lower bound on the optimal empirical accuracy R* achievable by linear classifiers in the same feature space. To improve scalability, we introduce Monte Carlo axis-selection strategies that estimate Rmin from random subsets of Pauli-feature axes and derive quantile-coverage guarantees for sampling high-accuracy directions. We validate the framework using exact statevector simulations of an n=6 qubit quantum feature map, corresponding to d=46=4096 Pauli axes, over 30 independent runs on five synthetic datasets. The proposed methods sample as few as 60 axes, produce lower-bound estimates and achieve speedups of approximately 27× to 68× compared with exhaustive evaluation. The results support generalized minimum accuracy as a scalable and theoretically grounded tool for pre-screening quantum feature maps in simulated quantum-kernel workflows.
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 emerged as a promising approach for leveraging high-dimensional feature spaces in machine learning, particularly in domains where classical kernel methods face scalability limitations. In this work, we present the first large-scale study of fidelity-quantum-kernel support vector machines for hyperspectral data classification without requiring heavy prior feature selection or dimensionality reduction. By simulating quantum kernels using tensor network contraction techniques and GPU acceleration, we overcome the computational bottlenecks traditionally associated with quantum models, achieving quadratic scaling O(n^2) in the number of qubits. Our approach enables the evaluation of quantum kernels on hyperspectral data with hundreds of spectral bands, aligning quantum feature spaces with real-world remote sensing applications. We provide an in-depth analysis of kernel bandwidth optimization, demonstrating its crucial role in mitigating exponential concentration effects and ensuring the model's ability to generalize. Experimental results on binary classification (Indian Pines and Methane Detection) and multiclass classification (Indian Pines) demonstrate that quantum kernels achieve competitive performance compared to a broad range of state-of-the-art classical baselines. As illustrative cases, on four 50-band splits selected from Indian Pines, the quantum model achieved a 78.0 pm6.2% accuracy for a binary classification task compared to 72.0 pm5.0% for the standard radial basis function (RBF) kernel. For a four-class classification task, the quantum kernel reached 83.3 pm3.1% accuracy, outperforming several state-of-the-art baselines. On five 75-band splits selected from the Methane Detection dataset, the quantum approach yielded 58.5\pm5.0% accuracy versus 55.1\pm2.5% for the classical counterpart...
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 are the most concrete near-term proposal for quantum machine learning on classical data, yet published benchmarks disagree on whether they outperform tuned classical kernels, and the disagreement cannot be resolved from the literature because the comparisons are not protocol-controlled. We argue that the obstacle is one of measurement, not theory: the usual setup fixes the quantum feature map's data scaling while grid-searching the classical kernel's hyperparameters, recomputes nothing per fold, and reports cost in simulator time. We therefore treat the comparison itself as the object of study and impose three controls. The bandwidth is tuned on the same grid budget as the classical γγγ, the kernel is recomputed inside every fold from fold-fitted preprocessing, and cost is counted in hardware circuit evaluations. On top of these we run a factorial design of 324 cells in which dimensionality, training size, class separability and data structure are explicit covariates, together with four standard datasets, a shots-versus-gate-noise ablation, and a cost sweep. The dominant effect we measure is not quantum: tuning the feature map's bandwidth is worth 0.120 accuracy on synthetic data and 0.339 on real data, exceeding every quantum-classical difference we observe. Tuned quantum kernels are then statistically indistinguishable from a tuned RBF on all four real datasets. The advantage on synthetic data is confined almost entirely to data generated by the feature map itself, and it shrinks with dimensionality (-0.0045 per qubit) while growing with sample size. Finite sampling costs an order of magnitude more accuracy than gate and readout noise, and a fidelity kernel needs 5×1075\times10^{7}5×107 circuits at n = 10,000. Protocol variance is thus sufficient to explain the field's contradictory conclusions.