Training-Free Certified Bounds for Quantum Regression: A Scalable Framework
Preprint
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 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.Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Barren plateaus in variational quantum computingNature Reviews Physics, 2025
- Power of data in quantum machine learningNature Communications, 2021
- Cost function dependent barren plateaus in shallow parametrized quantum circuitsNature Communications, 2021
- Analysis and synthesis of feature map for kernel-based quantum classifierQuantum Machine Intelligence, 2020
- Expressibility and Entangling Capability of Parameterized Quantum Circuits for Hybrid Quantum‐Classical AlgorithmsAdvanced Quantum Technologies, 2019
- Supervised learning with quantum-enhanced feature spacesNature, 2019
- Barren plateaus in quantum neural network training landscapesNature Communications, 2018
- A tutorial on support vector regressionStatistics and Computing, 2004
- Measurement Error Models1987
- Probability Inequalities for Sums of Bounded Random VariablesJournal of the American Statistical Association, 1963