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

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.