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 · 2025

Read Certified Lower Bounds and Efficient Estimation of Minimum Accuracy in Quantum Kernel Methods by Demerson N. Gonçalves, Tharso D. Fernandes, Andrias M. M. Cordeiro, Pedro H. G. Lugao, João T. Dias (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-20588.txt.

Introduction

Demerson N Gonçalves and co-authors make a screening tool for quantum machine learning both cheaper and rigorous. The minimum accuracy heuristic estimates how well a quantum feature map can do without training a full quantum support vector machine. Originally it was expensive, limited to balanced data sets, and theoretically unproven.

The authors generalize the metric to arbitrary binary data sets and prove it is a certified lower bound on the best empirical accuracy of any linear classifier in the same feature space. Monte Carlo strategies then estimate the bound from a random subset of Pauli directions, with probabilistic guarantees attached. Feature map designers for near-term quantum devices gain a scalable, trustworthy pre-screen before committing to full training runs.

Catalog record

CREATORDemerson N. Gonçalves, Tharso D. Fernandes, Andrias M. M. Cordeiro, Pedro H. G. Lugao, João T. Dias
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE34 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-20588

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

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 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. keywords Quantum kernel methods, Minimum accuracy, Feature map evaluation, Pauli decomposition. 1 Introduction Machine learning (ML) is a key part of modern science and technology, supporting tasks such as pattern recognition, decision-making under uncertainty, and automated discovery in complex data russel2010 . Quantum machine learning (QML) is a growing field that aims to go beyond classical ML by exploiting the structure and resources of quantum systems Rocchetto2018 . One of the most promising QML paradigms is based on quantum kernel methods. Central to this framework is the feature map , a transformation that embeds input data into a high-dimensional vector space to render complex, non-linear patterns linearly separable. In the quantum setting, this map encodes classical data into quantum states through parameterized quantum circuits, allowing classical algorithms such as support vector machines (SVMs) to operate on the resulting quantum-induced feature space ayachi ; petruccione . Quantum kernel methods are naturally suited to Noisy Intermediate-Scale Quantum (NISQ) devices because the most expensive operation, evaluating the kernel entries via quantum circuits, is delegated to the quantum hardware, while optimization and training are performed classically wang . Foundational works by Havlíček et al. havlicek2019supervised and Schuld and Killoran schuld2019quantum introduced the notion of quantum feature maps, establishing the basic hybrid quantum–classical framework. Subsequent research has investigated the expressivity generalization properties of these maps, as well as their implementation on real quantum processors tacchino2020quantum ; huang2021power ; li2022quantumkernel ; raubitzek . A practical challenge in this setting is how to compare different quantum feature maps without having to train a complete quantum support vector machine (QSVM) for each candidate. Suzuki et al. suzuki2022analysis addressed this problem by proposing the minimum accuracy heuristic, which estimates the best achievable classification accuracy when measurements are restricted to axis-aligned Pauli observables. Their method avoids explicit optimization and can be resource-efficient in small and medium-scale quantum systems, since it eliminates repeated training. However, the original formulation has three important limitations: it assumes balanced, even-sized datasets; it is presented as a heuristic without a formal proof that it lower-bounds the optimal SVM accuracy in the same feature space; and its computation requires a full Pauli decomposition, whose cost scales as 4^{n} for n qubits, quickly becoming intractable for larger systems. In this work we advance the analysis and practical usability of the minimum accuracy in three main directions, going beyond the original proposal suzuki2022analysis . First, we generalize the definition of minimum accuracy to arbitrary binary datasets (Section 2 ), removing assumptions on sample size and class balance; our formulation is valid for any number of training examples N and any label distribution, while preserving the geometric intuition of axis-aligned thresholds in the Pauli feature space. Second, we provide a rigorous theoretical result (Theorem 1 ) showing that the generalized minimum accuracy R_{\min} is always a certified lower bound on the optimal empirical accuracy R^{*} achievable by a linear SVM in the same feature space, i.e., R_{\min}\leq R^{*} ; this formally justifies the use of minimum accuracy as a provable baseline rather than a purely empirical heuristic. Third, we introduce a family of Monte Carlo-based axis-selection strategies (Section 4 ) that estimate R_{\min} from a random subset of Pauli-feature axes and derive statistical guarantees, via a quantile-coverage analysis, that relate the number of sampled axes to the probability of capturing high-performing directions (Theorem 3 and Corollary 1 ) Rubinstein2016 . From a practical standpoint, our results show that the minimum accuracy can be turned into a scalable, certified tool for evaluating quantum feature maps in QSVM pipelines. The generalized definition makes the metric applicable to real-world, possibly imbalanced datasets; the lower-bound theorem connects it directly to SVM performance in the same kernel-induced feature space; and the Monte Carlo strategies drastically reduce the number of Pauli axes that need to be evaluated in high-dimensional spaces. This approach suggests a concrete workflow: for any quantum feature map \Phi:\mathcal{X}\to\mathbb{R}^{4^{n}}, one avoids the exponential cost of characterizing the full space by drawing a random sample of t\ll 4^{n} Pauli axes; one then obtains the dataset projections \{a_{i}(x_{k})\}_{k=1}^{N} only for these sampled directions, where a_{i}(x)=\mathrm{Tr}[\rho(x)\sigma_{i}] (Section 2 ), and computes the corresponding axis-wise accuracies. This yields a scalable approximation with explicit guarantees that the estimated minimum accuracy exceeds a target threshold with high confidence. Finally, this certified baseline allows one to discard feature maps with low R_{\min} and prioritize those with high R_{\min} before investing in full QSVM training. In this way, the computational cost of QSVM pipeline design can be reduced from \mathcal{O}(N^{2}\cdot 4^{n}+N^{3}) (classical simulation of full kernel SVM) or \tilde{\mathcal{O}}(N^{4.67}/\varepsilon^{2}) quantum circuit evaluations gentinetta2024complexity to \mathcal{O}(tN\log N) classical operations, where t=\mathcal{O}\bigl(\frac{1}{p}\log\frac{1}{\delta}\bigr) is typically small ( t\approx 10 – 100 ) when good axes exist. The remainder of this paper is organized as follows. Section 2 introduces the generalized minimum accuracy framework. Section 3 provides the formal proof that R_{\min}\leq R^{*} . Section 4 establishes the theoretical foundations for Monte Carlo axis selection, followed by Section 5 , which details the concrete sampling strategies. Section 6 reports the empirical results on synthetic datasets. Finally, Section 7 concludes with a discussion and directions for future work. 2 Generalized minimum accuracy We consider a binary classification problem with a dataset D=\{(x_{k},y_{k})\}_{k=1}^{N}, where each input x_{k}\in\mathcal{X} is associated with a label y_{k}\in\{-1,+1\} . A feature map \Phi:\mathcal{X}\to\mathbb{R}^{d} embeds the data into a d ‑dimensional real feature space. In the quantum setting, \Phi is typically induced by a parameterized quantum circuit acting on n qubits, and we have d=4^{n} , with coordinates given by expectation values of Pauli observables, \Phi(x)=\bigl(a_{1}(x),a_{2}(x),\dots,a_{d}(x)\bigr),\qquad a_{i}(x)=\mathrm{Tr}\bigl[\rho(x)\,\sigma_{i}\bigr], (1) where \rho(x) is the quantum state prepared from x and \{\sigma_{i}\}_{i=1}^{d} is an orthonormal Pauli basis. The validity of this decomposition and the interpretation of coefficients as expectation values follow from the completeness of the Pauli group in the space of Hermitian operators nielsen_chuang . We refer to each coordinate direction i\in\{1,\dots,d\} as a Pauli‑feature axis . The idea behind minimum accuracy is to evaluate, for each Pauli‑feature axis, how well the dataset can be separated by a one‑dimensional threshold on that coordinate. Fix an index i\in\{1,\dots,d\} and a threshold \tau\in\mathbb{R} . We consider the one‑dimensional classifier f_{i,\tau}(x)=\mathrm{sign}\bigl(a_{i}(x)-\tau\bigr), (2) which assigns all points with a_{i}(x)\geq\tau to one side of the threshold and all points with a_{i}(x)<\tau to the other side. Since the overall sign of the classifier is arbitrary with respect to the labels \{-1,+1\} , for each

Read the complete text