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

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.