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.
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.
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.
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.
Finding optimal measurement operators is crucial for the performance of quantum reservoir computers (QRCs), since they employ a fixed quantum feature map. We formulate the training of both stateless (quantum extreme learning machines, QELMs) and stateful (memory dependent) QRCs in the framework of kernel ridge regression. We thus extend the kernel viewpoint of supervised quantum models to recurrent QRCs by deriving an exact Hilbert--Schmidt kernel representation of the optimal readout observable on history space. This approach renders an optimal measurement operator that minimizes prediction error for a given reservoir and training dataset. For large qubit numbers, this method is more efficient than the conventional training of QRCs. We discuss efficiency and practical implementation strategies, including Pauli basis decomposition and operator diagonalization, to adapt the optimal observable to hardware constraints. To demonstrate the effectiveness of this approach, we present numerical experiments on image classification and time series prediction tasks, including chaotic and strongly non-Markovian systems. The developed method can also be applied to other quantum machine learning models.
Hybrid variational quantum algorithms are promising for solving practical problems, such as combinatorial optimization, quantum chemistry simulation, quantum machine learning, and quantum error correction on noisy quantum computers. However, variational quantum algorithms (derived from randomized hardware-efficient ansatz or adaptive ansatz) become a black box, not trustworthy for model interpretation, and not to mention for application deployment in informing critical decisions. In this paper, we construct the first interpretable quantum regression algorithm, in which the quantum state exactly encodes the classical data table and the variational parameters correspond directly to the regression coefficients, which are real numbers by construction, providing a high degree of model interpretability and minimal cost to optimize due to the right expressiveness. We also exploit the encoded data structure to reduce the gate complexity of computing the regression map. To reduce circuit depth in nonlinear regression, our algorithm can be extended by directly constructing nonlinear features via classical preprocessing, such as independent encoded column vectors. By design, the model performance is determined by the cost function measurement results C synchronous to the mean squared errors (MSE) for the regression models. We derived the read-out errors induced by one-hot encoding and compact encoding; the required physical qubit resources are exponentially compressed for the compact encoding to be favorable for noisy quantum devices. We also derive the cost function dependent sample complexity $ \in \mathcal{O}\left(σ^{2}(\mathcal{C}) \ln (1/α)/ε^{2}\right)$ under the error budget ε and confidence tolerance α.
Quantum-enhanced machine learning is a rapidly evolving field that aims to leverage the unique properties of quantum mechanics to enhance classical machine learning. However, the practical applicability of these methods remains an open question, particularly beyond the context of specifically crafted toy problems, and given the current limitations of quantum hardware. This study focuses on quantum kernel methods in the context of classification tasks. In particular, it examines the performance of quantum kernel estimation and quantum kernel training (QKT) in connection with two quantum feature mappings, namely, ZZFeatureMap and CovariantFeatureMap. Remarkably, these feature maps have been proposed in the literature under the conjecture of possible near-term quantum advantage and have shown promising performance in ad hoc datasets. This study aims to evaluate their versatility and generalization capabilities in a more general benchmark, encompassing both artificial and established reference datasets. Classical machine learning methods, specifically support vector machines and logistic regression, are also incorporated as baseline comparisons. Experimental results indicate that quantum methods exhibit varying performance across different datasets. Despite outperforming classical methods in ad hoc datasets, mixed results are obtained for the general case among standard classical benchmarks. The experimental data call into question a general added value of applying QKT optimization, for which the additional computational cost does not necessarily translate into improved classification performance. Instead, it is suggested that a careful choice of the quantum feature map in connection with proper hyperparameterization may prove more effective.