Introduction
Parameterized quantum circuits (PQCs) are widely studied as trainable quantum models for supervised learning, e.g. binary classification [17 , 3 ] . Classical inputs and trainable parameters enter a sequence of quantum gates, possibly through repeated data encoding, and measurements of the resulting state provide real-valued prediction scores. The functions represented by such circuits depend on the circuit architecture, depth, and encoding strategy [21 ] .
On near-term hardware, the noisy circuit executions are used during training to estimate prediction scores, losses, gradients, and other quantities required by the optimizer. Noise can therefore alter both the final circuit evaluations and the optimization trajectory that produces the classifier, so the procedure intended to reproduce the corresponding ideal learning process must account for it.
These training quantities are typically computed from circuit expectation values. Quantum error mitigation (QEM) offers a way to estimate the corresponding noiseless expectation values from noisy circuit executions [5 ] . Methods include zero-noise extrapolation [22 , 12 ] , virtual distillation [9 ] , and probabilistic error cancellation (PEC) [22 , 7 ] . PEC is particularly convenient for a resource comparison because it produces an unbiased estimator of an ideal expectation value through a quasiprobability decomposition of the inverse noise channel [22 , 7 ] . The resulting variance amplification leads to a sampling overhead proportional to the squared quasiprobability norm, which can grow exponentially with the number of noisy circuit locations [TBG17, EBL18, [23 ] . More generally, lower bounds show that recovery of noiseless observables can require superpolynomial sampling resources in broad noisy-circuit settings [23 , 18 ] .
These results motivate a different question. They concern recovery of the ideal circuit output, but a learning task need not require that entire quantity. In binary classification, for example, the relevant objective is to assign the correct label with sufficient margin. Accurate reconstruction of every ideal expectation value is therefore a stronger requirement than correct classification. This task structure suggests that it may be possible to use information that remains available in noisy circuit outputs without first reconstructing the corresponding ideal outputs. Boosting provides a well-established method for obtaining accurate predictions by combining less accurate classifiers [19 , 8 ] .
More specifically, we investigate this connection by treating noisy PQCs as so-called weak learners (as called in computational learning theory, and defined later) and combining them using classical boosting. We compare this strategy with PEC for the same binary-classification problem and ask how many quantum-circuit executions each method requires to attain a common learning criterion. The PEC strategy applies quasiprobability sampling to the expectation-value evaluations of a target-reaching noiseless reference procedure, whereas the boosting strategy trains and combines noisy PQCs directly under the physical noise model.
A resource comparison of this type is meaningful only when the ideal circuit output is not already efficiently available by classical computation. For efficiently classically simulable circuit families, such as Clifford circuits, the ideal quantity can instead be computed directly [1 ] .
To compare PEC and boosting on common statistical terms, we use a margin-based generalization bound. Both strategies are required to attain the same empirical margin-loss target on the same training sample and are using the same reference hypothesis class. Consequently, attaining the common empirical target gives the same high-probability upper bound on expected classification risk, allowing the circuit resources required to reach that target to be compared directly.
The two methods incur qualitatively different resource costs. For PEC, the sampling cost is governed by the so-called squared quasiprobability overhead γ 2 \gamma^2 γ 2 , which is determined by the circuit and noise model. For boosting, the required resource depends on the sequence of weak learners obtained under the adaptively reweighted training distributions. For Real AdaBoost [20 ] , we derive an upper bound on the number of boosting rounds needed to reach the common learning target, provided that every weak learner meets a performance requirement determined by the chosen margin. For AdaBoostR [16 ] , the corresponding condition also depends on the weights assigned to the weak learners during training. These requirements are stated precisely in § 5 . The performance of the weak learners cannot, however, be determined from the physical noise strength alone.
Consequently, we could not determine the exact PEC–boosting resource comparison. We therefore perform finite-shot numerical experiments to measure the boosting resource directly and determine how the ordering of the two methods changes with circuit depth and physical noise strength. In these experiments, we compare AdaBoostR and Real AdaBoost with Projected PEC , obtained by applying the quasiprobability sampling overhead to the target-reaching reference trajectory. We additionally simulate explicit stochastic Sampled PEC in selected settings to test the projected resource model. Boosting requires fewer circuit executions than Projected PEC in 39 of the 56 reported comparisons. For the classification target, its advantage generally grows with physical noise strength and circuit depth, although the depth dependence is not monotonic. In all 36 comparisons the median difference in test accuracy also favours boosting over the corresponding reference.
Related work. Ensembles of noisy variational quantum classifiers have already been studied. Li et al. combine shallow classifiers using bagging and adaptive boosting and compare their predictive performance with error-mitigated primitive classifiers [13 ] . Wang et al. derive a supervised-learning guarantee for quantum AdaBoost and report settings in which a noisy boosted classifier outperforms a noiseless unboosted classifier [26 ] . Chen et al. introduce AdaBoost.Q and experimentally demonstrate improved quantum-classifier performance on a programmable superconducting processor [6 ] . In contrast, the focus here is the circuit-execution cost of reaching matched learning targets.
Our main contributions are:
A common margin-based framework for comparing PEC and boosting. We place both strategies under the same margin-based generalization criterion, so reaching the same empirical margin-loss target implies the same high-probability upper bound on expected classification risk.
Resource criteria for reaching the common learning target. We express the PEC cost through its quasiprobability sampling overhead and derive the corresponding boosting conditions in terms of the weak-learner edges and, for AdaBoostR, the realized coefficient trajectory.
A finite-shot numerical comparison across circuit depth and physical noise. We compare AdaBoostR and Real AdaBoost with Projected PEC under both the theoretical positive-margin criterion and a matched classification criterion, and validate the Projected-PEC resource model using Sampled PEC in selected settings.
Throughout this work, we restrict the analysis to binary classification. The paper is organized as follows:
Background (§ 2 ). We introduce PEC, the two boosting algorithms, and the margin-based generalization tools used in the comparison.
Learning setup (§ 3 ). We specify the binary-classification problem, the common learning target, and the noiseless-reference resource budget. This fixes what the methods must achieve and which resources are compared.
PEC resources (§ 4 ). We estimate the cost of training with PEC by accounting for the additional measurements needed to recover noiseless circuit outputs. We explain how this cost changes with circuit depth and noise strength.
Boosting resource bounds (§ 5 ). We derive sufficient conditions for reaching the empirical margin loss target for Real AdaBoost and AdaBoostR.
Common theoretical comparison (§ 6 ). We bring the preceding results together in our central theoretical contribution: a theorem comparing the resources needed by PEC and boosting to meet the same learning target. Under the stated assumptions, it gives conditions under which combining noisy predictors can require fewer circuit executions than the PEC budget derived earlier.
Numerical comparison (§ 7 ). Finite-shot simulations compare resource costs to reach learning targets. We identify depth–noise regimes favouring each method, examine test performance and the tightness of the theoretical bounds.
Discussion and conclusions (§ 8 and § 9 ). We summarize the observed resource advantages and identify open questions.
Background
PAC Learning Framework
We briefly recall the Probably Approximately Correct (PAC) learning framework in the realizable setting [24 , 11 ] , which formalizes the notions of weak and strong learnability underlying boosting theory.
Let n n n denote a problem size (e.g. number of qubits, input dimension, circuit size), X ⊆ R N \mathcal{X} \subseteq\mathbb{R}^{N} X ⊆ R N define the input space and C ⊆ { c : X → { − 1 , + 1 } } \mathcal{C} \subseteq\{c:\mathcal{X}\to\{-1,+1\}\} C ⊆ { c : X → { − 1 , + 1 }} be a concept class consisting of binary labeling functions, where N ( n ) N(n) N ( n ) is polynomially bounded in n n n . Training examples are generated by drawing inputs x ∼ D x \sim\mathcal{D} x ∼ D independently from an unknown but fixed distribution D \mathcal{D} D over X \mathcal{X} X and assigning labels deterministically according to y = c ( x ) y=c(x) y = c ( x ) .
Given the above and a labeled sample S = { ( x i , c ( x i ) ) } i = 1 m ( n ) S=\{(x_i,c(x_i))\}_{i=1}^{m(n)} S = {( x i , c ( x i )) } i = 1 m ( n ) , the goal of a learning algorithm is to output a hypothesis h : X → { − 1 , + 1 } h:\mathcal{X}\to\{-1,+1\} h : X → { − 1 , + 1 } that generalizes well to new samples drawn from the same distribution D \mathcal{D} D .
Definition 1. (Efficient Weak Learner) Let C \mathcal{C} C be a concept class over X ⊆ R N \mathcal{X}\subseteq\mathbb{R}^{N} X ⊆ R N . A (possibly randomized) learning algorithm A \mathcal{A} A is called an efficient weak learner for C \mathcal{C} C if there exist polynomials p p p and q q q such that for every distribution D \mathcal{D} D over X \mathcal{X} X , every target concept c ∈ C c\in\mathcal{C} c ∈ C , and every confidence parameter δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , the following holds:
Given m = p ( n , 1 δ ) m = p(n, \frac{1}{\delta}) m = p ( n , δ 1 ) i.i.d. labeled samples S = { ( x i , c ( x i ) ) } i = 1 m S = \{(x_i,c(x_i))\}_{i=1}^m S = {( x i , c ( x i )) } i = 1 m with x i ∼ D x_i \sim\mathcal{D} x i ∼ D on input, the algorithm A \mathcal{A} A runs in time polynomial in n n n and 1 / δ 1/\delta 1/ δ and outputs, with probability at least 1 − δ 1-\delta 1 − δ , a hypothesis h h h such that
Pr x ∼ D [ h ( x ) = c ( x ) ] ≥ 1 2 + η P A C , η P A C = 1 q ( n ) . (1) \Pr_{x\sim\mathcal{D}}[h(x)=c(x)] \ge\frac{1}{2}+\eta_{\mathrm{PAC}}, \qquad\eta_{\mathrm{PAC}}=\frac{1}{q(n)}. \tag*{(1)} x ∼ D Pr [ h ( x ) = c ( x )] ≥ 2 1 + η PAC , η PAC = q ( n ) 1 . (1)
The quantity η P A C \eta_{\mathrm{PAC}} η PAC is the advantage in classification accuracy over random guessing.
Definition 2. (Efficient Strong Learner) Let C \mathcal{C} C be a concept class over X ⊆ R N \mathcal{X} \subseteq\mathbb{R}^N X ⊆ R N . A (possibly randomized) learning algorithm A \mathcal{A} A is called an efficient strong learner for C \mathcal{C} C if there exist polynomial p p p such that for every accuracy parameter ϵ ∈ ( 0 , 1 ) \epsilon\in(0,1) ϵ ∈ ( 0 , 1 ) , every confidence parameter δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , every distribution D \mathcal{D} D over X \mathcal{X} X , and every target concept c ∈ C c \in\mathcal{C} c ∈ C , the following holds:
Given m = p ( n , 1 ϵ , 1 δ ) m = p(n,\frac{1}{\epsilon},\frac{1}{\delta}) m = p ( n , ϵ 1 , δ 1 ) i.i.d. labeled samples S = { ( x i , c ( x i ) ) } i = 1 m S = \{(x_i,c(x_i))\}_{i=1}^m S = {( x i , c ( x i )) } i = 1 m with x i ∼ D x_i \sim\mathcal{D} x i ∼ D on input, the algorithm A \mathcal{A} A runs in time polynomial in n n n , 1 / ϵ 1/\epsilon 1/ ϵ , and 1 / δ 1/\delta 1/ δ and outputs, with probability at least 1 − δ 1-\delta 1 − δ , a hypothesis h h h such that
Pr x ∼ D [ h ( x ) = c ( x ) ] ≥ 1 − ϵ (2) \Pr_{x\sim\mathcal{D}}[h(x)=c(x)] \ge1-\epsilon \tag*{(2)} x ∼ D Pr [ h ( x ) = c ( x )] ≥ 1 − ϵ (2)
The relevant distinction between definitions 1 and 2 is that a strong learner can reach an arbitrarily small classification error ϵ \epsilon ϵ (expected risk), whereas a weak learner is guaranteed only an inverse-polynomial advantage over random guessing. A foundational result showed that any concept class that is efficiently weakly learnable in the PAC model is also efficiently strongly learnable [19 ] . Boosting algorithms give constructive procedures for combining repeated outputs of a weak learner into a strong classifier [8 ] .
These PAC definitions provide the weak-learning terminology used in our boosting analysis. In this work, however, the resource comparison is carried out for fixed classification tasks rather than by proving distribution-free efficient learnability of the PQC hypothesis class. In the theoretical analysis, we assume that the noisy PQC weak learners attain a positive edge under the successive reweighted training distributions. In the numerical study, we then train these weak learners explicitly and measure the circuit resources required to reach the same task-specific learning target as the reference procedure. PEC needs additional circuit executions to approximate the expectation values produced by the noiseless reference procedure. Boosting, on the other hand, uses circuit executions to train and combine noisy classifiers that satisfy the weak-learning condition. This distinction forms the basis of the resource comparison developed later in § 6 .
Probabilistic Error Cancellation
Quantum error mitigation (QEM) techniques aim to reduce the effect of noise in near-term quantum devices without implementing full quantum error correction. Several QEM methods aim to estimate quantities associated with an ideal computation from noisy circuit executions. Here we focus on probabilistic error cancellation (PEC), which constructs unbiased estimators of ideal expectation values through quasiprobability sampling [22 , 7 ] .
Let h n o i s e l e s s ( x ) = tr ( O ρ n o i s e l e s s ( x ) ) h^{\mathrm{noiseless}}(x) = \operatorname{tr}(\mathcal{O}\rho^{\mathrm{noiseless}}(x)) h noiseless ( x ) = tr ( O ρ noiseless ( x )) denote the noiseless PQC expectation for an observable satisfying ∥ O ∥ ∞ ≤ 1 \lVert\mathcal{O} \rVert_\infty\le1 ∥ O ∥ ∞ ≤ 1 . PEC represents the noiseless channel as a linear combination of implementable noisy channels { O ν } \{\mathcal{O}_\nu\} { O ν } :
U ( ⋅ ) = ∑ ν ζ ν O ν ( ⋅ ) , γ : = ∑ ν ∣ ζ ν ∣ ≥ 1 , ζ ν ∈ R (3) \mathcal{U}(\cdot) = \sum_{\nu} \zeta_\nu\mathcal{O}_\nu(\cdot), \qquad\gamma:= \sum_{\nu} |\zeta_\nu| \ge1, \qquad\zeta_\nu\in\mathbb{R} \tag*{(3)} U ( ⋅ ) = ν ∑ ζ ν O ν ( ⋅ ) , γ := ν ∑ ∣ ζ ν ∣ ≥ 1 , ζ ν ∈ R (3)
where γ \gamma γ is the ℓ 1 \ell_1 ℓ 1 norm of the quasiprobability coefficients in the circuit-level decomposition. In a gatewise implementation of PEC, each noiseless gate channel U g \mathcal{U}_g U g at location g ∈ [ G ] g \in[G] g ∈ [ G ] is decomposed as
U g = ∑ ν g ζ g , ν g O g , ν g , γ g = ∑ ν g ∣ ζ g , ν g ∣ . \mathcal{U}_g = \sum_{\nu_g} \zeta_{g,\nu_g}\mathcal{O}_{g,\nu_g}, \qquad\gamma_g = \sum_{\nu_g} |\zeta_{g,\nu_g}|. U g = ν g ∑ ζ g , ν g O g , ν g , γ g = ν g ∑ ∣ ζ g , ν g ∣.
The complete sampled circuit is indexed by ν = ( ν 1 , … , ν G ) \boldsymbol{\nu} = (\nu_1,\ldots,\nu_G) ν = ( ν 1 , … , ν G ) , where G G G is the number of noisy gate locations. Its quasiprobability norm is
γ = ∏ g = 1 G γ g . (4) \gamma= \prod_{g=1}^{G} \gamma_g. \tag*{(4)} γ = g = 1 ∏ G γ g . (4)
A single PEC sample is constructed by drawing a complete circuit index ν \nu ν with probability
p ν = ∣ ζ ν ∣ γ , ζ ν = ∏ g = 1 G ζ g , ν g , p_{\nu} = \frac{|\zeta_{\nu}|}{\gamma}, \qquad\zeta_{\nu} = \prod_{g=1}^{G} \zeta_{g,\nu_g}, p ν = γ ∣ ζ ν ∣ , ζ ν = g = 1 ∏ G ζ g , ν g ,
executing the corresponding noisy circuit O ν \mathcal{O}_{\nu} O ν , and measuring O O O to obtain an outcome Z ν ∈ [ − 1 , 1 ] Z_{\nu} \in[-1,1] Z ν ∈ [ − 1 , 1 ] . The reweighted outcome is
Z ^ P E C = γ sign ( ζ ν ) Z ν . (5) \widehat{Z}_{\mathrm{PEC}} = \gamma\operatorname{sign}(\zeta_{\nu}) Z_{\nu}. \tag*{(5)} Z PEC = γ sign ( ζ ν ) Z ν . (5)
The empirical PEC estimator based on N s h N_{\mathrm{sh}} N sh shots is
h ^ P E C ( x ) = 1 N s h ∑ k = 1 N s h Z ^ P E C ( k ) (6) \widehat{h}_{\mathrm{PEC}}(x) = \frac{1}{N_{\mathrm{sh}}} \sum_{k=1}^{N_{\mathrm{sh}}} \widehat{Z}_{\mathrm{PEC}}^{(k)} \tag*{(6)} h PEC ( x ) = N sh 1 k = 1 ∑ N sh Z PEC ( k ) (6)
Provided that the quasiprobability decomposition is constructed from an accurate description of the physical noisy operations, the estimator is unbiased:
E [ h ^ P E C ( x ) ] = h θ n o i s e l e s s ( x ) (7) \mathbb{E}\left[\widehat{h}_{\mathrm{PEC}}(x)\right] = h_{\theta}^{\mathrm{noiseless}}(x) \tag*{(7)} E [ h PEC ( x ) ] = h θ noiseless ( x ) (7)
Since Z ∈ [ − 1 , 1 ] Z \in[-1,1] Z ∈ [ − 1 , 1 ] , the reweighted PEC outcomes satisfy Z ^ P E C ∈ [ − γ , γ ] \widehat{Z}_{\mathrm{PEC}} \in[-\gamma,\gamma] Z PEC ∈ [ − γ , γ ] . Thus, PEC enlarges the range of a single measurement outcome by a factor γ \gamma γ and the variance scale by γ 2 \gamma^2 γ 2 :
E [ ( Z ^ P E C ) 2 ] ≤ γ 2 , Var ( Z ^ P E C ) ≤ γ 2 . (8) \mathbb{E}\left[\left(\widehat{Z}_{\mathrm{PEC}}\right)^2\right] \leq\gamma^2, \qquad\operatorname{Var}\left(\widehat{Z}_{\mathrm{PEC}}\right) \leq\gamma^2. \tag*{(8)} E [ ( Z PEC ) 2 ] ≤ γ 2 , Var ( Z PEC ) ≤ γ 2 . (8)
Because the PEC samples are independent and bounded, Hoeffding’s inequality applies. For any ϵ > 0 \epsilon> 0 ϵ > 0 and confidence parameter δ s h ∈ ( 0 , 1 ) \delta_{\mathrm{sh}} \in(0,1) δ sh ∈ ( 0 , 1 ) ,
Pr ( ∣ h ^ P E C ( x ) − h θ n o i s e l e s s ( x ) ∣ ≥ ϵ ) ≤ 2 exp ( − 2 N s h ϵ 2 ( 2 γ ) 2 ) (9) \Pr\left(\left|\widehat{h}_{\mathrm{PEC}}(x) - h_{\theta}^{\mathrm{noiseless}}(x)\right| \geq\epsilon\right) \leq2\exp\left(-\frac{2N_{\mathrm{sh}}\epsilon^2}{(2\gamma)^2}\right) \tag*{(9)} Pr ( h PEC ( x ) − h θ noiseless ( x ) ≥ ϵ ) ≤ 2 exp ( − ( 2 γ ) 2 2 N sh ϵ 2 ) (9)
It therefore suffices to choose
N s h P E C ≥ 2 γ 2 ϵ 2 log 2 δ s h . (10) N_{\mathrm{sh}}^{\mathrm{PEC}} \geq\frac{2\gamma^2}{\epsilon^2}\log\frac{2}{\delta_{\mathrm{sh}}}. \tag*{(10)} N sh PEC ≥ ϵ 2 2 γ 2 log δ sh 2 . (10)
shots to estimate each expectation value within accuracy ϵ \epsilon ϵ with confidence 1 − δ s h 1-\delta_{\mathrm{sh}} 1 − δ sh .
The number of circuit executions required to achieve fixed additive precision and confidence therefore scales as γ 2 \gamma^2 γ 2 . Under the gate-wise construction,
γ 2 = ∏ g = 1 G γ g 2 . (11) \gamma^2 = \prod_{g=1}^{G}\gamma_g^2. \tag*{(11)} γ 2 = g = 1 ∏ G γ g 2 . (11)
Consequently, if the gate-level norms are bounded below by a constant greater than one, the PEC sampling cost grows exponentially with the number of noisy gates and hence, for fixed-width layered circuits, with circuit depth [22 , 7 , 23 ] .
Importantly, the γ 2 \gamma^2 γ 2 factor is the sampling overhead incurred when the ideal expectation value is estimated using PEC. In some special circuit families, the same ideal expectation value can instead be computed efficiently by a different method. For example, if the circuit is efficiently classically simulable, one may compute the ideal expectation value directly and bypass PEC altogether. This does not make PEC itself require fewer samples; it removes the need to use PEC for that problem.
In the context of supervised learning with PQCs, PEC can therefore be interpreted as using noisy circuit executions to estimate the expectation values of the ideal PQC hypothesis class, with a multiplicative shot overhead determined by γ 2 \gamma^2 γ 2 . This perspective will serve as the reference point for our subsequent comparison with boosting-based strategies.
Boosting Framework
Let S = { ( x i , y i ) } i = 1 m \mathcal{S} = \{(x_i,y_i)\}_{i=1}^{m} S = {( x i , y i ) } i = 1 m be a fixed training dataset drawn i.i.d. from a distribution D \mathcal{D} D over X ⊆ R N \mathcal{X} \subseteq\mathbb{R}^{N} X ⊆ R N . Boosting constructs an ensemble predictor by repeatedly invoking a weak learner on reweighted versions of the fixed training sample. According to § 2.1 , we use weak learner for the learning procedure and weak hypothesis for the function returned by that procedure. We first introduce the notation and ingredients common to both boosting methods considered in this work; their algorithm-specific coefficients and reweighting rules are defined separately below.
The procedure operates in rounds t = 1 , 2 , … , T t=1,2,\ldots,T t = 1 , 2 , … , T . At each round, it maintains a distribution D t \mathcal{D}^{t} D t over the indices of the fixed training sample S \mathcal{S} S . Initially,
D 1 ( i ) = 1 m , i = 1 , … , m . (12) \mathcal{D}^{1}(i)=\frac{1}{m}, \qquad i=1,\ldots,m. \tag*{(12)} D 1 ( i ) = m 1 , i = 1 , … , m . (12)
As boosting proceeds, the distribution is updated so that training examples that are handled poorly by the current ensemble receive greater importance in subsequent rounds. The distribution D t \mathcal{D}^{t} D t is therefore a discrete reweighting of the fixed sample S \mathcal{S} S and should not be confused with the underlying data-generating distribution D \mathcal{D} D , which remains fixed throughout boosting.
At round t t t , the weak learner is trained according to the distribution D t \mathcal{D}^{t} D t and returns a weak hypothesis
h t : X → [ − 1 , 1 ] . h_t:\mathcal{X}\to[-1,1]. h t : X → [ − 1 , 1 ] .
In our setting, h t h_t h t is realized by a noisy parameterized quantum circuit (PQC) of fixed ansatz depth trained for a bounded number of optimization epochs. For fixed trained parameters, the circuit defines the mean prediction
h t ( x ) : = E s h o t s [ h ^ t ( x ) ] ∈ [ − 1 , 1 ] , (13) h_t(x):=\mathbb{E}_{\mathrm{shots}}\left[\widehat{h}_t(x)\right]\in[-1,1], \tag*{(13)} h t ( x ) := E shots [ h t ( x ) ] ∈ [ − 1 , 1 ] , (13)
where h ^ t ( x ) \widehat{h}_t(x) h t ( x ) is the corresponding finite-shot estimate. The bound h t ( x ) ∈ [ − 1 , 1 ] h_t(x)\in[-1,1] h t ( x ) ∈ [ − 1 , 1 ] follows from measuring an observable O O O satisfying ∥ O ∥ ∞ ≤ 1 \lVert O\rVert_{\infty}\leq1 ∥ O ∥ ∞ ≤ 1 . The boosting analysis below is formulated in terms of the deterministic mean hypotheses h t h_t h t , whereas h ^ t \widehat{h}_t h t is random because it is obtained from a finite number of measurement shots. The finite-shot accuracy required to estimate the quantities entering the boosting procedure is treated separately in the resource analysis.
Following the confidence-rated prediction formalism [20 ] , a real-valued weak hypothesis h t : X → [ − 1 , 1 ] h_t:\mathcal{X}\to[-1,1] h t : X → [ − 1 , 1 ] retains both the predicted class and the magnitude of its prediction: sign ( h t ( x ) ) \operatorname{sign}(h_t(x)) sign ( h t ( x )) determines the predicted label, while ∣ h t ( x ) ∣ \lvert h_t(x)\rvert ∣ h t ( x )∣ is the confidence rating used by the boosting rule. Thus, the real-valued hypothesis is combined directly rather than being thresholded to { − 1 , + 1 } \{-1,+1\} { − 1 , + 1 } before constructing the ensemble.
We define the empirical edge of h t h_t h t under the current distribution D t \mathcal{D}^{t} D t as
r t : = ∑ i = 1 m D t ( i ) y i h t ( x i ) . (14) r_t:=\sum_{i=1}^{m}\mathcal{D}^{t}(i)y_i h_t(x_i). \tag*{(14)} r t := i = 1 ∑ m D t ( i ) y i h t ( x i ) . (14)
For each training example, y i h t ( x i ) y_i h_t(x_i) y i h t ( x i ) is positive when the predicted sign agrees with the label and negative when it does not. Hence r t r_t r t is the D t \mathcal{D}^{t} D t -weighted average of these signed prediction values.
To connect this definition with the PAC weak-learning edge introduced in § 2.1 , consider the special case in which the weak hypothesis is binary-valued on the training sample, h t ( x i ) ∈ { − 1 , + 1 } h_t(x_i)\in\{-1,+1\} h t ( x i ) ∈ { − 1 , + 1 } . Define its weighted classification error by
ϵ t : = ∑ i = 1 m D t ( i ) I { h t ( x i ) ≠ y i } , (15) \epsilon_t:=\sum_{i=1}^{m}\mathcal{D}^{t}(i)\mathbb{I}\{h_t(x_i)\ne y_i\}, \tag*{(15)} ϵ t := i = 1 ∑ m D t ( i ) I { h t ( x i ) = y i } , (15)
where I { A } = 1 \mathbb{I}\{A\}=1 I { A } = 1 when A A A is true and 0 0 0 otherwise. In this binary case, y i h t ( x i ) = + 1 y_i h_t(x_i)=+1 y i h t ( x i ) = + 1 on correctly classified examples and y i h t ( x i ) = − 1 y_i h_t(x_i)=-1 y i h t ( x i ) = − 1 on incorrectly classified examples. Therefore,
r t = ( 1 − ϵ t ) − ϵ t = 1 − 2 ϵ t . (16) r_t=(1-\epsilon_t)-\epsilon_t=1-2\epsilon_t. \tag*{(16)} r t = ( 1 − ϵ t ) − ϵ t = 1 − 2 ϵ t . (16)
Consequently,
r t 2 = 1 2 − ϵ t . \frac{r_t}{2}=\frac{1}{2}-\epsilon_t. 2 r t = 2 1 − ϵ t .
which is the fixed-sample, round-dependent analogue of the PAC accuracy advantage η P A C \eta_{\mathrm{PAC}} η PAC . In particular, r t > 0 r_t > 0 r t > 0 is equivalent to weighted classification accuracy greater than 1 / 2 1/2 1/2 in this binary special case.
For the real-valued hypotheses used in this work, h t ( x i ) ∈ [ − 1 , 1 ] h_t(x_i) \in[-1,1] h t ( x i ) ∈ [ − 1 , 1 ] , this equivalence no longer holds because r t r_t r t depends also on the magnitudes of the predictions. We therefore work directly with the real-valued edge in Eq. (14) .
Both boosting methods below use the same sign convention. If a trained weak hypothesis has r t < 0 r_t < 0 r t < 0 , we replace h t h_t h t by − h t -h_t − h t , changing its edge from r t r_t r t to − r t > 0 -r_t > 0 − r t > 0 . For the noisy-PQC hypotheses considered here, this operation is purely classical post-processing of already evaluated predictions and requires neither retraining nor additional circuit executions. The convergence analyses below concern the positive-edge regime 0 < r t < 1 0 < r_t < 1 0 < r t < 1 .
After obtaining the weak hypothesis, the boosting algorithm assigns it a coefficient and updates the distribution over the training examples. These steps are algorithm dependent: Real AdaBoost uses the confidence-rated hypothesis directly, whereas AdaBoostR first normalizes the weak hypothesis on the training sample. Their respective coefficients and reweighting rules are defined in the following subsections.
After T T T rounds, the ensemble score and associated classifier are
F T ( x ) = ∑ t = 1 T α t h t ( x ) , H T ( x ) = sign ( F T ( x ) ) . (17) F_T(x) = \sum_{t=1}^{T} \alpha_t h_t(x), \qquad H_T(x) = \operatorname{sign}(F_T(x)). \tag*{(17)} F T ( x ) = t = 1 ∑ T α t h t ( x ) , H T ( x ) = sign ( F T ( x )) . (17)
We now specialize this common framework to two boosting algorithms for real-valued weak hypotheses: Real AdaBoost [20 ] and AdaBoostR [16 ] . Both are compatible with bounded PQC prediction functions h t : X → [ − 1 , 1 ] h_t : \mathcal{X} \to[-1,1] h t : X → [ − 1 , 1 ] , which arise naturally as expectation values of bounded observables.
Real AdaBoost with Confidence-Rated Predictions. We first consider Real AdaBoost with confidence-rated predictions in the formulation [20 ] . In the general boosting framework above, the coefficient α t \alpha_t α t assigned to the new weak hypothesis and the update of the sample weights were left unspecified. Real AdaBoost chooses these quantities so that adding the new hypothesis reduces the exponential loss of the ensemble on the training sample.
Let
F t − 1 ( x ) = ∑ s = 1 t − 1 α s h s ( x ) (18) F_{t-1}(x) = \sum_{s=1}^{t-1} \alpha_s h_s(x) \tag*{(18)} F t − 1 ( x ) = s = 1 ∑ t − 1 α s h s ( x ) (18)
denote the ensemble score before round t t t , with F 0 ( x ) = 0 F_0(x) = 0 F 0 ( x ) = 0 . Real AdaBoost measures its training performance through the exponential potential
Φ t − 1 : = ∑ i = 1 m exp ( − y i F t − 1 ( x i ) ) . (19) \Phi_{t-1} := \sum_{i=1}^{m} \exp(-y_i F_{t-1}(x_i)). \tag*{(19)} Φ t − 1 := i = 1 ∑ m exp ( − y i F t − 1 ( x i )) . (19)
An example with a negative or small ensemble margin y i F t − 1 ( x i ) y_i F_{t-1}(x_i) y i F t − 1 ( x i ) contributes more strongly to Φ t − 1 \Phi_{t-1} Φ t − 1 than an example that is classified correctly with high confidence.
The distribution used to train the next weak hypothesis is obtained by normalizing these contributions:
D t ( i ) = exp ( − y i F t − 1 ( x i ) ) Φ t − 1 . (20) D^t(i) = \frac{\exp(-y_i F_{t-1}(x_i))}{\Phi_{t-1}}. \tag*{(20)} D t ( i ) = Φ t − 1 exp ( − y i F t − 1 ( x i )) . (20)
For F 0 = 0 F_0 = 0 F 0 = 0 , one has Φ 0 = m \Phi_0 = m Φ 0 = m and therefore D 1 ( i ) = 1 / m D^1(i) = 1/m D 1 ( i ) = 1/ m .
At round t t t , the weak learner returns a confidence-rated hypothesis h t : X → [ − 1 , 1 ] h_t : \mathcal{X} \to[-1,1] h t : X → [ − 1 , 1 ] . Let r t r_t r t denote its empirical edge under D t D^t D t , as defined in Eq. (14) . Suppose that h t h_t h t is added to the ensemble with a candidate coefficient α \alpha α . The resulting exponential potential is
Φ t ( α ) : = ∑ i = 1 m exp ( − y i ( F t − 1 ( x i ) + α h t ( x i ) ) ) = Φ t − 1 ∑ i = 1 m D t ( i ) exp ( − α y i h t ( x i ) ) . (21) \Phi_t(\alpha) := \sum_{i=1}^{m} \exp\left(-y_i\left(F_{t-1}(x_i) + \alpha h_t(x_i)\right)\right) = \Phi_{t-1} \sum_{i=1}^{m} D^t(i) \exp\left(-\alpha y_i h_t(x_i)\right). \tag*{(21)} Φ t ( α ) := i = 1 ∑ m exp ( − y i ( F t − 1 ( x i ) + α h t ( x i ) ) ) = Φ t − 1 i = 1 ∑ m D t ( i ) exp ( − α y i h t ( x i ) ) . (21)
This motivates the definition
Z t ( α ) : = ∑ i = 1 m D t ( i ) exp ( − α y i h t ( x i ) ) . (22) Z_t(\alpha) := \sum_{i=1}^{m} D^t(i) \exp\left(-\alpha y_i h_t(x_i)\right). \tag*{(22)} Z t ( α ) := i = 1 ∑ m D t ( i ) exp ( − α y i h t ( x i ) ) . (22)
Equation (21) gives
Z t ( α ) = Φ t ( α ) Φ t − 1 . (23) Z_t(\alpha)=\frac{\Phi_t(\alpha)}{\Phi_{t-1}}. \tag*{(23)} Z t ( α ) = Φ t − 1 Φ t ( α ) . (23)
Thus, Z t ( α ) Z_t(\alpha) Z t ( α ) is the factor by which the exponential training potential changes after adding α h t \alpha h_t α h t to the current ensemble. In particular, Z t ( α ) < 1 Z_t(\alpha)<1 Z t ( α ) < 1 means that the new hypothesis decreases the exponential training potential.
For the positive-edge regime 0 < r t < 1 0<r_t<1 0 < r t < 1 , used in the convergence analysis, [20 ] show that
Z t ( α ) ≤ 1 − r t 2 e α + 1 + r t 2 e − α . (24) Z_t(\alpha)\le\frac{1-r_t}{2}e^\alpha+\frac{1+r_t}{2}e^{-\alpha}. \tag*{(24)} Z t ( α ) ≤ 2 1 − r t e α + 2 1 + r t e − α . (24)
Although r t r_t r t is computed from the current weights D t D^t D t , the labels, and the weak-hypothesis values h t ( x i ) h_t(x_i) h t ( x i ) , the bound above depends on these quantities only through r t r_t r t . The right-hand side is minimized by
α t = 1 2 log ( 1 + r t 1 − r t ) , 0 < r t < 1. (25) \alpha_t=\frac{1}{2}\log\left(\frac{1+r_t}{1-r_t}\right),\qquad0<r_t<1. \tag*{(25)} α t = 2 1 log ( 1 − r t 1 + r t ) , 0 < r t < 1. (25)
Since 0 < r t < 1 0<r_t<1 0 < r t < 1 , the denominator 1 − r t 1-r_t 1 − r t is positive and
1 + r t 1 − r t > 1 , \frac{1+r_t}{1-r_t}>1, 1 − r t 1 + r t > 1 ,
so α t > 0 \alpha_t>0 α t > 0 . Substituting (25) into (24) yields
Z t ( α t ) ≤ 1 − r t 2 < 1. (26) Z_t(\alpha_t)\le\sqrt{1-r_t^2}<1. \tag*{(26)} Z t ( α t ) ≤ 1 − r t 2 < 1. (26)
Hence, every accepted positive-edge hypothesis reduces the exponential training potential by a factor of at most 1 − r t 2 \sqrt{1-r_t^2} 1 − r t 2 .
For binary-valued hypotheses h t ( x i ) ∈ { − 1 , + 1 } h_t(x_i)\in\{-1,+1\} h t ( x i ) ∈ { − 1 , + 1 } , the inequality in (24) is attained exactly, and therefore
Z t ( α t ) = 1 − r t 2 . (27) Z_t(\alpha_t)=\sqrt{1-r_t^2}. \tag*{(27)} Z t ( α t ) = 1 − r t 2 . (27)
Using the coefficient (25) , the sample weights are updated according to
D t + 1 ( i ) = D t ( i ) exp ( − α t y i h t ( x i ) ) Z t ( α t ) . (28) D^{t+1}(i)=\frac{D^t(i)\exp(-\alpha_t y_i h_t(x_i))}{Z_t(\alpha_t)}. \tag*{(28)} D t + 1 ( i ) = Z t ( α t ) D t ( i ) exp ( − α t y i h t ( x i )) . (28)
To interpret the update, define the signed score s t , i : = y i h t ( x i ) s_{t,i}:=y_i h_t(x_i) s t , i := y i h t ( x i ) . Equation (28) gives
D t + 1 ( i ) D t ( i ) = exp ( − α t s t , i ) Z t ( α t ) . (29) \frac{D^{t+1}(i)}{D^t(i)}=\frac{\exp(-\alpha_t s_{t,i})}{Z_t(\alpha_t)}. \tag*{(29)} D t ( i ) D t + 1 ( i ) = Z t ( α t ) exp ( − α t s t , i ) . (29)
Since α t > 0 \alpha_t>0 α t > 0 , the factor exp ( − α t s t , i ) \exp(-\alpha_t s_{t,i}) exp ( − α t s t , i ) decreases as the signed score increases. Therefore, examples with smaller signed scores are emphasized relative to examples with larger signed scores.
More precisely, define
ϑ t : = − 1 α t log Z t ( α t ) . (30) \vartheta_t:=-\frac{1}{\alpha_t}\log Z_t(\alpha_t). \tag*{(30)} ϑ t := − α t 1 log Z t ( α t ) . (30)
Because Z t ( α t ) < 1 Z_t(\alpha_t)<1 Z t ( α t ) < 1 , one has ϑ t > 0 \vartheta_t>0 ϑ t > 0 . It follows from (29) that
{ D t + 1 ( i ) > D t ( i ) , s t , i < ϑ t , D t + 1 ( i ) = D t ( i ) , s t , i = ϑ t , D t + 1 ( i ) < D t ( i ) , s t , i > ϑ t . (31) \begin{cases}
D^{t+1}(i)>D^t(i), & s_{t,i}<\vartheta_t,\\
D^{t+1}(i)=D^t(i), & s_{t,i}=\vartheta_t,\\
D^{t+1}(i)<D^t(i), & s_{t,i}>\vartheta_t. \tag*{(31)}
\end{cases} ⎩ ⎨ ⎧ D t + 1 ( i ) > D t ( i ) , D t + 1 ( i ) = D t ( i ) , D t + 1 ( i ) < D t ( i ) , s t , i < ϑ t , s t , i = ϑ t , s t , i > ϑ t . (31)
Thus, every wrong-sign prediction, for which s t , i < 0 s_{t,i}<0 s t , i < 0 , receives greater weight. A correctly signed but low-confidence prediction may also receive greater weight when its signed score lies below ϑ t \vartheta_t ϑ t , whereas a sufficiently confident correct prediction receives less weight.
The complete procedure is summarized in Algorithm 1. The update rule below is stated for the regime 0 < r t < 1 0<r_t<1 0 < r t < 1 used in the theoretical analysis. Numerical handling of the endpoint r t = 1 r_t=1 r t = 1 is specified separately in the implementation protocol.
Algorithm 1 Real AdaBoost with confidence-rated predictions
Input: weak learner A \mathcal{A} A , sample S = { ( x i , y i ) } i = 1 m \mathcal{S} = \{(x_i,y_i)\}_{i=1}^{m} S = {( x i , y i ) } i = 1 m , number of rounds T T T
Initialize: D 1 ( i ) = 1 / m D^1(i) = 1/m D 1 ( i ) = 1/ m for every i ∈ [ m ] i \in[m] i ∈ [ m ] and F 0 ( x ) = 0 F_0(x) = 0 F 0 ( x ) = 0 .
for t = 1 t = 1 t = 1 to T T T do
Invoke A \mathcal{A} A with respect to D t D^t D t to obtain h t : X → [ − 1 , 1 ] h_t : \mathcal{X} \to[-1,1] h t : X → [ − 1 , 1 ] .
Compute the raw edge
r t r a w = ∑ i = 1 m D t ( i ) y i h t ( x i ) . r_t^{\mathrm{raw}} = \sum_{i=1}^{m} D^t(i)y_i h_t(x_i). r t raw = i = 1 ∑ m D t ( i ) y i h t ( x i ) .
if r t r a w < 0 r_t^{\mathrm{raw}} < 0 r t raw < 0 then
Replace h t = − h t h_t = -h_t h t = − h t .
end if
Set
r t = ∣ r t r a w ∣ . r_t = \lvert r_t^{\mathrm{raw}}\rvert. r t = ∣ r t raw ∣ .
Set
α t = 1 2 log ( 1 + r t 1 − r t ) . \alpha_t = \frac{1}{2}\log\left(\frac{1+r_t}{1-r_t}\right). α t = 2 1 log ( 1 − r t 1 + r t ) .
Update, for every i ∈ [ m ] i \in[m] i ∈ [ m ] ,
D t + 1 ( i ) = D t ( i ) exp ( − α t y i h t ( x i ) ) Z t ( α t ) . D^{t+1}(i) = \frac{D^t(i)\exp(-\alpha_t y_i h_t(x_i))}{Z_t(\alpha_t)}. D t + 1 ( i ) = Z t ( α t ) D t ( i ) exp ( − α t y i h t ( x i )) .
Set
F t ( x ) = F t − 1 ( x ) + α t h t ( x ) . F_t(x) = F_{t-1}(x) + \alpha_t h_t(x). F t ( x ) = F t − 1 ( x ) + α t h t ( x ) .
end for
Return
F T ( x ) = ∑ t = 1 T α t h t ( x ) , H T ( x ) = sign ( F T ( x ) ) . F_T(x) = \sum_{t=1}^{T}\alpha_t h_t(x), \qquad H_T(x) = \operatorname{sign}(F_T(x)). F T ( x ) = t = 1 ∑ T α t h t ( x ) , H T ( x ) = sign ( F T ( x )) .
AdaBoostR with Rational Reweighting. We next consider the rational-update boosting algorithm denoted by AdaBoostR throughout this work. AdaBoostR first normalizes the real-valued weak hypothesis on the training sample and then updates the weights using a rational function of its signed scores.
At round t t t , the weak learner returns a real-valued hypothesis h t : X → [ − 1 , 1 ] h_t : \mathcal{X} \to[-1,1] h t : X → [ − 1 , 1 ] . To separate the direction of its predictions from their overall scale on the training sample, define
h t ∗ : = max i ∈ [ m ] ∣ h t ( x i ) ∣ . (32) h_t^* := \max_{i\in[m]} \lvert h_t(x_i)\rvert. \tag*{(32)} h t ∗ := i ∈ [ m ] max ∣ h t ( x i )∣ . (32)
If h t ∗ = 0 h_t^* = 0 h t ∗ = 0 , the hypothesis assigns zero score to every training example and is therefore rejected. For h t ∗ > 0 h_t^* > 0 h t ∗ > 0 , define the normalized score
h ˉ t ( x ) : = h t ( x ) h t ∗ . (33) \bar{h}_t(x) := \frac{h_t(x)}{h_t^*}. \tag*{(33)} h ˉ t ( x ) := h t ∗ h t ( x ) . (33)
By construction,
∣ h ˉ t ( x i ) ∣ ≤ 1 for every i ∈ [ m ] . \lvert\bar{h}_t(x_i)\rvert\le1 \qquad\text{for every } i \in[m]. ∣ h ˉ t ( x i )∣ ≤ 1 for every i ∈ [ m ] .
The normalization does not change the predicted labels on the training sample, since sign ( h ˉ t ( x i ) ) = sign ( h t ( x i ) ) \operatorname{sign}(\bar{h}_t(x_i)) = \operatorname{sign}(h_t(x_i)) sign ( h ˉ t ( x i )) = sign ( h t ( x i )) , but it makes the normalized scores, the normalized edge, and the resulting ensemble increment invariant under a positive rescaling of h t h_t h t on the training sample. The normalized empirical edge is
r t : = ∑ i = 1 m D t ( i ) y i h ˉ t ( x i ) ∈ [ − 1 , 1 ] . (34) r_t := \sum_{i=1}^{m} D^t(i)y_i\bar{h}_t(x_i) \in[-1,1]. \tag*{(34)} r t := i = 1 ∑ m D t ( i ) y i h ˉ t ( x i ) ∈ [ − 1 , 1 ] . (34)
As in the general framework, r t r_t r t measures the weighted alignment between the normalized scores and the labels. For the positive-edge regime 0 < r t < 1 0 < r_t < 1 0 < r t < 1 considered in the convergence analysis, AdaBoostR assigns the normalized hypothesis the coefficient
β t : = 1 2 log ( 1 + r t 1 − r t ) , 0 < r t < 1. (35) \beta_t := \frac{1}{2}\log\left(\frac{1+r_t}{1-r_t}\right), \qquad0<r_t<1. \tag*{(35)} β t := 2 1 log ( 1 − r t 1 + r t ) , 0 < r t < 1. (35)
Since r t > 0 r_t>0 r t > 0 , one has β t > 0 \beta_t>0 β t > 0 . The coefficient multiplying the original, unnormalized hypothesis is therefore
α t : = β t h t ⋆ = 1 2 h t ⋆ log ( 1 + r t 1 − r t ) . (36) \alpha_t := \frac{\beta_t}{h_t^\star}=\frac{1}{2h_t^\star}\log\left(\frac{1+r_t}{1-r_t}\right). \tag*{(36)} α t := h t ⋆ β t = 2 h t ⋆ 1 log ( 1 − r t 1 + r t ) . (36)
Consequently,
α t h t ( x ) = β t h ˉ t ( x ) . (37) \alpha_t h_t(x)=\beta_t\bar{h}_t(x). \tag*{(37)} α t h t ( x ) = β t h ˉ t ( x ) . (37)
Thus, the contribution of the new hypothesis to the ensemble is determined by its normalized score and its normalized edge, rather than by the arbitrary overall magnitude of h t h_t h t on the training sample.
The distribution over the training examples is updated according to
D t + 1 ( i ) = D t ( i ) 1 − r t y i h ˉ t ( x i ) 1 − r t 2 , i ∈ [ m ] . (38) D^{t+1}(i)=D^t(i)\frac{1-r_t y_i\bar{h}_t(x_i)}{1-r_t^2}, \qquad i\in[m]. \tag*{(38)} D t + 1 ( i ) = D t ( i ) 1 − r t 2 1 − r t y i h ˉ t ( x i ) , i ∈ [ m ] . (38)
The denominator 1 − r t 2 1-r_t^2 1 − r t 2 normalizes the updated weights. Indeed, using the definition of r t r_t r t ,
∑ i = 1 m D t ( i ) ( 1 − r t y i h t ( x i ) ) = 1 − r t ∑ i = 1 m D t ( i ) y i h t ( x i ) = 1 − r t 2 . (39) \sum_{i=1}^{m}D^t(i)\left(1-r_t y_i h_t(x_i)\right)=1-r_t\sum_{i=1}^{m}D^t(i)y_i h_t(x_i)=1-r_t^2. \tag*{(39)} i = 1 ∑ m D t ( i ) ( 1 − r t y i h t ( x i ) ) = 1 − r t i = 1 ∑ m D t ( i ) y i h t ( x i ) = 1 − r t 2 . (39)
Moreover, since ∣ y i h ˉ t ( x i ) ∣ ≤ 1 \lvert y_i\bar{h}_t(x_i)\rvert\leq1 ∣ y i h ˉ t ( x i )∣ ≤ 1 and 0 < r t < 1 0<r_t<1 0 < r t < 1 ,
1 − r t y i h ˉ t ( x i ) ≥ 1 − r t > 0. 1-r_t y_i\bar{h}_t(x_i)\geq1-r_t>0. 1 − r t y i h ˉ t ( x i ) ≥ 1 − r t > 0.
Thus, the updated weights are nonnegative and sum to one.
To determine how the weight of an individual example changes, define its signed score by s t , i : = y i h ˉ t ( x i ) s_{t,i}:=y_i\bar{h}_t(x_i) s t , i := y i h ˉ t ( x i ) . Then
D t + 1 ( i ) D t ( i ) − 1 = r t ( r t − s t , i ) 1 − r t 2 . (40) \frac{D^{t+1}(i)}{D^t(i)}-1=\frac{r_t(r_t-s_{t,i})}{1-r_t^2}. \tag*{(40)} D t ( i ) D t + 1 ( i ) − 1 = 1 − r t 2 r t ( r t − s t , i ) . (40)
Because 0 < r t < 1 0<r_t<1 0 < r t < 1 , the weight of example i i i increases if s t , i < r t s_{t,i}<r_t s t , i < r t , remains unchanged if s t , i = r t s_{t,i}=r_t s t , i = r t , and decreases if s t , i > r t s_{t,i}>r_t s t , i > r t . In particular, every wrong-sign example satisfies s t , i < 0 < r t s_{t,i}<0<r_t s t , i < 0 < r t and therefore receives greater weight. A correctly classified example may also receive greater weight when its positive signed score lies below the round edge, whereas examples with signed scores above the round edge receive less weight.
When the weak hypothesis is binary-valued, h t ( x i ) ∈ { − 1 , + 1 } h_t(x_i)\in\{-1,+1\} h t ( x i ) ∈ { − 1 , + 1 } , one has
h t ⋆ = 1 , h ˉ t = h t , r t = 1 − 2 ε t , h_t^\star=1,\qquad\bar{h}_t=h_t,\qquad r_t=1-2\varepsilon_t, h t ⋆ = 1 , h ˉ t = h t , r t = 1 − 2 ε t ,
where ε t \varepsilon_t ε t is the weighted classification error. The coefficient then becomes
α t = 1 2 log ( 1 − ε t ε t ) . (41) \alpha_t=\frac{1}{2}\log\left(\frac{1-\varepsilon_t}{\varepsilon_t}\right). \tag*{(41)} α t = 2 1 log ( ε t 1 − ε t ) . (41)
and the rational update (38) reduces to the normalized weight update of discrete AdaBoost. Thus, AdaBoostR differs from discrete AdaBoost only when the weak hypotheses take intermediate confidence-rated values in ( − 1 , 1 ) (-1,1) ( − 1 , 1 ) [8 , 16 ] . The complete procedure is summarized in Algorithm 2.
Algorithm 2 AdaBoostR with rational reweighting
Input: weak learner A \mathcal{A} A , sample S = { ( x i , y i ) } i = 1 m \mathcal{S} = \{(x_i,y_i)\}_{i=1}^{m} S = {( x i , y i ) } i = 1 m , number of rounds T T T
Initialize: D 1 ( i ) = 1 / m D^1(i) = 1/m D 1 ( i ) = 1/ m for every i ∈ [ m ] i \in[m] i ∈ [ m ] and F 0 ( x ) = 0 F_0(x) = 0 F 0 ( x ) = 0 .
for t = 1 t = 1 t = 1 to T T T do
Invoke A \mathcal{A} A with respect to D t D^t D t to obtain h t : X → [ − 1 , 1 ] h_t : \mathcal{X} \to[-1,1] h t : X → [ − 1 , 1 ] .
Compute
h t ∗ = max i ∈ [ m ] ∣ h t ( x i ) ∣ . h_t^* = \max_{i \in[m]} |h_t(x_i)|. h t ∗ = i ∈ [ m ] max ∣ h t ( x i ) ∣.
if h t ∗ = 0 h_t^* = 0 h t ∗ = 0 then
Reject the hypothesis and continue to the next weak-learner fit.
end if
Define
h ˉ t ( x ) = h t ( x ) h t ∗ . \bar{h}_t(x) = \frac{h_t(x)}{h_t^*}. h ˉ t ( x ) = h t ∗ h t ( x ) .
Compute the raw normalized edge
r t r a w = ∑ i = 1 m D t ( i ) y i h ˉ t ( x i ) . r_t^{\mathrm{raw}} = \sum_{i=1}^{m} D^t(i)y_i\bar{h}_t(x_i). r t raw = i = 1 ∑ m D t ( i ) y i h ˉ t ( x i ) .
if r t r a w < 0 r_t^{\mathrm{raw}} < 0 r t raw < 0 then
Replace h t = − h t h_t = -h_t h t = − h t and h ˉ t = − h ˉ t \bar{h}_t = -\bar{h}_t h ˉ t = − h ˉ t .
end if
Set r t = ∣ r t r a w ∣ r_t = |r_t^{\mathrm{raw}}| r t = ∣ r t raw ∣ .
Set
β t = 1 2 log ( 1 + r t 1 − r t ) , α t = β t h t ∗ . \beta_t = \frac{1}{2}\log\left(\frac{1+r_t}{1-r_t}\right), \qquad\alpha_t = \frac{\beta_t}{h_t^*}. β t = 2 1 log ( 1 − r t 1 + r t ) , α t = h t ∗ β t .
Update, for every i ∈ [ m ] i \in[m] i ∈ [ m ] ,
D t + 1 ( i ) = D t ( i ) 1 − r t y i h ˉ t ( x i ) 1 − r t 2 . D^{t+1}(i) = D^t(i)\frac{1-r_ty_i\bar{h}_t(x_i)}{1-r_t^2}. D t + 1 ( i ) = D t ( i ) 1 − r t 2 1 − r t y i h ˉ t ( x i ) .
Set
F t ( x ) = F t − 1 ( x ) + α t h t ( x ) . F_t(x) = F_{t-1}(x) + \alpha_t h_t(x). F t ( x ) = F t − 1 ( x ) + α t h t ( x ) .
end for
Return
F T ( x ) = ∑ t = 1 T α t h t ( x ) , H T ( x ) = sign ( F T ( x ) ) . F_T(x) = \sum_{t=1}^{T}\alpha_t h_t(x), \qquad H_T(x) = \operatorname{sign}(F_T(x)). F T ( x ) = t = 1 ∑ T α t h t ( x ) , H T ( x ) = sign ( F T ( x )) .
Generalization Bounds via Rademacher Complexity
Fundamentally, learning selects a hypothesis from H \mathcal{H} H based on a finite training sample, but the main objective is good performance on new examples drawn from the same distribution D \mathcal{D} D . Generalization theory allows to relate empirical performance to expected classification risk.
In practice, generalization performance can be estimated using data that are not used to fit the model, for example through a separate test set or cross-validation. Here, instead, we seek an explicit theoretical upper bound on the expected risk in terms of quantities measured on the training sample and the complexity of the hypothesis class.
In what follows, we derive such a generalization bound using standard uniform complexity arguments. In particular, we employ Rademacher complexity as our primary measure of hypothesis class capacity [15 , 4 ] . Rademacher complexity provides uniform bounds over the entire hypothesis class and is well suited to bounded real-valued predictors in [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] . Moreover, as we explain shortly, it is invariant under taking convex hulls of a hypothesis class, a property that will be relevant when analyzing ensemble constructions.
This framework allows us to decompose the expected risk into empirical, complexity, and finitesample contributions, which will serve as the basis for our comparison of noiseless training, PEC-based mitigation, and boosting with noisy PQCs.
We use this standard bound because the compared methods will later be placed under the same reference hypothesis class. Consequently, for fixed sample size, margin threshold, and confidence level, the complexity and finite-sample terms in this bound are common to the compared methods. The resource comparison can therefore be based on the empirical margin-loss term.
Before defining risk formally, we emphasize that although the task is binary classification, all theoretical analysis is carried out on the hypotheses that are real-valued functions h : X → [ − 1 , 1 ] h:\mathcal{X}\to[-1,1] h : X → [ − 1 , 1 ] , since margins and generalization bounds depend on the magnitude of the score rather than only its sign. The associated classifier is then obtained by applying a sign (signum ) function:
y ^ = sign ( h ( x ) ) \hat{y}=\operatorname{sign}(h(x)) y ^ = sign ( h ( x ))
In the realizable PAC setting introduced in § 2.1 , the labels are determined by an unknown target concept c : X → { − 1 , + 1 } c:\mathcal{X}\to\{-1,+1\} c : X → { − 1 , + 1 } , so that y i = c ( x i ) y_i=c(x_i) y i = c ( x i ) .
Definition 3. (Empirical risk) Given a finite training sample S = { ( x i , y i ) } i = 1 m S=\{(x_i,y_i)\}_{i=1}^{m} S = {( x i , y i ) } i = 1 m with y i ∈ { − 1 , + 1 } y_i\in\{-1,+1\} y i ∈ { − 1 , + 1 } , the empirical risk of a hypothesis h h h is defined as
R ^ S ( h ) = 1 m ∑ i = 1 m I { y i h ( x i ) ≤ 0 } . (42) \widehat{R}_S(h)=\frac{1}{m}\sum_{i=1}^{m}\mathbb{I}\{y_i h(x_i)\leq0\}. \tag*{(42)} R S ( h ) = m 1 i = 1 ∑ m I { y i h ( x i ) ≤ 0 } . (42)
Definition 4. (Expected risk) The expected risk (or generalization error) of a classifier h h h is defined as the expected classification error with respect to the data distribution D \mathcal{D} D :
R ( h ) = Pr x ∼ D [ y h ( x ) ≤ 0 ] . (43) R(h)=\Pr_{x\sim\mathcal{D}}[y h(x)\leq0]. \tag*{(43)} R ( h ) = x ∼ D Pr [ y h ( x ) ≤ 0 ] . (43)
This quantity captures the true generalization performance of the classifier, but is not directly accessible in practice since D \mathcal{D} D is unknown. The empirical risk is observable on the training sample, whereas the expected risk is the quantity of interest for generalization. Statistical learning theory therefore seeks to control the difference between these quantities in terms of properties of the hypothesis class and the number of training examples. We use Rademacher complexity for this purpose.
Definition 5. (Empirical Rademacher complexity) Let X ⊂ R N \mathcal{X}\subset\mathbb{R}^{N} X ⊂ R N denote the input space and H ⊂ { h : X → [ − 1 , + 1 ] } \mathcal{H}\subset\{h:\mathcal{X}\to[-1,+1]\} H ⊂ { h : X → [ − 1 , + 1 ]} be a family of functions. Let S = ( x 1 , … , x m ) S=(x_1,\ldots,x_m) S = ( x 1 , … , x m ) be a sample of size m m m drawn i.i.d. from a distribution D \mathcal{D} D over X \mathcal{X} X . The empirical Rademacher complexity of H \mathcal{H} H with respect to S S S is defined as
R ^ S ( H ) = E σ ∼ Unif ( { − 1 , + 1 } m ) [ sup h ∈ H 1 m ∑ i = 1 m σ i h ( x i ) ] , (44) \widehat{\mathfrak{R}}_S(\mathcal{H})=\mathbb{E}_{\sigma\sim\operatorname{Unif}(\{-1,+1\}^{m})}\left[\sup_{h\in\mathcal{H}}\frac{1}{m}\sum_{i=1}^{m}\sigma_i h(x_i)\right], \tag*{(44)} R S ( H ) = E σ ∼ Unif ({ − 1 , + 1 } m ) [ h ∈ H sup m 1 i = 1 ∑ m σ i h ( x i ) ] , (44) where Unif ( { − 1 , + 1 } m ) \operatorname{Unif}(\{-1,+1\}^{m}) Unif ({ − 1 , + 1 } m ) is the uniform distribution on { − 1 , + 1 } m \{-1,+1\}^{m} { − 1 , + 1 } m . The i.i.d. random variables σ = ( σ i ) i ∈ [ m ] \boldsymbol{\sigma}=(\sigma_i)_{i\in[m]} σ = ( σ i ) i ∈ [ m ] are often called Rademacher random variables, that is, Pr ( σ i = + 1 ) = Pr ( σ i = − 1 ) = 1 2 \Pr(\sigma_i=+1)=\Pr(\sigma_i=-1)=\frac{1}{2} Pr ( σ i = + 1 ) = Pr ( σ i = − 1 ) = 2 1 .
The (distribution-dependent) Rademacher complexity of H \mathcal{H} H is defined as
R m ( H ) = E S ∼ D m [ R ^ S ( H ) ] (45) \mathfrak{R}_m(\mathcal{H})=\mathbb{E}_{S\sim\mathcal{D}^{m}}[\widehat{\mathfrak{R}}_S(\mathcal{H})] \tag*{(45)} R m ( H ) = E S ∼ D m [ R S ( H )] (45)
In many learning settings, one additionally seeks hypotheses that assign the correct label with a large confidence margin y h ( x ) y h(x) y h ( x ) : it is positive for a correctly signed prediction and its magnitude measures the confidence rating assigned by the predictor. In our analysis, margin considerations play an explicit role in the theoretical comparison, as boosting algorithms are naturally analyzed through margin-based guarantees.
Definition 6. (Empirical margin loss) The empirical margin loss of h h h given S S S and μ ∈ ( 0 , 1 ] \mu\in(0,1] μ ∈ ( 0 , 1 ] is defined as
R ^ S , μ ( h ) = 1 m ∑ i = 1 m Φ μ ( y i h ( x i ) ) where Φ μ ( x ) = min { 1 , max { 0 , 1 − x μ } } = { 1 , x ≤ 0 1 − x μ , 0 ≤ x ≤ μ 0 , μ ≤ x (46) \widehat{R}_{S,\mu}(h)=\frac{1}{m}\sum_{i=1}^{m}\Phi_\mu(y_i h(x_i)) \quad\text{where}\quad\Phi_\mu(x)=\min\left\{1,\max\left\{0,1-\frac{x}{\mu}\right\}\right\}=
\begin{cases}
1, & x\leq0\\
1-\frac{x}{\mu}, & 0\leq x\leq\mu\\
0, & \mu\leq x
\end{cases} \tag*{(46)} R S , μ ( h ) = m 1 i = 1 ∑ m Φ μ ( y i h ( x i )) where Φ μ ( x ) = min { 1 , max { 0 , 1 − μ x } } = ⎩ ⎨ ⎧ 1 , 1 − μ x , 0 , x ≤ 0 0 ≤ x ≤ μ μ ≤ x (46)
It assigns full loss to wrong predictions, partial loss to correct but low-margin predictions, and zero loss to predictions with margin at least μ \mu μ .
Definition 7. (Empirical margin error) For a predictor h : X → R h : \mathcal{X} \to\mathbb{R} h : X → R and margin parameter μ > 0 \mu> 0 μ > 0 , we define the empirical margin error
R ^ S , μ m a r ( h ) = 1 m ∑ i = 1 m I { y i h ( x i ) ≤ μ } . (47) \widehat{R}^{\mathrm{mar}}_{S,\mu}(h) = \frac{1}{m} \sum_{i=1}^{m} \mathbb{I}\{y_i h(x_i) \le\mu\}. \tag*{(47)} R S , μ mar ( h ) = m 1 i = 1 ∑ m I { y i h ( x i ) ≤ μ } . (47)
This quantity counts the fraction of examples whose margin falls below the threshold μ \mu μ .
Having introduced the empirical margin loss in Eq. (46) , we now use it to obtain a generalization bound that depends explicitly on the margin. The bound applies uniformly to a class of hypotheses and depends on the Rademacher complexity of that class.
To apply a Rademacher-complexity bound to the boosting ensemble, we need a hypothesis class that contains the ensemble while retaining a complexity term that can be related directly to that of the base hypotheses. We therefore show that a normalized boosting ensemble belongs to the convex hull of the signed base class. The key property used below is that taking a convex hull does not increase Rademacher complexity.
As specified in § 2.3 , if a trained weak hypothesis has a negative edge, its output is replaced by − h t -h_t − h t through classical post-processing. The hypotheses used by the ensemble may therefore belong either to H \mathcal{H} H or to − H -\mathcal{H} − H . We consequently define the signed closure:
H ± : = H ∪ ( − H ) , − H : = { − h : h ∈ H } . (48) \mathcal{H}_{\pm} := \mathcal{H} \cup(-\mathcal{H}), \qquad-\mathcal{H} := \{-h : h \in\mathcal{H}\}. \tag*{(48)} H ± := H ∪ ( − H ) , − H := { − h : h ∈ H } . (48)
If H \mathcal{H} H is already closed under sign reversal, then H ± = H \mathcal{H}_{\pm} = \mathcal{H} H ± = H . The convex hull of H ± \mathcal{H}_{\pm} H ± is
conv ( H ± ) : = { ∑ k = 1 p λ k h k : p ∈ N , h k ∈ H ± , λ k ≥ 0 , ∑ k = 1 p λ k = 1 } . (49) \operatorname{conv}(\mathcal{H}_{\pm}) := \left\{ \sum_{k=1}^{p} \lambda_k h_k : p \in\mathbb{N},\ h_k \in\mathcal{H}_{\pm},\ \lambda_k \ge0,\ \sum_{k=1}^{p} \lambda_k = 1 \right\}. \tag*{(49)} conv ( H ± ) := { k = 1 ∑ p λ k h k : p ∈ N , h k ∈ H ± , λ k ≥ 0 , k = 1 ∑ p λ k = 1 } . (49)
Here, p p p is the finite number of base hypotheses in the combination and λ 1 , … , λ p \lambda_1,\ldots,\lambda_p λ 1 , … , λ p are their nonnegative weights. The condition ∑ k = 1 p λ k = 1 \sum_{k=1}^{p} \lambda_k = 1 ∑ k = 1 p λ k = 1 makes the resulting predictor a convex combination.
Recall that the boosting score after T T T rounds is
F T ( x ) = ∑ t = 1 T α t h t ( x ) , α t ≥ 0. (50) F_T(x) = \sum_{t=1}^{T} \alpha_t h_t(x), \qquad\alpha_t \ge0. \tag*{(50)} F T ( x ) = t = 1 ∑ T α t h t ( x ) , α t ≥ 0. (50)
The boosting coefficients α t \alpha_t α t do not generally sum to one, so the raw score F T F_T F T need not belong to conv ( H ± ) \operatorname{conv}(\mathcal{H}_{\pm}) conv ( H ± ) . To place the ensemble in this class without changing its predicted labels, we normalize the coefficients by their sum. Define
A T : = ∑ t = 1 T α t , F ~ T ( x ) : = F T ( x ) A T , (51) A_T := \sum_{t=1}^{T} \alpha_t, \qquad\widetilde{F}_T(x) := \frac{F_T(x)}{A_T}, \tag*{(51)} A T := t = 1 ∑ T α t , F T ( x ) := A T F T ( x ) , (51)
assuming A T > 0 A_T > 0 A T > 0 . Then
F ~ T ( x ) = ∑ t = 1 T α t A T h t ( x ) , α t A T ≥ 0 , ∑ t = 1 T α t A T = 1 , (52) \widetilde{F}_T(x) = \sum_{t=1}^{T} \frac{\alpha_t}{A_T}h_t(x), \qquad\frac{\alpha_t}{A_T} \ge0, \qquad\sum_{t=1}^{T} \frac{\alpha_t}{A_T} = 1, \tag*{(52)} F T ( x ) = t = 1 ∑ T A T α t h t ( x ) , A T α t ≥ 0 , t = 1 ∑ T A T α t = 1 , (52)
and hence
F ~ T ∈ conv ( H ± ) . (53) \widetilde{F}_T \in\operatorname{conv}(\mathcal{H}_{\pm}). \tag*{(53)} F T ∈ conv ( H ± ) . (53)
Since A T > 0 A_T > 0 A T > 0 , normalization does not change the predicted label:
sign ( F ~ T ( x ) ) = sign ( F T ( x ) ) . (54) \operatorname{sign}\left(\widetilde{F}_T(x)\right) = \operatorname{sign}\left(F_T(x)\right). \tag*{(54)} sign ( F T ( x ) ) = sign ( F T ( x ) ) . (54)
It only fixes the scale on which the ensemble margins and the threshold μ \mu μ are measured.
Taking the convex hull does not increase Rademacher complexity:
R m ( conv ( H ± ) ) = R m ( H ± ) . (55) \mathfrak{R}_{m}(\operatorname{conv}(\mathcal{H}_{\pm}))=\mathfrak{R}_{m}(\mathcal{H}_{\pm}). \tag*{(55)} R m ( conv ( H ± )) = R m ( H ± ) . (55)
Indeed, for fixed Rademacher signs and any f = ∑ k = 1 p λ k h k ∈ conv ( H ± ) f=\sum_{k=1}^{p}\lambda_k h_k\in\operatorname{conv}(\mathcal{H}_{\pm}) f = ∑ k = 1 p λ k h k ∈ conv ( H ± ) ,
1 m ∑ i = 1 m σ i f ( x i ) = ∑ k = 1 p λ k ( 1 m ∑ i = 1 m σ i h k ( x i ) ) ≤ sup h ∈ H ± 1 m ∑ i = 1 m σ i h ( x i ) . \frac{1}{m}\sum_{i=1}^{m}\sigma_i f(x_i)=\sum_{k=1}^{p}\lambda_k\left(\frac{1}{m}\sum_{i=1}^{m}\sigma_i h_k(x_i)\right)\leq\sup_{h\in\mathcal{H}_{\pm}}\frac{1}{m}\sum_{i=1}^{m}\sigma_i h(x_i). m 1 i = 1 ∑ m σ i f ( x i ) = k = 1 ∑ p λ k ( m 1 i = 1 ∑ m σ i h k ( x i ) ) ≤ h ∈ H ± sup m 1 i = 1 ∑ m σ i h ( x i ) .
Conversely, H ± ⊆ conv ( H ± ) \mathcal{H}_{\pm}\subseteq\operatorname{conv}(\mathcal{H}_{\pm}) H ± ⊆ conv ( H ± ) , so the reverse inequality between the corresponding suprema is immediate. This proves Eq. (55) [4 , 15 ] . We can now state the margin-based generalization guarantee.
Theorem 1 (Ensemble Rademacher margin bound [15 ] ). Let H ± ⊆ { h : X → [ − 1 , 1 ] } \mathcal{H}_{\pm}\subseteq\{h:\mathcal{X}\to[-1,1]\} H ± ⊆ { h : X → [ − 1 , 1 ]} , let D \mathcal{D} D be a probability distribution over X ⊆ R N \mathcal{X}\subseteq\mathbb{R}^{N} X ⊆ R N , and let c : X → { − 1 , + 1 } c:\mathcal{X}\to\{-1,+1\} c : X → { − 1 , + 1 } be the target concept. Fix a margin threshold μ ∈ ( 0 , 1 ] \mu\in(0,1] μ ∈ ( 0 , 1 ] and a confidence parameter δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) .
Then, with probability at least 1 − δ 1-\delta 1 − δ over a sample S = { ( x i , c ( x i ) ) } i = 1 m S=\{(x_i,c(x_i))\}_{i=1}^{m} S = {( x i , c ( x i )) } i = 1 m , x i ∼ i . i . d . D x_i\overset{\mathrm{i.i.d.}}{\sim}\mathcal{D} x i ∼ i.i.d. D , the following holds simultaneously for every f ∈ conv ( H ± ) f\in\operatorname{conv}(\mathcal{H}_{\pm}) f ∈ conv ( H ± ) :
R ( f , c ) ≤ R ^ S , μ ( f ) + 2 μ R m ( H ± ) + log ( 1 / δ ) 2 m . (56) R(f,c)\leq\widehat{R}_{S,\mu}(f)+\frac{2}{\mu}\mathfrak{R}_{m}(\mathcal{H}_{\pm})+\sqrt{\frac{\log(1/\delta)}{2m}}. \tag*{(56)} R ( f , c ) ≤ R S , μ ( f ) + μ 2 R m ( H ± ) + 2 m log ( 1/ δ ) . (56)
Applying Theorem 1 to the normalized boosting score f = F ~ T f=\widetilde{F}_T f = F T gives
R ( F ~ T , c ) ≤ R ^ S , μ ( F ~ T ) + 2 μ R m ( H ± ) + log ( 1 / δ ) 2 m . (57) R(\widetilde{F}_T,c)\leq\widehat{R}_{S,\mu}(\widetilde{F}_T)+\frac{2}{\mu}\mathfrak{R}_{m}(\mathcal{H}_{\pm})+\sqrt{\frac{\log(1/\delta)}{2m}}. \tag*{(57)} R ( F T , c ) ≤ R S , μ ( F T ) + μ 2 R m ( H ± ) + 2 m log ( 1/ δ ) . (57)
Because F T F_T F T and F ~ T \widetilde{F}_T F T define the same classifier, R ( F T , c ) = R ( F ~ T , c ) R(F_T,c)=R(\widetilde{F}_T,c) R ( F T , c ) = R ( F T , c ) .
The bound separates three contributions. The first term is the empirical margin loss R ^ S , μ \widehat{R}_{S,\mu} R S , μ of the normalized ensemble and penalizes both incorrect and low-margin predictions. The second term measures the capacity of the signed base hypothesis class, while the final term accounts for statistical fluctuations due to the finite training sample. Thus, a small empirical margin loss together with controlled Rademacher complexity yields a small upper bound on the expected classification risk.
The empirical risk (Eq. (42) ), empirical margin loss (Eq. (46) ), and empirical margin error (Eq. (47) ) satisfy
R ^ S ( h ) ≤ R ^ S , μ ( h ) ≤ R ^ S , μ m a r ( h ) . (58) \widehat{R}_{S}(h)\leq\widehat{R}_{S,\mu}(h)\leq\widehat{R}^{\mathrm{mar}}_{S,\mu}(h). \tag*{(58)} R S ( h ) ≤ R S , μ ( h ) ≤ R S , μ mar ( h ) . (58)
Indeed, the three quantities coincide on examples with nonpositive margin. For an example with margin 0 < y i h ( x i ) < μ 0<y_i h(x_i)<\mu 0 < y i h ( x i ) < μ , the empirical risk is zero, the empirical margin loss lies strictly between zero and one, and the empirical margin error is one. Consequently, a bound R ^ S , μ ( h ) ≤ ϵ ′ \widehat{R}_{S,\mu}(h)\leq\epsilon' R S , μ ( h ) ≤ ϵ ′ implies R ^ S ( h ) ≤ ϵ ′ \widehat{R}_{S}(h)\leq\epsilon' R S ( h ) ≤ ϵ ′ . The converse is not true. Hence small classification error alone does not imply small empirical margin loss. The empirical margin error R ^ S , μ m a r ( f ) \widehat{R}^{\mathrm{mar}}_{S,\mu}(f) R S , μ mar ( f ) remains useful as an auxiliary quantity. Whenever an algorithm-specific analysis yields an upper bound on R ^ S , μ m a r \widehat{R}^{\mathrm{mar}}_{S,\mu} R S , μ mar , it also provides a sufficient upper bound on the empirical margin loss R ^ S , μ ( f ) \widehat{R}_{S,\mu}(f) R S , μ ( f ) .
We emphasize that the quantity of interest in this work is the expected 0–1 classification risk R ( h ) R(h) R ( h ) . Theorem 1 provides the condition required for a common resource comparison. Suppose two learning strategies produce predictors that can both be bounded using the same reference class H ± \mathcal{H}_{\pm} H ± , and suppose that the sample size m m m , margin threshold μ \mu μ , and confidence level δ \delta δ are fixed across the comparison. Then the last two terms in Eq. (56) are common to both strategies. Consequently, comparing the resources required to attain the same empirical margin-loss level
R ^ S , μ ( f ) ≤ ϵ m a r (59) \widehat{R}_{S,\mu}(f)\leq\epsilon_{\mathrm{mar}} \tag*{(59)} R S , μ ( f ) ≤ ϵ mar (59)
allows to compare the resources required to attain the same high-probability upper bound on expected classification risk.
This provides the generic comparison principle used for the analysis. The following sections instantiate it for noiseless PQCs, PEC, and boosting. In particular, we will identify an appropriate common reference class and then compare the circuit runs (shots) as resource cost required by PEC and boosting to attain the same empirical margin-loss target.
Learning Setup
Binary Classification with PQCs
We study a standard binary classification problem in the realizable PAC learning framework. Let C \mathcal{C} C be a concept class consisting of labeling functions c : X → { − 1 , + 1 } c:\mathcal{X}\to\{-1,+1\} c : X → { − 1 , + 1 } , where X ⊆ R N \mathcal{X}\subseteq\mathbb{R}^{N} X ⊆ R N denotes the input space. There exists an unknown target concept c ∈ C c\in\mathcal{C} c ∈ C that determines the labels.
Data points x ∈ X x\in\mathcal{X} x ∈ X are drawn i.i.d. from an unknown but fixed distribution D \mathcal{D} D over X \mathcal{X} X , and each label is given by y = c ( x ) y=c(x) y = c ( x ) . Given a training dataset S = { ( x i , c ( x i ) ) } i = 1 m S=\{(x_i,c(x_i))\}_{i=1}^{m} S = {( x i , c ( x i )) } i = 1 m of a fixed size m m m , the goal is to learn a classifier that generalizes well to unseen inputs drawn from the same distribution D \mathcal{D} D .
We consider real-valued hypotheses h : X → [ − 1 , 1 ] h:\mathcal{X}\to[-1,1] h : X → [ − 1 , 1 ] , where the predicted label is given by y ^ = sign ( h ( x ) ) \hat{y}=\operatorname{sign}(h(x)) y ^ = sign ( h ( x )) . In our setting, hypotheses are realized by parameterized quantum circuits (PQCs): for fixed circuit architecture and parameters, the output h ( x ) h(x) h ( x ) corresponds to the expectation value of a bounded observable (e.g., a Pauli operator or Pauli string) measured on the quantum state prepared by the circuit. The restriction h ( x ) ∈ [ − 1 , 1 ] h(x)\in[-1,1] h ( x ) ∈ [ − 1 , 1 ] reflects the bounded spectrum of such observables. We model a PQC hypothesis by specifying a family of input- and parameter-dependent quantum circuits, together with the physical noise model and the final measurement observable.
Given an input feature vector x ∈ X ⊆ R N x\in\mathcal{X}\subseteq\mathbb{R}^{N} x ∈ X ⊆ R N and trainable parameters θ \theta θ , we consider a circuit family in which the operations may depend on both x x x and θ \theta θ . This includes architectures with a single data-encoding stage as well as data-reuploading architectures in which the input enters at multiple layers. We use d d d for circuit depth (the number of repeated layers) and ℓ ∈ [ d ] = { 1 , … , d } \ell\in[d]=\{1,\ldots,d\} ℓ ∈ [ d ] = { 1 , … , d } for a layer index. Concretely, the ideal state prepared by the circuit can be written as
ρ θ ( x ) = U d ( θ d , x ) ⋯ U 2 ( θ 2 , x ) U 1 ( θ 1 , x ) ρ i n U 1 † ( θ 1 , x ) ⋯ U d † ( θ d , x ) , \rho_{\theta}(x)=U_{d}(\theta_{d},x)\cdots U_{2}(\theta_{2},x)U_{1}(\theta_{1},x)\rho_{\mathrm{in}}U_{1}^{\dagger}(\theta_{1},x)\cdots U_{d}^{\dagger}(\theta_{d},x), ρ θ ( x ) = U d ( θ d , x ) ⋯ U 2 ( θ 2 , x ) U 1 ( θ 1 , x ) ρ in U 1 † ( θ 1 , x ) ⋯ U d † ( θ d , x ) ,
where ρ i n \rho_{\mathrm{in}} ρ in is a fixed initial state and each U ℓ ( θ ℓ , x ) U_{\ell}(\theta_{\ell},x) U ℓ ( θ ℓ , x ) may depend both on trainable parameters θ ℓ \theta_{\ell} θ ℓ and on the input x x x . This formulation includes standard single-encoding architectures as a special case, as well as data re-uploading schemes in which classical information is injected at multiple layers. The chosen circuit family and parameter space determine the corresponding PQC hypothesis class.
We model physical noise by a local Markovian completely positive trace-preserving map (CPTP) channel applied after each circuit layer. The channel may depend on the layer, so the maps N ℓ \mathcal{N}_{\ell} N ℓ need not be identical, but in this model they are taken to be independent of the particular input x x x and parameter values θ \theta θ :
ρ 0 , θ n o i s y ( x ) : = ρ i n , \rho_{0,\theta}^{\mathrm{noisy}}(x):=\rho_{\mathrm{in}}, ρ 0 , θ noisy ( x ) := ρ in ,
and for ℓ ∈ [ d ] \ell\in[d] ℓ ∈ [ d ] ,
ρ ℓ , θ n o i s y ( x ) : = N ℓ ( U ℓ ( θ ℓ , x ) ρ ℓ − 1 , θ n o i s y ( x ) U ℓ † ( θ ℓ , x ) ) . (60) \rho_{\ell,\theta}^{\mathrm{noisy}}(x):=\mathcal{N}_{\ell}\left(U_{\ell}(\theta_{\ell},x)\rho_{\ell-1,\theta}^{\mathrm{noisy}}(x)U_{\ell}^{\dagger}(\theta_{\ell},x)\right). \tag*{(60)} ρ ℓ , θ noisy ( x ) := N ℓ ( U ℓ ( θ ℓ , x ) ρ ℓ − 1 , θ noisy ( x ) U ℓ † ( θ ℓ , x ) ) . (60)
where each N ℓ \mathcal{N}_{\ell} N ℓ is a CPTP map describing the noise associated with the ℓ \ell ℓ th circuit layer. The final noisy state is
ρ θ n o i s y ( x ) : = ρ d , θ n o i s y ( x ) . (61) \rho_{\theta}^{\mathrm{noisy}}(x):=\rho_{d,\theta}^{\mathrm{noisy}}(x). \tag*{(61)} ρ θ noisy ( x ) := ρ d , θ noisy ( x ) . (61)
The same construction applies at gate level by associating a CPTP noise channel with each individual gate location rather than with each layer. The numerical experiments below use this gate-local form.
Let O O O be a fixed Hermitian observable acting on the n n n -qubit Hilbert space and satisfying ∥ O ∥ ∞ ≤ 1 \lVert O\rVert_{\infty}\leq1 ∥ O ∥ ∞ ≤ 1 . The ideal prediction score is h θ ( x ) : = tr [ O ρ θ ( x ) ] h_{\theta}(x):=\operatorname{tr}[O\rho_{\theta}(x)] h θ ( x ) := tr [ O ρ θ ( x )] . The operator-norm condition ensures that h θ ( x ) ∈ [ − 1 , 1 ] h_{\theta}(x)\in[-1,1] h θ ( x ) ∈ [ − 1 , 1 ] . The physical circuit noise is incorporated into the final noisy state ρ θ n o i s y ( x ) \rho_{\theta}^{\mathrm{noisy}}(x) ρ θ noisy ( x ) . The corresponding mean noisy prediction score is
h θ n o i s y ( x ) : = tr [ O ρ θ n o i s y ( x ) ] . (62) h_{\theta}^{\mathrm{noisy}}(x):=\operatorname{tr}\left[O\rho_{\theta}^{\mathrm{noisy}}(x)\right]. \tag*{(62)} h θ noisy ( x ) := tr [ O ρ θ noisy ( x ) ] . (62)
The same observable O O O is used in the ideal and noisy prediction scores. In the present model, noise is represented by channels acting on the quantum state before an ideal measurement of O O O . We do not consider measurement-assignment or readout errors.
For a fixed d d d -layer architecture with parameter space Θ d \Theta_d Θ d , the ideal and noisy hypothesis classes are
H d n o i s e l e s s : = { h θ : X → [ − 1 , 1 ] ∣ h θ ( x ) = tr [ O ρ θ ( x ) ] , θ ∈ Θ d } , (63) \mathcal{H}_{d}^{\mathrm{noiseless}}:=\left\{h_{\theta}:\mathcal{X}\to[-1,1]\mid h_{\theta}(x)=\operatorname{tr}\left[O\rho_{\theta}(x)\right],\ \theta\in\Theta_d\right\}, \tag*{(63)} H d noiseless := { h θ : X → [ − 1 , 1 ] ∣ h θ ( x ) = tr [ O ρ θ ( x ) ] , θ ∈ Θ d } , (63)
and
H d n o i s y : = { h θ n o i s y : X → [ − 1 , 1 ] ∣ h θ n o i s y ( x ) = tr [ O ρ θ n o i s y ( x ) ] , θ ∈ Θ d } . (64) \mathcal{H}_{d}^{\mathrm{noisy}}:=\left\{h_{\theta}^{\mathrm{noisy}}:\mathcal{X}\to[-1,1]\mid h_{\theta}^{\mathrm{noisy}}(x)=\operatorname{tr}\left[O\rho_{\theta}^{\mathrm{noisy}}(x)\right],\ \theta\in\Theta_d\right\}. \tag*{(64)} H d noisy := { h θ noisy : X → [ − 1 , 1 ] ∣ h θ noisy ( x ) = tr [ O ρ θ noisy ( x ) ] , θ ∈ Θ d } . (64)
The functions h θ h_\theta h θ and h θ n o i s y h_\theta^{\mathrm{noisy}} h θ noisy denote exact mean expectation values. In the numerical experiments, they are estimated using a finite number of measurement shots. For the Pauli observables considered here, the finite-shot estimator satisfies
E s h o t s [ h ^ θ n o i s y ( x ) ] = h θ n o i s y ( x ) . (65) \mathbb{E}_{\mathrm{shots}}\left[\hat{h}_\theta^{\mathrm{noisy}}(x)\right] = h_\theta^{\mathrm{noisy}}(x). \tag*{(65)} E shots [ h ^ θ noisy ( x ) ] = h θ noisy ( x ) . (65)
Thus, circuit noise changes the mean prediction h θ n o i s y ( x ) h_\theta^{\mathrm{noisy}}(x) h θ noisy ( x ) , whereas finite-shot sampling introduces statistical fluctuations around that mean, which is treated separately from the physical noise defining H d n o i s y \mathcal{H}_d^{\mathrm{noisy}} H d noisy .
Common comparison target and assumptions
For the resource comparison, we fix a realized training sample S S S , the base circuit architecture and depth d d d , the parameter space Θ d \Theta_d Θ d , the observable O O O , and the physical noise condition N \mathcal{N} N .
We also fix the parameters entering the generalization bound: a margin threshold μ ∈ ( 0 , 1 ] \mu\in(0,1] μ ∈ ( 0 , 1 ] , an empirical margin-loss target ε m a r ∈ ( 0 , 1 ) \varepsilon_{\mathrm{mar}} \in(0,1) ε mar ∈ ( 0 , 1 ) , and a confidence parameter δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) . Here, μ \mu μ specifies the positive margin used in the empirical loss, while δ \delta δ controls the probability, over the random draw of the training sample, with which the generalization bound holds.
Our goal is to compare the resources required by PEC and boosting under the same generalization criterion. As established in § 2.4 , any predictor f f f in the common reference class satisfies, with probability at least 1 − δ 1-\delta 1 − δ over the draw of S S S ,
R ( f , c ) ≤ R ^ S , μ ( f ) + Δ g e n , (66) R(f,c) \le\widehat{R}_{S,\mu}(f) + \Delta_{\mathrm{gen}}, \tag*{(66)} R ( f , c ) ≤ R S , μ ( f ) + Δ gen , (66)
where Δ g e n \Delta_{\mathrm{gen}} Δ gen represents the complexity and finite-sample terms. For fixed m m m , μ \mu μ , δ \delta δ , and reference hypothesis class, Δ g e n \Delta_{\mathrm{gen}} Δ gen is common to the compared methods. We therefore require both methods to attain the same empirical margin-loss target,
R ^ S , μ ( f ) ≤ ε m a r . (67) \widehat{R}_{S,\mu}(f) \le\varepsilon_{\mathrm{mar}}. \tag*{(67)} R S , μ ( f ) ≤ ε mar . (67)
Any method reaching this target then satisfies the same upper bound R ( f , c ) ≤ ε m a r + Δ g e n R(f,c) \le\varepsilon_{\mathrm{mar}} + \Delta_{\mathrm{gen}} R ( f , c ) ≤ ε mar + Δ gen .
To make the resource comparison meaningful, we also fix training ingredients that are common by construction, including the optimizer, initialization distribution, batching rule, and per-evaluation shot policy. Method-specific operations remain different: PEC replaces ideal expectation-value evaluations by mitigated estimates, whereas boosting trains and combines noisy predictors and therefore introduces its own round-dependent updates and stopping conditions.
The resource analysis below additionally requires assumptions concerning the physical noise model, attainability of the common target, and the cost of reaching that target with the noiseless reference learner.
Assumption A1: local Markovian circuit noise. The maps in N \mathcal{N} N are assumed to be local Markovian CPTP channels acting at prescribed circuit locations. Here, local means that each noise map acts only on the qubits associated with that circuit location, while Markovian means that the noise at a given location acts on the current state without dependence on earlier noise events. In the numerical experiments, this model is specialized to gate-local depolarizing noise with the channel strength specified separately for each experimental condition.
This assumption specifies the physical-noise model used in the resource analysis and numerical implementation. Additional structure on the noise model is introduced later when establishing the common reference hypothesis class.
Assumption A2: noiseless margin-target attainability. For the given training dataset S S S , the fixed margin threshold μ \mu μ , and the selected circuit architecture of depth d d d , there exists a parameter vector θ ∈ Θ d \theta\in\Theta_d θ ∈ Θ d such that
R ^ S , μ ( h θ ) ≤ ε m a r . (68) \widehat{R}_{S,\mu}(h_\theta) \le\varepsilon_{\mathrm{mar}}. \tag*{(68)} R S , μ ( h θ ) ≤ ε mar . (68) Thus, the common empirical margin-loss target Eq. (67) is attainable by the ideal PQC hypothesis class.
Assumption A3: finite-evaluation reference optimization reachability. We fix a reference training procedure for the noiseless PQC model. This is a specified learning procedure, not an optimal one: it fixes the optimizer, initialization rule, batching scheme, and other training choices used to define the noiseless baseline. The procedure may still be randomized; for example, parameter initialization, mini-batch selection, or finite-shot measurement outcomes. Let ξ \xi ξ denote this internal randomness. Define the random variable N h i t r e f ( μ , ε m a r ; ξ ) N_{\mathrm{hit}}^{\mathrm{ref}}(\mu,\varepsilon_{\mathrm{mar}};\xi) N hit ref ( μ , ε mar ; ξ ) as the total number of expectation-value evaluations performed by the reference training procedure up to the first iterate whose deterministic mean predictor satisfies R ^ S , μ ( h θ ) ≤ ε m a r \widehat{R}_{S,\mu}(h_\theta) \leq\varepsilon_{\mathrm{mar}} R S , μ ( h θ ) ≤ ε mar .
We assume that there exists a finite reference evaluation budget N n o i s e l e s s N_{\mathrm{noiseless}} N noiseless such that
Pr ξ [ N h i t r e f ( μ , ε m a r ; ξ ) ≤ N n o i s e l e s s ] ≥ 1 − δ o p t , (69) \Pr_{\xi}\left[N_{\mathrm{hit}}^{\mathrm{ref}}(\mu,\varepsilon_{\mathrm{mar}};\xi) \leq N_{\mathrm{noiseless}}\right] \geq1-\delta_{\mathrm{opt}}, \tag*{(69)} ξ Pr [ N hit ref ( μ , ε mar ; ξ ) ≤ N noiseless ] ≥ 1 − δ opt , (69) where δ o p t ∈ [ 0 , 1 / 2 ) \delta_{\mathrm{opt}} \in[0,1/2) δ opt ∈ [ 0 , 1/2 ) is the optimization failure probability.
Assumptions A2 and A3 define the noiseless reference learning problem. Assumption A2 states that the selected PQC family contains a hypothesis that attains the common empirical margin-loss target, whereas Assumption A3 states that the fixed reference training procedure reaches such a hypothesis within the finite evaluation budget N n o i s e l e s s N_{\mathrm{noiseless}} N noiseless with probability at least 1 − δ o p t 1-\delta_{\mathrm{opt}} 1 − δ opt over its internal randomness. These assumptions are conditional on the realized training sample S S S : the probability in Assumption A3 is over the internal training randomness ξ \xi ξ . This is distinct from the confidence parameter δ \delta δ in the generalization bound, whose probability statement is over the random draw of S S S . We do not assume a uniform optimization guarantee over all possible training samples.
Resource Cost in the Noiseless Case
We distinguish two levels of resource accounting. An expectation-value evaluation is the estimation of one circuit expectation value for a fixed parameter–input pair ( θ , x ) (\theta,x) ( θ , x ) using a prescribed shot allocation. The physical resource required for such an evaluation is the number of circuit executions (shots) used to construct that estimate. Different components of the training procedure, such as loss evaluation, gradient estimation, or stopping checks, may require multiple expectation-value evaluations. Under Assumption A3, we use the finite reference budget N n o i s e l e s s N_{\mathrm{noiseless}} N noiseless as the evaluation-level cost of the noiseless reference procedure:
Cost n o i s e l e s s ( e v a l ) = N n o i s e l e s s . (70) \operatorname{Cost}_{\mathrm{noiseless}}^{(\mathrm{eval})}=N_{\mathrm{noiseless}}. \tag*{(70)} Cost noiseless ( eval ) = N noiseless . (70)
This coarse-grained accounting is sufficient for the resource comparison because the details of the optimizer, batching scheme, and stopping procedure are already reflected in the total number of expectation-value evaluations.
We now convert this evaluation count into the physical circuit-execution cost. Even in the noiseless reference model, each expectation value must be estimated from finitely many measurement shots. Thus, “noiseless” refers to ideal circuit evolution and does not imply exact access to expectation values. If each expectation-value evaluation uses N s h N_{\mathrm{sh}} N sh shots, then the corresponding physical circuit-execution budget is
S h o t s n o i s e l e s s = N n o i s e l e s s × N s h . (71) \mathrm{Shots}_{\mathrm{noiseless}}=N_{\mathrm{noiseless}}\times N_{\mathrm{sh}}. \tag*{(71)} Shots noiseless = N noiseless × N sh . (71)
For a Pauli observable with outcomes in { − 1 , + 1 } \{-1,+1\} { − 1 , + 1 } , Hoeffding’s inequality implies that estimating an expectation value within additive error ε e v a l \varepsilon_{\mathrm{eval}} ε eval with confidence 1 − δ s h 1-\delta_{\mathrm{sh}} 1 − δ sh requires
N s h ≥ 2 ε e v a l 2 log 2 δ s h . (72) N_{\mathrm{sh}} \geq\frac{2}{\varepsilon_{\mathrm{eval}}^2}\log\frac{2}{\delta_{\mathrm{sh}}}. \tag*{(72)} N sh ≥ ε eval 2 2 log δ sh 2 . (72)
In what follows, we express the total cost of PEC and boosting-based trainings relative to the reference baseline. Specifically, additional multiplicative factors will account for: (i) quasiprobability variance amplification in PEC, and (ii) repeated training of weak learners in boosting. This allows a direct comparison of strategies in terms of the overhead required to reach the same target empirical margin loss ε m a r \varepsilon_{\mathrm{mar}} ε mar .
PEC as a Cost Multiplier of the Ideal Case
Effect of PEC on Optimization and Risk
In the PEC-based strategy (Section 2.2), each ideal expectation-value evaluation required by the reference training procedure is replaced by a quasiprobability estimator constructed from noisy circuit executions. This construction requires classical knowledge of the elementary noisy operations. To relate this finite-sampling procedure to the common learning target and to the reference resource budget, we now state the additional assumptions specific to PEC.
Assumption P1: known elementary noisy operations. PEC is assumed to have classical descriptions of the elementary noisy operations used by the device, and these descriptions are treated as exact within the theoretical model. Channel-characterization and calibration errors, as well as the resources required to obtain the channel descriptions, are not included in the PEC training cost.
Under this assumption, the quasiprobability representation is constructed for the actual noisy operations, and the resulting PEC estimator is unbiased for the corresponding ideal expectation value. This channel-knowledge requirement is specific to PEC. The boosting strategy does not require an explicit classical description of the physical noise channels, although it relies on its own weak-learning assumptions.
Now we establish the deterministic mean function represented by PEC, then relate finite-shot PEC estimates to the common empirical margin-loss target introduced in Section 3.2, and finally quantify the additional sampling cost required to attain a fixed expectation-value precision.
For every fixed parameter vector θ ∈ Θ d \theta\in\Theta_d θ ∈ Θ d and input x ∈ X x \in\mathcal{X} x ∈ X , let h ^ θ P E C ( x ) \hat{h}^{\mathrm{PEC}}_\theta(x) h ^ θ PEC ( x ) denote the finite-sample PEC estimator of the ideal prediction score. By the unbiasedness guarantee of PEC,
E P E C [ h ^ θ P E C ( x ) ] = h θ ( x ) , (73) \mathbb{E}_{\mathrm{PEC}}\left[\hat{h}^{\mathrm{PEC}}_\theta(x)\right] = h_\theta(x), \tag*{(73)} E PEC [ h ^ θ PEC ( x ) ] = h θ ( x ) , (73)
where the expectation is taken over quasiprobability sampling and finite-shot measurement randomness.
PEC therefore preserves the ideal hypothesis class at the level of mean prediction functions. More precisely, define
H d P E C , m e a n : = { x ↦ E P E C [ h ^ θ P E C ( x ) ] ∣ θ ∈ Θ d } . (74) \mathcal{H}^{\mathrm{PEC,mean}}_d := \left\{x \mapsto\mathbb{E}_{\mathrm{PEC}}\left[\hat{h}^{\mathrm{PEC}}_\theta(x)\right] \mid\theta\in\Theta_d\right\}. \tag*{(74)} H d PEC , mean := { x ↦ E PEC [ h ^ θ PEC ( x ) ] ∣ θ ∈ Θ d } . (74)
Equation (73) implies
H d P E C , m e a n = H d n o i s e l e s s . (75) \mathcal{H}^{\mathrm{PEC,mean}}_d = \mathcal{H}^{\mathrm{noiseless}}_d. \tag*{(75)} H d PEC , mean = H d noiseless . (75)
A finite-shot PEC estimate is nevertheless random and is not itself a deterministic element of H d n o i s e l e s s \mathcal{H}^{\mathrm{noiseless}}_d H d noiseless . PEC does not enlarge the deterministic mean-function class; instead, finite sampling produces a random estimator whose expectation is the ideal prediction.
Since the two deterministic mean-function classes coincide, their Rademacher complexities are equal:
R m ( H d P E C , m e a n ) = R m ( H d n o i s e l e s s ) . (76) \mathfrak{R}_m\left(\mathcal{H}^{\mathrm{PEC,mean}}_d\right) = \mathfrak{R}_m\left(\mathcal{H}^{\mathrm{noiseless}}_d\right). \tag*{(76)} R m ( H d PEC , mean ) = R m ( H d noiseless ) . (76)
Assumption P2: PEC finite-shot margin condition. The generalization analysis applies to the deterministic mean predictor h θ h_\theta h θ , whereas in practice its prediction scores are accessed through finite-shot PEC estimates. We therefore relate the empirical margin loss computed from the finite-shot PEC estimates to the empirical margin loss of the underlying deterministic mean predictor. For a fixed parameter vector θ \theta θ , define the event
E e v a l P E C ( θ ) : = ⋂ i = 1 m { ∣ h ^ θ P E C ( x i ) − h θ ( x i ) ∣ ≤ ε e v a l } . (77) \mathcal{E}^{\mathrm{PEC}}_{\mathrm{eval}}(\theta) := \bigcap_{i=1}^{m} \left\{\left|\hat{h}^{\mathrm{PEC}}_\theta(x_i) - h_\theta(x_i)\right| \le\varepsilon_{\mathrm{eval}}\right\}. \tag*{(77)} E eval PEC ( θ ) := i = 1 ⋂ m { h ^ θ PEC ( x i ) − h θ ( x i ) ≤ ε eval } . (77) We assume that the PEC shot allocation used for the margin evaluation is chosen such that
Pr ( E e v a l P E C ( θ ) ) ≥ 1 − δ e s t P E C , δ e s t P E C ∈ ( 0 , 1 ) . (78) \Pr\left(\mathcal{E}^{\mathrm{PEC}}_{\mathrm{eval}}(\theta)\right) \ge1-\delta^{\mathrm{PEC}}_{\mathrm{est}}, \qquad\delta^{\mathrm{PEC}}_{\mathrm{est}} \in(0,1). \tag*{(78)} Pr ( E eval PEC ( θ ) ) ≥ 1 − δ est PEC , δ est PEC ∈ ( 0 , 1 ) . (78) On the event E e v a l P E C ( θ ) \mathcal{E}^{\mathrm{PEC}}_{\mathrm{eval}}(\theta) E eval PEC ( θ ) , multiplication by y i ∈ { − 1 , + 1 } y_i \in\{-1,+1\} y i ∈ { − 1 , + 1 } preserves the deviation as ∣ y i ∣ = 1 \lvert y_i\rvert= 1 ∣ y i ∣ = 1 , so
∣ y i h ^ θ P E C ( x i ) − y i h θ ( x i ) ∣ ≤ ε e v a l . (79) \left|y_i\hat{h}^{\mathrm{PEC}}_\theta(x_i)-y_i h_\theta(x_i)\right| \le\varepsilon_{\mathrm{eval}}. \tag*{(79)} y i h ^ θ PEC ( x i ) − y i h θ ( x i ) ≤ ε eval . (79)
The ramp function Φ μ \Phi_\mu Φ μ defined in Eq. (46) is 1 / μ 1/\mu 1/ μ -Lipschitz. Therefore,
∣ Φ μ ( y i h ^ θ P E C ( x i ) ) − Φ μ ( y i h θ ( x i ) ) ∣ ≤ ε e v a l μ . (80) \left|\Phi_\mu\left(y_i\hat{h}^{\mathrm{PEC}}_\theta(x_i)\right)-\Phi_\mu\left(y_i h_\theta(x_i)\right)\right|\le\frac{\varepsilon_{\mathrm{eval}}}{\mu}. \tag*{(80)} Φ μ ( y i h ^ θ PEC ( x i ) ) − Φ μ ( y i h θ ( x i ) ) ≤ μ ε eval . (80)
Averaging over the training sample gives
∣ R ^ S , μ ( h ^ θ P E C ) − R ^ S , μ ( h θ ) ∣ ≤ ε e v a l μ . (81) \left|\widehat{R}_{S,\mu}\left(\hat{h}^{\mathrm{PEC}}_\theta\right)-\widehat{R}_{S,\mu}\left(h_\theta\right)\right|\le\frac{\varepsilon_{\mathrm{eval}}}{\mu}. \tag*{(81)} R S , μ ( h ^ θ PEC ) − R S , μ ( h θ ) ≤ μ ε eval . (81)
Consequently,
R ^ S , μ ( h θ ) ≤ R ^ S , μ ( h ^ θ P E C ) + ε e v a l μ . (82) \widehat{R}_{S,\mu}\left(h_\theta\right)\le\widehat{R}_{S,\mu}\left(\hat{h}^{\mathrm{PEC}}_\theta\right)+\frac{\varepsilon_{\mathrm{eval}}}{\mu}. \tag*{(82)} R S , μ ( h θ ) ≤ R S , μ ( h ^ θ PEC ) + μ ε eval . (82)
Hence, provided ε m a r > ε e v a l / μ \varepsilon_{\mathrm{mar}}>\varepsilon_{\mathrm{eval}}/\mu ε mar > ε eval / μ , the finite-shot stopping condition
R ^ S , μ ( h ^ θ P E C ) ≤ ε m a r − ε e v a l μ (83) \widehat{R}_{S,\mu}\left(\hat{h}^{\mathrm{PEC}}_\theta\right)\le\varepsilon_{\mathrm{mar}}-\frac{\varepsilon_{\mathrm{eval}}}{\mu} \tag*{(83)} R S , μ ( h ^ θ PEC ) ≤ ε mar − μ ε eval (83)
is sufficient, on E ε e v a l P E C ( θ ) \mathcal{E}^{\mathrm{PEC}}_{\varepsilon_{\mathrm{eval}}}(\theta) E ε eval PEC ( θ ) , to meet the deterministic mean target R ^ S , μ ( h θ ) ≤ ε m a r \widehat{R}_{S,\mu}(h_\theta)\le\varepsilon_{\mathrm{mar}} R S , μ ( h θ ) ≤ ε mar . Thus, an additive prediction error of at most ε e v a l \varepsilon_{\mathrm{eval}} ε eval changes the empirical margin loss by at most ε e v a l / μ \varepsilon_{\mathrm{eval}}/\mu ε eval / μ . The PEC sampling cost required to achieve this prediction accuracy is part of the resource analysis and numerical protocol.
Assumption P3: PEC evaluation stability. Although PEC expectation-value estimators are unbiased, their finite-shot fluctuations propagate into loss and gradient estimates and may therefore change the optimization trajectory. Unbiasedness alone does not imply that PEC training reaches the target using the same number of expectation-value evaluations as the ideal reference procedure. Let ξ ⋆ \xi^\star ξ ⋆ collect all internal randomness of PEC training, including parameter initialization, mini-batch selection, quasiprobability sampling, and finite-shot measurement outcomes. Define N h i t P E C ( μ , ε m a r ; ξ ⋆ ) N_{\mathrm{hit}}^{\mathrm{PEC}}(\mu,\varepsilon_{\mathrm{mar}};\xi^\star) N hit PEC ( μ , ε mar ; ξ ⋆ ) to be the total number of expectation-value evaluations performed by PEC training up to the first training iterate whose deterministic mean predictor satisfies R ^ S , μ ( h θ P E C ) ≤ ε m a r \widehat{R}_{S,\mu}(h_{\theta_{\mathrm{PEC}}})\le\varepsilon_{\mathrm{mar}} R S , μ ( h θ PEC ) ≤ ε mar . We assume that the PEC shot allocation is sufficiently large that
Pr ξ ⋆ [ N h i t P E C ( μ , ε m a r ; ξ ⋆ ) ≤ N n o i s e l e s s ] ≥ 1 − δ o p t P E C , (84) \Pr_{\xi^\star}\left[N_{\mathrm{hit}}^{\mathrm{PEC}}(\mu,\varepsilon_{\mathrm{mar}};\xi^\star)\le N_{\mathrm{noiseless}}\right]\ge1-\delta_{\mathrm{opt}}^{\mathrm{PEC}}, \tag*{(84)} ξ ⋆ Pr [ N hit PEC ( μ , ε mar ; ξ ⋆ ) ≤ N noiseless ] ≥ 1 − δ opt PEC , (84)
where N n o i s e l e s s N_{\mathrm{noiseless}} N noiseless is the ideal reference evaluation budget defined in § 3.3 . Assumption P3 therefore bounds the number of expectation-value evaluations required by PEC to reach the common deterministic margin-loss target by the reference evaluation budget. Consequently, the PEC optimization cost has the form
Cost P E C ( e v a l ) ≤ N n o i s e l e s s = Cost n o i s e l e s s ( e v a l ) . (85) \operatorname{Cost}_{\mathrm{PEC}}^{(\mathrm{eval})}\le N_{\mathrm{noiseless}}=\operatorname{Cost}_{\mathrm{noiseless}}^{(\mathrm{eval})}. \tag*{(85)} Cost PEC ( eval ) ≤ N noiseless = Cost noiseless ( eval ) . (85)
Assumption P3 concerns the number of expectation-value evaluations and does not yet account for the number of physical circuit executions required for each evaluation. That additional cost is determined by PEC sampling.
Let γ \gamma γ denote the circuit-level quasiprobability norm. The factor γ 2 \gamma^2 γ 2 controls the amplification of estimator variance and, consequently, the number of circuit samples required to attain the same estimation precision as an unmitigated expectation-value estimate [22 , 7 ] . We therefore refer to γ 2 \gamma^2 γ 2 as the PEC variance-amplification or quasiprobability-sampling overhead. The explicit dependence of γ \gamma γ on the circuit depth and physical error rates under local depolarizing noise is derived in the following subsection.
Cost Inflation via PEC
We now quantify the resource overhead introduced by probabilistic error cancellation (PEC) relative to the noiseless reference model.
From (85) we have that the optimization cost remains essentially unchanged. The difference between the ideal and PEC settings therefore arises from the number of measurement shots required per expectation-value evaluation.
In the noiseless reference model, the total number of circuit executions (shots) required to reach empirical margin error ε m a r ′ \varepsilon'_{\mathrm{mar}} ε mar ′ :
S h o t s n o i s e l e s s = N n o i s e l e s s × N s h , \mathrm{Shots}_{\mathrm{noiseless}} = N_{\mathrm{noiseless}} \times N_{\mathrm{sh}}, Shots noiseless = N noiseless × N sh ,
where N s h N_{\mathrm{sh}} N sh denotes the number of shots used to estimate each expectation value to fixed accuracy ε e v a l \varepsilon_{\mathrm{eval}} ε eval (Eq. (71) ).
A single PEC sample takes values in [ − γ , γ ] [-\gamma,\gamma] [ − γ , γ ] . Therefore, to attain the same additive precision ε e v a l \varepsilon_{\mathrm{eval}} ε eval ,
N s h P E C = γ 2 N s h , (86) N_{\mathrm{sh}}^{\mathrm{PEC}} = \gamma^2 N_{\mathrm{sh}}, \tag*{(86)} N sh PEC = γ 2 N sh , (86)
as mentioned in the background section (Eq. (10) ). Here γ \gamma γ denotes the quasi-probability norm associated with the inverted noise channel. Because our comparison is theoretical, we use the proven sufficient shot bounds themselves as the resource quantities entering the analysis.
Substituting N s h P E C N_{\mathrm{sh}}^{\mathrm{PEC}} N sh PEC into the shot-counting expression yields
S h o t s P E C = S h o t s n o i s e l e s s × γ 2 (87) \mathrm{Shots}_{\mathrm{PEC}} = \mathrm{Shots}_{\mathrm{noiseless}} \times\gamma^2 \tag*{(87)} Shots PEC = Shots noiseless × γ 2 (87)
Thus, PEC inflates the total resource cost multiplicatively through variance amplification, while leaving the optimization depth unchanged.
Sampled PEC Overhead under Gate-Local Depolarizing Noise
We now specialize the PEC sampling overhead to gate-local depolarizing noise. Here, “gate-local” means that a depolarizing channel acts independently at each noisy gate location and only on the qubits in the support of that gate.
For a gate acting on k ∈ { 1 , 2 } k \in\{1,2\} k ∈ { 1 , 2 } qubits, define
D k , p ( ρ ) = ( 1 − p ) ρ + p Tr ( ρ ) I 2 k 2 k , p ∈ [ 0 , 1 ) . (88) \mathcal{D}_{k,p}(\rho) = (1-p)\rho+ p \operatorname{Tr}(\rho)\frac{I_{2^k}}{2^k}, \qquad p \in[0,1). \tag*{(88)} D k , p ( ρ ) = ( 1 − p ) ρ + p Tr ( ρ ) 2 k I 2 k , p ∈ [ 0 , 1 ) . (88)
Consider an ideal gate channel U g \mathcal{U}_g U g acting on k g k_g k g qubits. Under the noise model adopted in this subsection, its physical implementation is
U ~ g = D k g , p ∘ U g . (89) \widetilde{\mathcal{U}}_g = \mathcal{D}_{k_g,p} \circ\mathcal{U}_g. \tag*{(89)} U g = D k g , p ∘ U g . (89)
PEC represents the ideal gate as a signed linear combination of implementable noisy operations. For the depolarizing channel ((88) ), the resulting gate-level quasiprobability 1-norm is [22 , 7 ]
γ k ( p ) = 1 + ( 1 − 2 4 k ) p 1 − p . (90) \gamma_k(p) = \frac{1 + \left(1-\frac{2}{4^k}\right)p}{1-p}. \tag*{(90)} γ k ( p ) = 1 − p 1 + ( 1 − 4 k 2 ) p . (90)
Consequently, the quasiprobability norms associated with one noisy single-qubit gate and one noisy two-qubit gate are
γ 1 ( p ) = 1 + p / 2 1 − p , γ 2 ( p ) = 1 + 7 p / 8 1 − p . (91) \gamma_1(p) = \frac{1+p/2}{1-p}, \qquad\gamma_2(p) = \frac{1+7p/8}{1-p}. \tag*{(91)} γ 1 ( p ) = 1 − p 1 + p /2 , γ 2 ( p ) = 1 − p 1 + 7 p /8 . (91)
Here we assume single- and two-qubit gate noise are same p 1 q = p 2 q = p p_{1\mathrm{q}} = p_{2\mathrm{q}} = p p 1 q = p 2 q = p for simplicity. On hardware, these strengths are not necessarily equal and may instead satisfy p 1 q ≪ p 2 q p_{1\mathrm{q}} \ll p_{2\mathrm{q}} p 1 q ≪ p 2 q . For unequal strengths, the same formulas apply separately as γ 1 ( p 1 q ) \gamma_1(p_{1\mathrm{q}}) γ 1 ( p 1 q ) and γ 2 ( p 2 q ) \gamma_2(p_{2\mathrm{q}}) γ 2 ( p 2 q ) .
For a fixed architecture family, let G 1 ( n , d ) G_1(n,d) G 1 ( n , d ) and G 2 ( n , d ) G_2(n,d) G 2 ( n , d ) be the numbers of noisy one- and two-qubit gate locations in a circuit of width n n n and depth d d d . Under the gate-local Markovian Assumption A1 (§ 3.2 ), PEC applies an independent gate-level quasiprobability decomposition at each location. The coefficient associated with a sampled circuit is therefore the product of the coefficients selected at the individual gate locations. Accordingly, the circuit-level quasiprobability norm is:
γ ( n , d , p ) = γ 1 ( p ) G 1 ( n , d ) γ 2 ( p ) G 2 ( n , d ) . (92) \gamma(n,d,p) = \gamma_1(p)^{G_1(n,d)}\gamma_2(p)^{G_2(n,d)}. \tag*{(92)} γ ( n , d , p ) = γ 1 ( p ) G 1 ( n , d ) γ 2 ( p ) G 2 ( n , d ) . (92)
Substituting Eq. (91) gives
γ ( n , d , p ) = ( 1 + p / 2 1 − p ) G 1 ( n , d ) ( 1 + 7 p / 8 1 − p ) G 2 ( n , d ) . (93) \gamma(n,d,p) =
\left(\frac{1+p/2}{1-p}\right)^{G_1(n,d)}
\left(\frac{1+7p/8}{1-p}\right)^{G_2(n,d)}. \tag*{(93)} γ ( n , d , p ) = ( 1 − p 1 + p /2 ) G 1 ( n , d ) ( 1 − p 1 + 7 p /8 ) G 2 ( n , d ) . (93)
Using the general formula for PEC shots calculation ((87) ):
S h o t s P E C d e p o l = S h o t s n o i s e l e s s × γ c i r c 2 (94) \mathrm{Shots}_{\mathrm{PEC}}^{\mathrm{depol}} =
\mathrm{Shots}_{\mathrm{noiseless}} \times\gamma_{\mathrm{circ}}^2 \tag*{(94)} Shots PEC depol = Shots noiseless × γ circ 2 (94)
Boosting as an Alternative to Cost-Inflated PEC
Empirical Margin Target and Cost of Boosting
The boosting strategy trains noisy PQCs directly under the physical noise model and combines their deterministic mean prediction scores into an ensemble. Unlike PEC, boosting does not attempt to reconstruct the corresponding noiseless expectation values.
Recall from § 2.4 that
A T : = ∑ t = 1 T α t , F ~ T : = F T A T , (95) A_T := \sum_{t=1}^{T} \alpha_t,\qquad\widetilde{F}_T := \frac{F_T}{A_T}, \tag*{(95)} A T := t = 1 ∑ T α t , F T := A T F T , (95)
with A T > 0 A_T > 0 A T > 0 . The normalized ensemble has the same classification decisions as F T F_T F T but fixes the scale on which its margins are measured.
The empirical quantity entering the common expected-risk comparison is margin loss. Accordingly, the boosting target is
R ^ S , μ ( F ~ T ) ≤ ϵ m a r , (96) \widehat{R}_{S,\mu}\left(\widetilde{F}_T\right) \leq\epsilon_{\mathrm{mar}}, \tag*{(96)} R S , μ ( F T ) ≤ ϵ mar , (96)
where the margin threshold μ \mu μ and target ϵ m a r \epsilon_{\mathrm{mar}} ϵ mar are the same as those fixed for the ideal and PEC reference procedures in § 3.2 .
The boosting resource cost is determined by two quantities: the number of rounds required to attain Eq. (96) , and the number of expectation-value evaluations required to train and evaluate the weak learner at each round. To obtain theoretical bounds on these two quantities, we introduce the following assumptions on the weak-learning edge, its finite-shot estimation, and the cost of training the weak learners.
Assumption B1: uniform weak learnability. To state the weak-learning condition uniformly for the two algorithms considered below, let g t g_t g t denote the deterministic mean score used to compute the edge of a boosting round and update the distribution D t D^t D t :
g t = { h t , for Real AdaBoost , h ˉ t , for AdaBoostR . (97) g_t =
\begin{cases}
h_t, & \text{for Real AdaBoost},\\
\bar{h}_t, & \text{for AdaBoostR}.
\end{cases} \tag*{(97)} g t = { h t , h ˉ t , for Real AdaBoost , for AdaBoostR . (97)
Here, h t h_t h t is the mean noisy-PQC score, whereas h ˉ t = h t / h t ⋆ \bar{h}_t = h_t/h_t^\star h ˉ t = h t / h t ⋆ is the training-sample-normalized score used by AdaBoostR, where h t ⋆ = max i ∈ [ m ] ∣ h t ( x i ) ∣ h_t^\star= \max_{i\in[m]} |h_t(x_i)| h t ⋆ = max i ∈ [ m ] ∣ h t ( x i ) ∣ is the maximum absolute score on the training sample. Using the distribution D t D^t D t over the fixed training sample defined in the boosting framework, the corresponding round edge (14) is r t : = ∑ i = 1 m D t ( i ) y i g t ( x i ) r_t := \sum_{i=1}^{m} D^t(i)y_i g_t(x_i) r t := ∑ i = 1 m D t ( i ) y i g t ( x i ) . We assume that there exists a constant η > 0 \eta> 0 η > 0 such that every round satisfies
r t ≥ η , t = 1 , … , T . (98) r_t \geq\eta,\qquad t=1,\ldots,T. \tag*{(98)} r t ≥ η , t = 1 , … , T . (98)
Thus, over any fixed sequence of T T T boosting rounds, η \eta η is a lower bound on the smallest round edge,
η ≤ min 1 ≤ t ≤ T r t . \eta\leq\min_{1\leq t\leq T} r_t. η ≤ 1 ≤ t ≤ T min r t .
No monotonic behavior of the edges with t t t is assumed: as boosting progresses, the distributions D t D^t D t may concentrate on increasingly difficult examples, so the round edges may decrease. Recall from § 2.1 that efficient weak learning requires an advantage that is at least inverse-polynomial in the problem size. Accordingly, we require η ( n ) ≥ 1 / q ( n ) \eta(n) \geq1/q(n) η ( n ) ≥ 1/ q ( n ) for some polynomial q q q , rather than merely η > 0 \eta> 0 η > 0 . An exponentially small edge guarantee, such as η = e − n \eta= e^{-n} η = e − n , is insufficient for a polynomial-time boosting guarantee: amplifying such a small advantage may require exponentially many rounds.
Assumption B1 is the weak-learning condition used in the boosting convergence analysis. Establishing a positive uniform lower bound η \eta η is generally difficult, because the edge at round t t t depends on the weak-learner optimization under the adaptively reweighted distribution D t D^t D t . For a specific circuit family and noise model, deriving such a bound would constitute a separate theoretical problem. In the present work, we therefore treat r t ≥ η > 0 r_t \geq\eta> 0 r t ≥ η > 0 as an explicit assumption and estimate the realized round edges numerically.
Assumption B2: finite-shot edge accuracy. The boosting convergence results are formulated in terms of the deterministic mean update scores g t g_t g t . In practice, these scores are estimated from a finite number of circuit executions. Let g ^ t ( x i ) \hat{g}_t(x_i) g ^ t ( x i ) denote the finite-shot estimate of g t ( x i ) g_t(x_i) g t ( x i ) . For an additive expectation-value precision ε e v a l > 0 \varepsilon_{\mathrm{eval}}>0 ε eval > 0 , define
E ε e v a l B : = ⋂ ( t , i ) ∈ J B { ∣ g ^ t ( x i ) − g t ( x i ) ∣ ≤ ε e v a l } , (99) \mathcal{E}^{\mathrm{B}}_{\varepsilon_{\mathrm{eval}}} := \bigcap_{(t,i)\in\mathcal{J}_{\mathrm{B}}} \left\{|\hat{g}_t(x_i)-g_t(x_i)|\leq\varepsilon_{\mathrm{eval}}\right\}, \tag*{(99)} E ε eval B := ( t , i ) ∈ J B ⋂ { ∣ g ^ t ( x i ) − g t ( x i ) ∣ ≤ ε eval } , (99) where J B \mathcal{J}_{\mathrm{B}} J B contains the round–example pairs whose finite-shot scores are used to evaluate the boosting edges.
We choose the shot allocation so that all finite-shot scores used in the edge evaluations satisfy the accuracy requirement simultaneously with probability at least 1 − δ e s t B 1-\delta_{\mathrm{est}}^{\mathrm{B}} 1 − δ est B :
Pr ( E ε e v a l B ) ≥ 1 − δ e s t B , (100) \Pr\left(\mathcal{E}^{\mathrm{B}}_{\varepsilon_{\mathrm{eval}}}\right)\geq1-\delta_{\mathrm{est}}^{\mathrm{B}}, \tag*{(100)} Pr ( E ε eval B ) ≥ 1 − δ est B , (100) where δ e s t B \delta_{\mathrm{est}}^{\mathrm{B}} δ est B is the allowed failure probability of this finite-shot edge-estimation guarantee. For the deterministic mean edge r t = ∑ i = 1 m D t ( i ) y i g t ( x i ) r_t=\sum_{i=1}^{m}D^{t}(i)y_i g_t(x_i) r t = ∑ i = 1 m D t ( i ) y i g t ( x i ) and its finite-shot estimate r ^ t = ∑ i = 1 m D t ( i ) y i g ^ t ( x i ) \hat{r}_t=\sum_{i=1}^{m}D^{t}(i)y_i\hat{g}_t(x_i) r ^ t = ∑ i = 1 m D t ( i ) y i g ^ t ( x i ) , the event E ε e v a l B \mathcal{E}^{\mathrm{B}}_{\varepsilon_{\mathrm{eval}}} E ε eval B implies
∣ r ^ t − r t ∣ ≤ ∑ i = 1 m D t ( i ) ∣ g ^ t ( x i ) − g t ( x i ) ∣ ≤ ε e v a l , (101) |\hat{r}_t-r_t|\leq\sum_{i=1}^{m}D^{t}(i)|\hat{g}_t(x_i)-g_t(x_i)|\leq\varepsilon_{\mathrm{eval}}, \tag*{(101)} ∣ r ^ t − r t ∣ ≤ i = 1 ∑ m D t ( i ) ∣ g ^ t ( x i ) − g t ( x i ) ∣ ≤ ε eval , (101) where we used D t ( i ) ≥ 0 D^{t}(i)\geq0 D t ( i ) ≥ 0 and ∑ i D t ( i ) = 1 \sum_iD^{t}(i)=1 ∑ i D t ( i ) = 1 . Consequently, the finite-shot condition
r ^ t ≥ η + ε e v a l (102) \hat{r}_t\geq\eta+\varepsilon_{\mathrm{eval}} \tag*{(102)} r ^ t ≥ η + ε eval (102) implies, on E ε e v a l B \mathcal{E}^{\mathrm{B}}_{\varepsilon_{\mathrm{eval}}} E ε eval B ,
r t ≥ r ^ t − ε e v a l ≥ η . (103) r_t\geq\hat{r}_t-\varepsilon_{\mathrm{eval}}\geq\eta. \tag*{(103)} r t ≥ r ^ t − ε eval ≥ η . (103) Thus, sufficiently accurate finite-shot edge estimates allow the mean-edge condition in Assumption B1 to be inferred from the measured scores.
Assumption B3: average weak-learner evaluation budget. For boosting round t t t , let N e v a l , t w e a k N_{\mathrm{eval},t}^{\mathrm{weak}} N eval , t weak denote the total number of expectation-value evaluations required by the round-t t t weak learner to obtain a deterministic mean predictor satisfying Assumption B1. The count includes the expectation-value evaluations included in the specified training and round-evaluation protocol.
We assume that the average weak-learner evaluation cost over the T T T boosting rounds does not exceed the noiseless reference budget:
1 T ∑ t = 1 T N e v a l , t w e a k ≤ N n o i s e l e s s , (104) \frac{1}{T}\sum_{t=1}^{T}N_{\mathrm{eval},t}^{\mathrm{weak}}\leq N_{\mathrm{noiseless}}, \tag*{(104)} T 1 t = 1 ∑ T N eval , t weak ≤ N noiseless , (104) where N n o i s e l e s s N_{\mathrm{noiseless}} N noiseless is the reference evaluation budget introduced in § 3.3 .
An individual boosting round only needs to produce a weak hypothesis with positive edge, whereas the noiseless reference procedure must reach the final empirical margin-loss target ε m a r \varepsilon_{\mathrm{mar}} ε mar . At the same time, later boosting rounds may be more difficult because the adaptive distributions D t D^t D t concentrate weight on examples that are poorly handled by the current ensemble. Assumption B3 therefore constrains only the average cost across rounds rather than every round individually. This condition is examined numerically.
The cumulative number of expectation-value evaluations used by boosting through round T T T is
N e v a l b o o s t ( T ) : = ∑ t = 1 T N e v a l , t w e a k . (105) N_{\mathrm{eval}}^{\mathrm{boost}}(T):=\sum_{t=1}^{T}N_{\mathrm{eval},t}^{\mathrm{weak}}. \tag*{(105)} N eval boost ( T ) := t = 1 ∑ T N eval , t weak . (105) If each expectation-value evaluation uses N s h N_{\mathrm{sh}} N sh physical circuit executions, then
S h o t s b o o s t ( T ) = N e v a l b o o s t ( T ) N s h . (106) \mathrm{Shots}_{\mathrm{boost}}(T)=N_{\mathrm{eval}}^{\mathrm{boost}}(T)N_{\mathrm{sh}}. \tag*{(106)} Shots boost ( T ) = N eval boost ( T ) N sh . (106)
Under Assumption B3,
S h o t s b o o s t ( T ) ≤ T N n o i s e l e s s N s h = T S h o t s n o i s e l e s s . (107) \mathrm{Shots}_{\mathrm{boost}}(T) \leq T N_{\mathrm{noiseless}}N_{\mathrm{sh}} = T\mathrm{Shots}_{\mathrm{noiseless}}. \tag*{(107)} Shots boost ( T ) ≤ T N noiseless N sh = T Shots noiseless . (107)
Thus, the remaining algorithm-specific problem is to determine a sufficient number of rounds T T T for which the normalized ensemble satisfies the common margin-loss target in Eq. (96) . This target depends on the particular boosting rule used to form the ensemble. We therefore derive the required round conditions separately for Real AdaBoost and AdaBoostR below.
The empirical 0–1 classification-error bounds are retained as secondary consequences, but they are not used as substitutes for the positive-margin quantity appearing in the expected-risk comparison.
Real AdaBoost Margin-Loss Bound
We apply the standard boosting margin analysis [15 , 20 ] to obtain a sufficient number of Real AdaBoost rounds for attaining the common empirical margin-loss target R ^ S , μ ( F ~ T ) ≤ ε m a r \widehat{R}_{S,\mu}(\widetilde{F}_T) \leq\varepsilon_{\mathrm{mar}} R S , μ ( F T ) ≤ ε mar . We use the Real AdaBoost definitions and exponential-potential relations established in § 2.3 , in particular Eqs. (23) , (26) , and (25) . Recall also the normalized ensemble used in the generalization analysis:
F ~ T = F T A T , A T = ∑ t = 1 T α t = ∥ α ∥ 1 , \widetilde{F}_T = \frac{F_T}{A_T}, \qquad A_T = \sum_{t=1}^{T}\alpha_t = \lVert\alpha\rVert_1, F T = A T F T , A T = t = 1 ∑ T α t = ∥ α ∥ 1 ,
where the last equality follows from the positive-edge convention. By Eq. (58) , the empirical margin loss is upper-bounded by the corresponding empirical margin error:
R ^ S , μ ( F ~ T ) ≤ R ^ S , μ m a r ( F ~ T ) = 1 m ∑ i = 1 m I { y i F ~ T ( x i ) ≤ μ } = 1 m ∑ i = 1 m I { y i F T ( x i ) ≤ μ A T } . \widehat{R}_{S,\mu}(\widetilde{F}_T) \leq\widehat{R}^{\mathrm{mar}}_{S,\mu}(\widetilde{F}_T) = \frac{1}{m}\sum_{i=1}^{m}\mathbb{I}\left\{y_i\widetilde{F}_T(x_i)\leq\mu\right\} = \frac{1}{m}\sum_{i=1}^{m}\mathbb{I}\left\{y_iF_T(x_i)\leq\mu A_T\right\}. R S , μ ( F T ) ≤ R S , μ mar ( F T ) = m 1 i = 1 ∑ m I { y i F T ( x i ) ≤ μ } = m 1 i = 1 ∑ m I { y i F T ( x i ) ≤ μ A T } .
Thus, the empirical margin error is used as an intermediate upper bound on the empirical margin loss appearing in the generalization analysis.
Using I { z ≤ 0 } ≤ e − z \mathbb{I}\{z\leq0\}\leq e^{-z} I { z ≤ 0 } ≤ e − z with z = y i F T ( x i ) − μ A T z=y_iF_T(x_i)-\mu A_T z = y i F T ( x i ) − μ A T , together with the Real AdaBoost exponential-potential relation established in § 2.3 , gives
R ^ S , μ ( F ~ T ) ≤ e μ A T 1 m ∑ i = 1 m e − y i F T ( x i ) = e μ A T ∏ t = 1 T Z t ( α t ) ≤ ∏ t = 1 T e μ α t 1 − r t 2 , \widehat{R}_{S,\mu}(\widetilde{F}_T) \leq e^{\mu A_T}\frac{1}{m}\sum_{i=1}^{m}e^{-y_iF_T(x_i)} = e^{\mu A_T}\prod_{t=1}^{T}Z_t(\alpha_t) \leq\prod_{t=1}^{T}e^{\mu\alpha_t}\sqrt{1-r_t^2}, R S , μ ( F T ) ≤ e μ A T m 1 i = 1 ∑ m e − y i F T ( x i ) = e μ A T t = 1 ∏ T Z t ( α t ) ≤ t = 1 ∏ T e μ α t 1 − r t 2 ,
where the final inequality follows from Eq. (26) .
Using the coefficient expression Eq. (25) , each factor in this product bound can be written as
e μ α t 1 − r t 2 = ( 1 + r t 1 − r t ) μ / 2 ( 1 − r t ) ( 1 + r t ) = ( 1 − r t ) 1 − μ ( 1 + r t ) 1 + μ . e^{\mu\alpha_t}\sqrt{1-r_t^2} = \left(\frac{1+r_t}{1-r_t}\right)^{\mu/2}\sqrt{(1-r_t)(1+r_t)} = \sqrt{(1-r_t)^{1-\mu}(1+r_t)^{1+\mu}}. e μ α t 1 − r t 2 = ( 1 − r t 1 + r t ) μ /2 ( 1 − r t ) ( 1 + r t ) = ( 1 − r t ) 1 − μ ( 1 + r t ) 1 + μ .
Define
b μ ( r ) : = ( 1 − r ) 1 − μ ( 1 + r ) 1 + μ . (108) b_\mu(r) := \sqrt{(1-r)^{1-\mu}(1+r)^{1+\mu}}. \tag*{(108)} b μ ( r ) := ( 1 − r ) 1 − μ ( 1 + r ) 1 + μ . (108)
We therefore obtain
R ^ S , μ ( F ~ T ) ≤ ∏ t = 1 T b μ ( r t ) . (109) \widehat{R}_{S,\mu}(\widetilde{F}_T) \leq\prod_{t=1}^{T}b_\mu(r_t). \tag*{(109)} R S , μ ( F T ) ≤ t = 1 ∏ T b μ ( r t ) . (109)
To express this bound through the uniform weak-edge parameter η \eta η from Assumption B1, note that
d d r log b μ ( r ) = μ − r 1 − r 2 . (110) \frac{\mathrm{d}}{\mathrm{d}r}\log b_\mu(r) = \frac{\mu-r}{1-r^2}. \tag*{(110)} d r d log b μ ( r ) = 1 − r 2 μ − r . (110)
Hence b μ ( r ) b_\mu(r) b μ ( r ) is decreasing for r > μ r>\mu r > μ . If r t ≥ η > μ r_t\geq\eta>\mu r t ≥ η > μ for all t t t , then b μ ( r t ) ≤ b μ ( η ) b_\mu(r_t)\leq b_\mu(\eta) b μ ( r t ) ≤ b μ ( η ) . Define
B r e a l ( μ , η ) : = b μ ( η ) = ( 1 − η ) 1 − μ ( 1 + η ) 1 + μ . (111) B_{\mathrm{real}}(\mu,\eta) := b_\mu(\eta) = \sqrt{(1-\eta)^{1-\mu}(1+\eta)^{1+\mu}}. \tag*{(111)} B real ( μ , η ) := b μ ( η ) = ( 1 − η ) 1 − μ ( 1 + η ) 1 + μ . (111)
Equation (109) then implies
R ^ S , μ ( F ~ T ) ≤ [ B r e a l ( μ , η ) ] T . (112) \widehat{R}_{S,\mu}(\widetilde{F}_T) \leq[B_{\mathrm{real}}(\mu,\eta)]^T. \tag*{(112)} R S , μ ( F T ) ≤ [ B real ( μ , η ) ] T . (112)
For this upper bound to decrease geometrically with the number of boosting rounds, we require
B r e a l ( μ , η ) < 1. (113) B_{\mathrm{real}}(\mu,\eta)<1. \tag*{(113)} B real ( μ , η ) < 1. (113)
From Eq. (111) , this condition is equivalent to
μ < − log ( 1 − η 2 ) log ( 1 + η 1 − η ) . (114) \mu<\frac{-\log(1-\eta^2)}{\log\left(\frac{1+\eta}{1-\eta}\right)}. \tag*{(114)} μ < log ( 1 − η 1 + η ) − log ( 1 − η 2 ) . (114)
Thus, a positive uniform edge alone does not guarantee geometric decay at an arbitrary margin threshold. The margin threshold μ \mu μ , fixed as part of the common comparison target in § 3.2 , and the weak-edge lower bound η \eta η must satisfy Eq. (114) . A simpler sufficient condition for this compatibility relation is
μ < η 2 . (115) \mu<\frac{\eta}{2}. \tag*{(115)} μ < 2 η . (115)
This is not an additional assumption; it is a convenient sufficient condition under which the exact contraction condition Eq. (114) is guaranteed.
Whenever B r e a l ( μ , η ) < 1 B_{\mathrm{real}}(\mu,\eta)<1 B real ( μ , η ) < 1 , the common margin-loss target ε m a r \varepsilon_{\mathrm{mar}} ε mar is guaranteed if
[ B r e a l ( μ , η ) ] T ≤ ε m a r . (116) [B_{\mathrm{real}}(\mu,\eta)]^T\leq\varepsilon_{\mathrm{mar}}. \tag*{(116)} [ B real ( μ , η ) ] T ≤ ε mar . (116)
Accordingly, the sufficient Real AdaBoost round budget
T r e a l ( m a r ) ( η , μ , ε m a r ) ≔ ⌈ log ( 1 / ε m a r ) − log B r e a l ( μ , η ) ⌉ (117) T_{\mathrm{real}}^{(\mathrm{mar})}(\eta,\mu,\varepsilon_{\mathrm{mar}})\coloneqq\left\lceil\frac{\log(1/\varepsilon_{\mathrm{mar}})}{-\log B_{\mathrm{real}}(\mu,\eta)}\right\rceil \tag*{(117)} T real ( mar ) ( η , μ , ε mar ) : = ⌈ − log B real ( μ , η ) log ( 1/ ε mar ) ⌉ (117)
The exact exponent governing this round bound is
− log B r e a l ( μ , η ) = 1 2 [ − log ( 1 − η 2 ) − μ log ( 1 + η 1 − η ) ] . (118) -\log B_{\mathrm{real}}(\mu,\eta)=\frac{1}{2}\left[-\log(1-\eta^2)-\mu\log\left(\frac{1+\eta}{1-\eta}\right)\right]. \tag*{(118)} − log B real ( μ , η ) = 2 1 [ − log ( 1 − η 2 ) − μ log ( 1 − η 1 + η ) ] . (118)
This expression shows explicitly how the convergence rate depends jointly on the weak edge and the prescribed normalized margin threshold.
To extract the small-edge scaling of the round bound, consider a family of settings in which the margin threshold is chosen proportionally to the weak edge,
μ = c η , 0 < c < 1 2 . (119) \mu=c\eta,\qquad0<c<\frac{1}{2}. \tag*{(119)} μ = cη , 0 < c < 2 1 . (119)
This proportional scaling is not required for the exact bound above; it specifies an asymptotic regime in which the contraction condition continues to hold as η → 0 \eta\to0 η → 0 . In this regime,
− log B r e a l ( c η , η ) = ( 1 2 − c ) η 2 + O ( η 4 ) . (120) -\log B_{\mathrm{real}}(c\eta,\eta)=\left(\frac{1}{2}-c\right)\eta^2+O(\eta^4). \tag*{(120)} − log B real ( cη , η ) = ( 2 1 − c ) η 2 + O ( η 4 ) . (120)
Consequently, under this small-edge scaling regime:
T r e a l ( m a r ) = O ( 1 η 2 log 1 ε m a r ) . (121) T_{\mathrm{real}}^{(\mathrm{mar})}=O\left(\frac{1}{\eta^2}\log\frac{1}{\varepsilon_{\mathrm{mar}}}\right). \tag*{(121)} T real ( mar ) = O ( η 2 1 log ε mar 1 ) . (121)
Thus, Real AdaBoost has an explicit sufficient resource bound for attaining the common empirical margin-loss target. This is the Real AdaBoost quantity used in the subsequent comparison with PEC.
AdaBoostR Margin-Loss Bound
We next derive the corresponding margin-loss condition for AdaBoostR. The convergence result [16 ] that we use is formulated in terms of a logistic transformation of the ensemble margin. We therefore first relate this logistic-margin bound to the normalized linear margin used in the generalization analysis. We use the AdaBoostR definitions established in § 2.3 . In particular, the round edge r t r_t r t is computed from the training-sample-normalized weak score h ˉ t \bar{h}_t h ˉ t , and the resulting ensemble is
F T ( x ) = ∑ t = 1 T α t h t ( x ) . F_T(x)=\sum_{t=1}^{T}\alpha_t h_t(x). F T ( x ) = t = 1 ∑ T α t h t ( x ) .
As in the preceding analysis, we consider the normalized ensemble
F ~ T = F T A T , A T : = ∑ t = 1 T α t = ∥ α ∥ 1 , (122) \widetilde{F}_T = \frac{F_T}{A_T}, \qquad A_T := \sum_{t=1}^{T} \alpha_t = \lVert\alpha\rVert_1, \tag*{(122)} F T = A T F T , A T := t = 1 ∑ T α t = ∥ α ∥ 1 , (122)
where the last equality follows from the positive-edge convention. The AdaBoostR analysis associates with F T F_T F T the logistic margin
ϑ T ( x , y ) : = tanh ( y F T ( x ) 2 ) . (123) \vartheta_T(x,y) := \tanh\left(\frac{yF_T(x)}{2}\right). \tag*{(123)} ϑ T ( x , y ) := tanh ( 2 y F T ( x ) ) . (123)
Recall that the initial training distribution is uniform, D 1 ( i ) = 1 / m D^1(i)=1/m D 1 ( i ) = 1/ m . For the ensemble F T F_T F T after T T T boosting rounds, define the empirical logistic-margin error at threshold τ ∈ [ 0 , 1 ) \tau\in[0,1) τ ∈ [ 0 , 1 ) by
ω D 1 , F T , τ : = ∑ i = 1 m D 1 ( i ) I { ϑ T ( x i , y i ) ≤ τ } = 1 m ∑ i = 1 m I { ϑ T ( x i , y i ) ≤ τ } . (124) \omega_{D^1,F_T,\tau} := \sum_{i=1}^{m} D^1(i)\mathbb{I}\{\vartheta_T(x_i,y_i)\leq\tau\} = \frac{1}{m}\sum_{i=1}^{m}\mathbb{I}\{\vartheta_T(x_i,y_i)\leq\tau\}. \tag*{(124)} ω D 1 , F T , τ := i = 1 ∑ m D 1 ( i ) I { ϑ T ( x i , y i ) ≤ τ } = m 1 i = 1 ∑ m I { ϑ T ( x i , y i ) ≤ τ } . (124)
This error is evaluated under the fixed uniform distribution D 1 D^1 D 1 , not the reweighted distribution D T D^T D T used during training. Applying the AdaBoostR margin bound [16 Theorem 1] to our deterministic-label setting, in which the empirical Bayes error is zero, gives, for τ ∈ [ 0 , 1 ) \tau\in[0,1) τ ∈ [ 0 , 1 ) ,
ω D 1 , F T , τ ≤ 1 + τ 1 − τ exp ( − 1 2 ∑ t = 1 T r t 2 ) . (125) \omega_{D^1,F_T,\tau} \leq\frac{1+\tau}{1-\tau}\exp\left(-\frac{1}{2}\sum_{t=1}^{T}r_t^2\right). \tag*{(125)} ω D 1 , F T , τ ≤ 1 − τ 1 + τ exp ( − 2 1 t = 1 ∑ T r t 2 ) . (125)
We now translate this result to the common empirical margin-loss target ε m a r \varepsilon_{\mathrm{mar}} ε mar . By Eq. (58) ,
R ^ S , μ ( F ~ T ) ≤ R ^ S , μ m a r ( F ~ T ) = 1 m ∑ i = 1 m I { y i F ~ T ( x i ) ≤ μ } = 1 m ∑ i = 1 m I { y i F T ( x i ) ≤ μ A T } . \widehat{R}_{S,\mu}\left(\widetilde{F}_T\right) \leq\widehat{R}^{\mathrm{mar}}_{S,\mu}\left(\widetilde{F}_T\right) = \frac{1}{m}\sum_{i=1}^{m}\mathbb{I}\{y_i\widetilde{F}_T(x_i)\leq\mu\} = \frac{1}{m}\sum_{i=1}^{m}\mathbb{I}\{y_iF_T(x_i)\leq\mu A_T\}. R S , μ ( F T ) ≤ R S , μ mar ( F T ) = m 1 i = 1 ∑ m I { y i F T ( x i ) ≤ μ } = m 1 i = 1 ∑ m I { y i F T ( x i ) ≤ μ A T } .
Because tanh ( ⋅ ) \tanh(\cdot) tanh ( ⋅ ) is strictly increasing, define
τ μ , T : = tanh ( μ A T 2 ) . (126) \tau_{\mu,T}:=\tanh\left(\frac{\mu A_T}{2}\right). \tag*{(126)} τ μ , T := tanh ( 2 μ A T ) . (126)
Then
y i F T ( x i ) ≤ μ A T ⟺ ϑ T ( x i , y i ) ≤ τ μ , T , y_iF_T(x_i)\leq\mu A_T \quad\Longleftrightarrow\quad\vartheta_T(x_i,y_i)\leq\tau_{\mu,T}, y i F T ( x i ) ≤ μ A T ⟺ ϑ T ( x i , y i ) ≤ τ μ , T ,
and therefore
R ^ S , μ ( F ~ T ) ≤ ω D 1 , F T , τ μ , T . (127) \widehat{R}_{S,\mu}\left(\widetilde{F}_T\right)\leq\omega_{D^1,F_T,\tau_{\mu,T}}. \tag*{(127)} R S , μ ( F T ) ≤ ω D 1 , F T , τ μ , T . (127)
Applying Eq. (125) at τ = τ μ , T \tau=\tau_{\mu,T} τ = τ μ , T gives
R ^ S , μ ( F ~ T ) ≤ 1 + τ μ , T 1 − τ μ , T exp ( − 1 2 ∑ t = 1 T r t 2 ) . (128) \widehat{R}_{S,\mu}\left(\widetilde{F}_T\right)\leq\frac{1+\tau_{\mu,T}}{1-\tau_{\mu,T}}\exp\left(-\frac{1}{2}\sum_{t=1}^{T}r_t^2\right). \tag*{(128)} R S , μ ( F T ) ≤ 1 − τ μ , T 1 + τ μ , T exp ( − 2 1 t = 1 ∑ T r t 2 ) . (128)
Using
1 + tanh ( z / 2 ) 1 − tanh ( z / 2 ) = e z , (129) \frac{1+\tanh(z/2)}{1-\tanh(z/2)}=e^z, \tag*{(129)} 1 − tanh ( z /2 ) 1 + tanh ( z /2 ) = e z , (129)
with z = μ A T z=\mu A_T z = μ A T , we obtain
R ^ S , μ ( F ~ T ) ≤ exp ( μ A T − 1 2 ∑ t = 1 T r t 2 ) . (130) \widehat{R}_{S,\mu}\left(\widetilde{F}_T\right)\leq\exp\left(\mu A_T-\frac{1}{2}\sum_{t=1}^{T}r_t^2\right). \tag*{(130)} R S , μ ( F T ) ≤ exp ( μ A T − 2 1 t = 1 ∑ T r t 2 ) . (130)
For convenience, define the accumulated squared edge
E T : = ∑ t = 1 T r t 2 (131) E_T:=\sum_{t=1}^{T}r_t^2 \tag*{(131)} E T := t = 1 ∑ T r t 2 (131)
and the corresponding normalized-margin progress quantity
Q T ( μ ) : = E T − 2 μ A T . (132) Q_T(\mu) := E_T - 2\mu A_T. \tag*{(132)} Q T ( μ ) := E T − 2 μ A T . (132)
Equation (130) can then be written as
R ^ S , μ ( F ~ T ) ≤ exp ( − Q T ( μ ) 2 ) . (133) \widehat{R}_{S,\mu}(\widetilde{F}_T) \le\exp\left(-\frac{Q_T(\mu)}{2}\right). \tag*{(133)} R S , μ ( F T ) ≤ exp ( − 2 Q T ( μ ) ) . (133)
Hence the common empirical margin-loss target ε m a r \varepsilon_{\mathrm{mar}} ε mar is guaranteed whenever
Q T ( μ ) ≥ 2 log ( 1 ε m a r ) , (134) Q_T(\mu) \ge2\log\left(\frac{1}{\varepsilon_{\mathrm{mar}}}\right), \tag*{(134)} Q T ( μ ) ≥ 2 log ( ε mar 1 ) , (134)
or, equivalently,
E T − 2 μ A T ≥ 2 log ( 1 ε m a r ) . (135) E_T - 2\mu A_T \ge2\log\left(\frac{1}{\varepsilon_{\mathrm{mar}}}\right). \tag*{(135)} E T − 2 μ A T ≥ 2 log ( ε mar 1 ) . (135)
We therefore define the trajectory-dependent sufficient round index:
T R ( m a r ) ( μ , ε m a r ) : = min { T ∈ N : E T − 2 μ A T ≥ 2 log ( 1 ε m a r ) } . (136) T_{\mathrm{R}}^{(\mathrm{mar})}(\mu,\varepsilon_{\mathrm{mar}}) := \min\left\{T \in\mathbb{N}: E_T - 2\mu A_T \ge2\log\left(\frac{1}{\varepsilon_{\mathrm{mar}}}\right)\right\}. \tag*{(136)} T R ( mar ) ( μ , ε mar ) := min { T ∈ N : E T − 2 μ A T ≥ 2 log ( ε mar 1 ) } . (136)
The dependence on the realized coefficient norm A T A_T A T is important. From the AdaBoostR coefficient definition introduced in § 2.3 ,
A T = ∑ t = 1 T α t = ∑ t = 1 T arctanh ( r t ) h t ∗ , (137) A_T = \sum_{t=1}^{T}\alpha_t = \sum_{t=1}^{T}\frac{\operatorname{arctanh}(r_t)}{h_t^*}, \tag*{(137)} A T = t = 1 ∑ T α t = t = 1 ∑ T h t ∗ arctanh ( r t ) , (137)
where h t ∗ = max i ∈ [ m ] ∣ h t ( x i ) ∣ h_t^*=\max_{i\in[m]}|h_t(x_i)| h t ∗ = max i ∈ [ m ] ∣ h t ( x i ) ∣ . At this stage, A T A_T A T is determined exactly by the realized boosting trajectory. The resulting margin condition is nevertheless sufficient rather than exact, because the derivation first upper-bounds the empirical margin loss by the empirical margin error and then applies the logistic-margin bound [16 ] . Assumption B1 implies
E T = ∑ t = 1 T r t 2 ≥ T η 2 , (138) E_T = \sum_{t=1}^{T}r_t^2 \ge T\eta^2, \tag*{(138)} E T = t = 1 ∑ T r t 2 ≥ T η 2 , (138)
but this lower bound alone is insufficient to control the positive-margin term in Eq. (130) . Indeed, the condition r t ≥ η r_t \ge\eta r t ≥ η does not provide an upper bound on A T A_T A T : the realized edges may approach one, and the normalization factors h t ∗ h_t^* h t ∗ may become small.
Consequently, unlike the Real AdaBoost result, Assumption B1 alone does not yield an a priori AdaBoostR round budget in terms of the uniform lower bound η \eta η of the edge together with the fixed comparison parameters μ \mu μ and ε m a r \varepsilon_{\mathrm{mar}} ε mar . For a realized AdaBoostR trajectory, however, both E T E_T E T and A T A_T A T are known after each round. Hence Eq. (135) is a trajectory-dependent sufficient condition for the empirical margin loss target under its stated assumptions; failing this condition does not imply that the target has not been reached.
These assumptions should control the coefficient growth. For example, if r t ≤ ρ < 1 r_t \le\rho< 1 r t ≤ ρ < 1 and h t ∗ ≥ κ > 0 h_t^* \ge\kappa> 0 h t ∗ ≥ κ > 0 uniformly over the boosting rounds, then
A T ≤ T arctanh ( ρ ) κ . A_T \le T\frac{\operatorname{arctanh}(\rho)}{\kappa}. A T ≤ T κ arctanh ( ρ ) .
We do not impose these additional assumptions in the present analysis. Instead, the AdaBoostR margin condition is evaluated from the realized boosting trajectory.
We have now derived the analytical resource conditions needed for PEC, Real AdaBoost, and AdaBoostR. In the next section, we collect these results into a common resource comparison and identify the quantities that remain to be determined numerically. In particular, the numerical analysis will evaluate the realized boosting edges and weak-learner evaluation costs, and, for AdaBoostR, the trajectory-dependent quantities E T E_T E T and A T A_T A T entering Eq. (135) .
Theoretical Comparative Analysis
The preceding sections provided the derivations needed to compare probabilistic error cancellation (PEC) and boosting at a common statistical target. The quantity of interest is the expected 0–1 classification risk, while the empirical quantity used in the comparison is the margin loss R ^ S , μ ( f ) \widehat{R}_{S,\mu}(f) R S , μ ( f ) . We now identify a common hypothesis class for the generalization bound, summarize the assumptions entering the resource analysis, and combine the method-specific results of § 4.1 –§ 5.3 into a single resource comparison.
Common Hypothesis Class and Expected-Risk Bound
The general comparison principle of § 2.4 requires PEC and boosting to be bounded using the same reference hypothesis class. We therefore define
H r e f , ± : = H d , ± n o i s e l e s s . (139) \mathcal{H}_{\mathrm{ref},\pm} := \mathcal{H}^{\mathrm{noiseless}}_{d,\pm}. \tag*{(139)} H ref , ± := H d , ± noiseless . (139)
For PEC, Eq. (75) gives
H d P E C , m e a n = H d n o i s e l e s s . (140) \mathcal{H}^{\mathrm{PEC,mean}}_{d} = \mathcal{H}^{\mathrm{noiseless}}_{d}. \tag*{(140)} H d PEC , mean = H d noiseless . (140)
Hence the deterministic PEC mean predictor belongs directly to the noiseless reference class. For boosting, we use the structural result established in Appendix § 11 . Under the Pauli-noise and circuit architecture conditions stated there,
H d n o i s y ⊆ conv ( H d n o i s e l e s s ) . (141) \mathcal{H}^{\mathrm{noisy}}_{d} \subseteq\operatorname{conv}\left(\mathcal{H}^{\mathrm{noiseless}}_{d}\right). \tag*{(141)} H d noisy ⊆ conv ( H d noiseless ) . (141)
Because the boosting procedure may reverse the sign of a weak hypothesis, the relevant signed noisy class is correspondingly contained in conv ( H r e f , ± ) \operatorname{conv}(\mathcal{H}_{\mathrm{ref},\pm}) conv ( H ref , ± ) . The normalized boosting ensemble is a convex combination of these signed weak hypotheses and therefore satisfies
F ~ T ∈ conv ( H r e f , ± ) . (142) \widetilde{F}_{T} \in\operatorname{conv}\left(\mathcal{H}_{\mathrm{ref},\pm}\right). \tag*{(142)} F T ∈ conv ( H ref , ± ) . (142)
Importantly, Eq. (141) is an inclusion, not an equality of the noisy and noiseless hypothesis classes. The purpose of introducing H r e f , ± \mathcal{H}_{\mathrm{ref},\pm} H ref , ± is instead to place both strategies under the same upper bound on the complexity contribution. Define
Δ g e n ( μ , m , δ ) : = 2 μ R m ( H r e f , ± ) + log ( 1 / δ ) 2 m . (143) \Delta_{\mathrm{gen}}(\mu,m,\delta) := \frac{2}{\mu}\mathfrak{R}_{m}\left(\mathcal{H}_{\mathrm{ref},\pm}\right) + \sqrt{\frac{\log(1/\delta)}{2m}}. \tag*{(143)} Δ gen ( μ , m , δ ) := μ 2 R m ( H ref , ± ) + 2 m log ( 1/ δ ) . (143)
By Theorem 1, both the deterministic PEC mean predictor and the normalized boosting ensemble can therefore be bounded as
R ( f , c ) ≤ R ^ S , μ ( f ) + Δ g e n ( μ , m , δ ) . (144) R(f,c) \leq\widehat{R}_{S,\mu}(f) + \Delta_{\mathrm{gen}}(\mu,m,\delta). \tag*{(144)} R ( f , c ) ≤ R S , μ ( f ) + Δ gen ( μ , m , δ ) . (144)
Consequently, if either strategy attains the common empirical target R ^ S , μ ( f ) ≤ ϵ m a r \widehat{R}_{S,\mu}(f) \leq\epsilon_{\mathrm{mar}} R S , μ ( f ) ≤ ϵ mar , then
R ( f , c ) ≤ ϵ m a r + Δ g e n ( μ , m , δ ) . (145) R(f,c) \leq\epsilon_{\mathrm{mar}} + \Delta_{\mathrm{gen}}(\mu,m,\delta). \tag*{(145)} R ( f , c ) ≤ ϵ mar + Δ gen ( μ , m , δ ) . (145)
Thus, the resource comparison below concerns the cost required to attain the same upper bound on expected classification risk, rather than equality of the unknown expected risks themselves.
Assumptions Entering the Comparison
For clarity, Table 1 –Table 3 summarize the assumptions introduced in § 3.2 –§ 5.1 . The hypothesis-class containment in Eq. (141) is not listed as an additional learning assumption: under the Pauli-noise and circuit architecture conditions used in this work, it is the structural result proved in Appendix § 11 .
Table 1. Assumptions common to the ideal reference problem and the PEC–boosting comparison.
Table 3. Additional assumptions specific to boosting.
Table 2. Additional assumptions specific to probabilistic error cancellation.
Expected-Risk-Aligned Resource Comparison
Recall from § 3.3 that:
S h o t s n o i s e l e s s = N n o i s e l e s s N s h . (146) \mathrm{Shots}_{\mathrm{noiseless}} = N_{\mathrm{noiseless}}N_{\mathrm{sh}}. \tag*{(146)} Shots noiseless = N noiseless N sh . (146)
We can now state the central comparison result.
Theorem 2 (Expected-risk-aligned resource comparison for PEC and boosting). Fix μ ∈ ( 0 , 1 ] \mu\in(0,1] μ ∈ ( 0 , 1 ] , ε m a r ∈ ( 0 , 1 ) \varepsilon_{\mathrm{mar}} \in(0,1) ε mar ∈ ( 0 , 1 ) , m ∈ N m \in\mathbb{N} m ∈ N , and δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) . Assume A 1 A1 A 1 –A 3 A3 A 3 and the common-reference-class condition Eq. (141) .
Let f P E C f_{\mathrm{PEC}} f PEC denote the deterministic PEC mean predictor and let f A f_A f A denote the normalized ensemble produced by a boosting algorithm A ∈ { Real Adaboost , AdaboostR } A \in\{\text{Real Adaboost},\text{AdaboostR}\} A ∈ { Real Adaboost , AdaboostR } .
If
R ^ S , μ ( f P E C ) ≤ ε m a r , R ^ S , μ ( f A ) ≤ ε m a r , (147) \widehat{R}_{S,\mu}(f_{\mathrm{PEC}}) \le\varepsilon_{\mathrm{mar}}, \qquad\widehat{R}_{S,\mu}(f_A) \le\varepsilon_{\mathrm{mar}}, \tag*{(147)} R S , μ ( f PEC ) ≤ ε mar , R S , μ ( f A ) ≤ ε mar , (147) then, with probability at least 1 − δ 1-\delta 1 − δ over the draw of the training sample,
R ( f P E C , c ) ≤ ε m a r + Δ g e n ( μ , m , δ ) , (148) R(f_{\mathrm{PEC}},c) \le\varepsilon_{\mathrm{mar}} + \Delta_{\mathrm{gen}}(\mu,m,\delta), \tag*{(148)} R ( f PEC , c ) ≤ ε mar + Δ gen ( μ , m , δ ) , (148) and
R ( f A , c ) ≤ ε m a r + Δ g e n ( μ , m , δ ) . (149) R(f_A,c) \le\varepsilon_{\mathrm{mar}} + \Delta_{\mathrm{gen}}(\mu,m,\delta). \tag*{(149)} R ( f A , c ) ≤ ε mar + Δ gen ( μ , m , δ ) . (149) Hence both strategies attain the same high-probability upper bound on expected 0–1 classification risk.
Under P 1 P1 P 1 –P 3 P3 P 3 and the matched per-evaluation precision used in § 3.3 and § 4.2 , a sufficient PEC shot budget is
S h o t s P E C s u f f ≤ γ 2 N n o i s e l e s s N s h = γ 2 S h o t s n o i s e l e s s . (150) \mathrm{Shots}_{\mathrm{PEC}}^{\mathrm{suff}} \le\gamma^{2}N_{\mathrm{noiseless}}N_{\mathrm{sh}} = \gamma^{2}\mathrm{Shots}_{\mathrm{noiseless}}. \tag*{(150)} Shots PEC suff ≤ γ 2 N noiseless N sh = γ 2 Shots noiseless . (150) For boosting algorithm A A A , let T A ( m a r ) T_A^{(\mathrm{mar})} T A ( mar ) be a sufficient round index for attaining Eq. (147) , and define
N e v a l A ( T A ( m a r ) ) : = ∑ t = 1 T A ( m a r ) N e v a l , t w e a k . (151) N_{\mathrm{eval}}^{A}\left(T_A^{(\mathrm{mar})}\right) := \sum_{t=1}^{T_A^{(\mathrm{mar})}} N_{\mathrm{eval},t}^{\mathrm{weak}}. \tag*{(151)} N eval A ( T A ( mar ) ) := t = 1 ∑ T A ( mar ) N eval , t weak . (151) Its corresponding shot cost is
S h o t s A = N e v a l A ( T A ( m a r ) ) N s h . (152) \mathrm{Shots}_A = N_{\mathrm{eval}}^{A}\left(T_A^{(\mathrm{mar})}\right)N_{\mathrm{sh}}. \tag*{(152)} Shots A = N eval A ( T A ( mar ) ) N sh . (152) Under Assumption B 3 B3 B 3 (5.1),
S h o t s A ≤ T A ( m a r ) S h o t s n o i s e l e s s . (153) \mathrm{Shots}_A \le T_A^{(\mathrm{mar})}\mathrm{Shots}_{\mathrm{noiseless}}. \tag*{(153)} Shots A ≤ T A ( mar ) Shots noiseless . (153)
Proof. For PEC, Eq. (75) implies that the deterministic mean predictor belongs to H d n o i s e l e s s \mathcal{H}_{d}^{\mathrm{noiseless}} H d noiseless and hence to conv ( H r e f , ± ) \operatorname{conv}(\mathcal{H}_{\mathrm{ref},\pm}) conv ( H ref , ± ) .
For boosting, Eq. (141) places every noisy base predictor in the convex hull of the noiseless class. Allowing the sign reversal used by the boosting procedures places every accepted signed weak hypothesis in conv ( H r e f , ± ) \operatorname{conv}(\mathcal{H}_{\mathrm{ref},\pm}) conv ( H ref , ± ) . Because the normalized ensemble is itself a convex combination of these hypotheses, Eq. (142) follows.
Theorem 1 can therefore be applied to both predictors using the same reference complexity term Eq. (143) . Combining that result with Eq. (147) yields Eqs. (148) and (149) .
For PEC, Assumption P3 bounds the number of expectation-value evaluations by the ideal reference budget, while PEC multiplies the required number of shots per evaluation by γ 2 \gamma^{2} γ 2 at matched additive precision and confidence. This gives Eq. (150) .
For boosting, summing the weak-learner evaluation counts through the first sufficient round gives Eq. (151) . Multiplication by N s h N_{\mathrm{sh}} N sh gives Eq. (152) , and Assumption B3 (5.1) yields Eq. (153) .
Theorem 2 separates the statistical statement from the resource statement. Equality of the empirical margin-loss targets does not imply equality of the unknown expected risks. Rather, because both methods are bounded using the same reference class, it gives the same high-probability upper bound on expected classification risk. The resource comparison then asks how many physical circuit executions each method requires to attain that common empirical target.
The most direct resource criterion is obtained before applying Assumption B3 (5.1). For either boosting algorithm A \mathcal{A} A , the boosting evaluation count is smaller than the PEC reference-schedule cost whenever
N e v a l A ( T A ( m a r ) ) < γ 2 N n o i s e l e s s . (154) N_{\mathrm{eval}}^{\mathcal{A}}\left(T_{\mathcal{A}}^{(\mathrm{mar})}\right) < \gamma^{2}N_{\mathrm{noiseless}}. \tag*{(154)} N eval A ( T A ( mar ) ) < γ 2 N noiseless . (154)
This is the form used most naturally in numerical experiments, where the expectation-value evaluations can be counted directly. Assumption B3 (§ 5.1 ) gives the simpler sufficient comparison
T A ( m a r ) < γ 2 . (155) T_{\mathcal{A}}^{(\mathrm{mar})} < \gamma^{2}. \tag*{(155)} T A ( mar ) < γ 2 . (155)
Algorithm-Specific Forms of the Crossover
The general criterion Eq. (154) takes different forms for Real AdaBoost and AdaBoostR because their positive-margin guarantees have different structures.
Real AdaBoost. Under Assumption B1 and the contraction condition B r e a l ( μ , η ) < 1 B_{\mathrm{real}}(\mu,\eta)<1 B real ( μ , η ) < 1 , § 5.2 gives
T r e a l ( m a r ) ( η , μ , ε m a r ) = ⌈ log ( 1 / ε m a r ) − log B r e a l ( μ , η ) ⌉ . (156) T_{\mathrm{real}}^{(\mathrm{mar})}(\eta,\mu,\varepsilon_{\mathrm{mar}})=\left\lceil\frac{\log(1/\varepsilon_{\mathrm{mar}})}{-\log B_{\mathrm{real}}(\mu,\eta)}\right\rceil. \tag*{(156)} T real ( mar ) ( η , μ , ε mar ) = ⌈ − log B real ( μ , η ) log ( 1/ ε mar ) ⌉ . (156)
The direct resource crossover is therefore
N e v a l r e a l ( T r e a l ( m a r ) ) < γ 2 N n o i s e l e s s . (157) N_{\mathrm{eval}}^{\mathrm{real}}\left(T_{\mathrm{real}}^{(\mathrm{mar})}\right)<\gamma^{2}N_{\mathrm{noiseless}}. \tag*{(157)} N eval real ( T real ( mar ) ) < γ 2 N noiseless . (157)
Under Assumption B3 (§ 5.1 ), the simpler sufficient condition becomes
⌈ log ( 1 / ε m a r ) − log B r e a l ( μ , η ) ⌉ < γ 2 . (158) \left\lceil\frac{\log(1/\varepsilon_{\mathrm{mar}})}{-\log B_{\mathrm{real}}(\mu,\eta)}\right\rceil<\gamma^{2}. \tag*{(158)} ⌈ − log B real ( μ , η ) log ( 1/ ε mar ) ⌉ < γ 2 . (158)
Thus, for Real AdaBoost, the weak-edge lower bound produces an explicit a priori positive-margin resource condition once μ \mu μ , η \eta η , and ε m a r \varepsilon_{\mathrm{mar}} ε mar are fixed.
AdaBoostR. § 5.3 gives the trajectory-dependent sufficient round index
T R ( m a r ) ( μ , ε m a r ) = min { T ∈ N : E T − 2 μ A T ≥ 2 log ( 1 ε m a r ) } , (159) T_{\mathrm{R}}^{(\mathrm{mar})}(\mu,\varepsilon_{\mathrm{mar}})=\min\left\{T\in\mathbb{N}:E_T-2\mu A_T\ge2\log\left(\frac{1}{\varepsilon_{\mathrm{mar}}}\right)\right\}, \tag*{(159)} T R ( mar ) ( μ , ε mar ) = min { T ∈ N : E T − 2 μ A T ≥ 2 log ( ε mar 1 ) } , (159)
whenever this set is nonempty. The corresponding direct resource crossover is
N e v a l R ( T R ( m a r ) ) < γ 2 N n o i s e l e s s . (160) N_{\mathrm{eval}}^{\mathrm{R}}\left(T_{\mathrm{R}}^{(\mathrm{mar})}\right)<\gamma^{2}N_{\mathrm{noiseless}}. \tag*{(160)} N eval R ( T R ( mar ) ) < γ 2 N noiseless . (160)
Under Assumption B3 (§ 5.1 ), a sufficient comparison of the resource bounds is T R ( m a r ) < γ 2 T_{\mathrm{R}}^{(\mathrm{mar})}<\gamma^{2} T R ( mar ) < γ 2 . Unlike Real AdaBoost, T R ( m a r ) T_{\mathrm{R}}^{(\mathrm{mar})} T R ( mar ) is not determined by the lower-edge parameter η \eta η alone. The realized quantities
E T = ∑ t = 1 T r t 2 and A T = ∑ t = 1 T α t E_T=\sum_{t=1}^{T}r_t^{2}
\qquad\text{and}\qquad
A_T=\sum_{t=1}^{T}\alpha_t E T = t = 1 ∑ T r t 2 and A T = t = 1 ∑ T α t
must also be taken into account. We do not impose additional assumptions solely to upper-bound A T A_T A T . Instead, the AdaBoostR condition is evaluated from the realized boosting trajectory.
Interpretation of the Comparison
The preceding analysis identifies the quantities that determine the resource comparison between PEC and boosting. The central distinction is that the PEC sampling overhead is determined by the circuit and noise model, whereas the boosting cost also depends on the learning task and on the resulting optimization trajectory. For a fixed task, noise model, and training procedure, this trajectory may still vary because of initialization, finite-shot sampling, and other internal training randomness.
For PEC, we apply the theoretical quasiprobability overhead to the measured resource of the noiseless reference procedure:
C P E C = γ 2 C r e f a l g . (161) C_{\mathrm{PEC}} = \gamma^{2} C_{\mathrm{ref}}^{\mathrm{alg}}. \tag*{(161)} C PEC = γ 2 C ref alg . (161)
Here γ 2 \gamma^{2} γ 2 is fixed by the circuit structure, noise strength, and chosen PEC decomposition. Thus, within the noise model considered in this work, the PEC contribution to the resource comparison can be calculated once the reference resource has been measured.
For boosting, the conditions in § 6.4 identify the quantities that remain to be determined. Applying the Real AdaBoost round bound requires a uniform edge lower bound η \eta η satisfying its contraction condition. The AdaBoostR _{\mathbb{R}} R criterion additionally depends on the realized quantities E T E_T E T and A T A_T A T . For the noisy PQC family and weak-learner training procedure considered here, we do not derive an analytic expression for a positive lower bound η \eta η that holds uniformly across boosting rounds. Establishing such a bound requires controlling the weak learner’s performance under the adaptively reweighted distributions D t D^t D t , which we leave to future work. We therefore retain the uniform-edge condition as an assumption and evaluate the realized edges and weak-learner costs along the training trajectories, rather than predicting them from physical noise strength alone.
The most direct comparison for either boosting method is therefore the resource criterion derived in § 6.3 :
C b o o s t a l g < C P E C = γ 2 C r e f a l g , (162) C_{\mathrm{boost}}^{\mathrm{alg}} < C_{\mathrm{PEC}} = \gamma^{2} C_{\mathrm{ref}}^{\mathrm{alg}}, \tag*{(162)} C boost alg < C PEC = γ 2 C ref alg , (162)
where C b o o s t a l g C_{\mathrm{boost}}^{\mathrm{alg}} C boost alg is the algorithm-required circuit resource used by the boosting trajectory to reach the same empirical margin-loss target as the reference procedure.
This observation motivates the numerical study that follows. For each classification task, circuit depth, and physical noise strength, we first measure the resource required by the noiseless reference learner to reach the prescribed empirical margin-loss target. Equation (161) then determines the corresponding PEC resource. We separately run the noisy boosting procedures and record their realized weak-learner behavior and algorithm-required circuit resources up to the same target. Comparing these quantities determines whether the rapid growth of the PEC sampling overhead is offset by the task-dependent cost of constructing a boosted ensemble.
The numerical experiments therefore do not assume a particular dependence of the weak-learner edge on circuit depth or physical noise. Instead, they measure the resulting boosting resource directly and determine the depth–noise regimes in which the ordering of C P E C C_{\mathrm{PEC}} C PEC and C b o o s t a l g C_{\mathrm{boost}}^{\mathrm{alg}} C boost alg changes.
Numerical Experiments
The theoretical analysis compares two distinct approaches to learning with noisy parameterized quantum circuits (PQCs). We are interested in how the resources required by PEC and boosting change with the physical noise strength and circuit depth, and whether these different dependences give rise to regimes in which one method requires fewer circuit executions than the other.
We investigate this question using a teacher–student binary-classification setting. 1 For each task, a fixed “teacher” PQC generates the binary labels, while the compared learning procedures train separate “student” PQCs from a finite sample of those labeled inputs. This construction gives us a controlled family of classification problems for which the target labeling rule is known and can be varied systematically across circuit depths and random teacher instances. We refer to each such teacher-defined classification problem as a teacher task . In the theory-based comparison, the reference learner and both boosting methods are required to reach the same task-specific empirical margin-loss target,
R ^ S j , μ ( f j m e t h o d ) ≤ ε m a r ( j ) , (163) \widehat{R}_{S_j,\mu}\left(f_j^{\mathrm{method}}\right) \le\varepsilon_{\mathrm{mar}}^{(j)}, \tag*{(163)} R S j , μ ( f j method ) ≤ ε mar ( j ) , (163)
where f j m e t h o d f_j^{\mathrm{method}} f j method denotes the predictor produced by the method being evaluated on teacher task j j j and R ^ S j , μ \widehat{R}_{S_j,\mu} R S j , μ is the empirical margin loss introduced in § 2.4 . The target ε m a r ( j ) \varepsilon_{\mathrm{mar}}^{(j)} ε mar ( j ) is fixed independently for each teacher task j j j before the PEC–boosting resource comparison and is identical for all methods on that task. Consequently, the primary numerical quantity is the number of algorithm-required circuit executions needed to produce a hypothesis satisfying Eq. (163) .
We also perform a separate resource comparison in which the methods are required to reach the same teacher-specific empirical 0–1 classification error on the validation set, derived from the noiseless reference. This target and the corresponding comparison are described in § 7.4 .
We compare two boosting methods, AdaBoostR and Real AdaBoost, against two numerical realizations of PEC. On the complete depth–noise grid we use Projected PEC : the algorithmic cost of the corresponding noiseless reference learner is multiplied by the PEC sampling overhead γ 2 \gamma^{2} γ 2 . This provides the full-grid PEC resource estimate used in the main comparison. In addition, we use Sampled PEC on a smaller preselected subset of depth–noise settings, where the quasiprobability sampling procedure is simulated explicitly. The Sampled-PEC experiments serve as a direct numerical check of the projected PEC resource model and are kept distinct from the full-grid Projected-PEC results.
The empirical margin-loss target determines only the resource-to-target comparison. Nevertheless, satisfying the training margin condition is not by itself the ultimate objective of the learning task. The quantity of interest is the expected 0–1 classification risk, i.e., the probability of misclassification on a fresh input drawn from D \mathcal{D} D :
R D ( f , c ) = Pr x ∼ D [ c ( x ) f ( x ) ≤ 0 ] , (164) R_{\mathcal{D}}(f,c)=\Pr_{x\sim\mathcal{D}}\left[c(x)f(x)\le0\right], \tag*{(164)} R D ( f , c ) = x ∼ D Pr [ c ( x ) f ( x ) ≤ 0 ] , (164)
where c : X → { − 1 , + 1 } c:\mathcal{X}\to\{-1,+1\} c : X → { − 1 , + 1 } is the teacher-defined target labeling function and f : X → R f:\mathcal{X}\to\mathbb{R} f : X → R is the learned prediction score.
We therefore additionally report the empirical training classification error and the classification error on an independent test set. These quantities do not affect the resource comparison; they are used as generalization checks to verify that reaching the common training margin target with fewer resources is not accompanied by a deterioration of predictive performance on unseen data.
Teacher–student classification tasks
We construct binary-classification tasks using four-qubit teacher circuits at depths d ∈ { 1 , … , 5 } d\in\{1,\ldots,5\} d ∈ { 1 , … , 5 } . Each teacher supplies the labels for a dataset, and student circuits are trained to predict these labels from the inputs. Teachers and students share the data-reuploading architecture shown in Figure 1 . For the corresponding width n = 4 n=4 n = 4 architecture, the numbers of one- and two-qubit gate locations are
Figure 1. Circuit architecture shared by teachers and students. Starting from ∣ 0 ⟩ ⊗ 4 \lvert0\rangle^{\otimes4} ∣ 0 ⟩ ⊗ 4 , each of the d d d repeated layers applies a local block V ℓ , q V_{\ell,q} V ℓ , q to every qubit, controlled-Z Z Z gates on ( 0 , 1 ) (0,1) ( 0 , 1 ) , ( 1 , 2 ) (1,2) ( 1 , 2 ) , ( 2 , 3 ) (2,3) ( 2 , 3 ) , ( 3 , 0 ) (3,0) ( 3 , 0 ) , and then R X ( x q λ ℓ , q ) R_{X}(x_{q}\lambda_{\ell,q}) R X ( x q λ ℓ , q ) , where x q x_{q} x q is an input feature and λ ℓ , q \lambda_{\ell,q} λ ℓ , q its scale parameter. A final local block V d + 1 , q V_{d+1,q} V d + 1 , q lies outside the repeated region. Measurements in the Z Z Z basis yield a parity outcome with expectation ⟨ Z 0 Z 1 Z 2 Z 3 ⟩ \langle Z_{0}Z_{1}Z_{2}Z_{3}\rangle ⟨ Z 0 Z 1 Z 2 Z 3 ⟩ .
G 1 ( n , d ) = n ( 4 d + 3 ) , G 2 ( n , d ) = n d . (165) G_{1}(n,d)=n(4d+3),\qquad G_{2}(n,d)=nd. \tag*{(165)} G 1 ( n , d ) = n ( 4 d + 3 ) , G 2 ( n , d ) = n d . (165)
At a fixed depth, let U j ( x ) U_j(x) U j ( x ) denote the circuit of teacher j ∈ { 0 , 1 , 2 } j \in\{0,1,2\} j ∈ { 0 , 1 , 2 } evaluated at input x ∈ [ 0 , 2 π ] 4 x \in[0,2\pi]^4 x ∈ [ 0 , 2 π ] 4 . The exact noiseless parity expectation defines its score,
s j ( x ) = ⟨ 0 ⊗ 4 ∣ U j ( x ) † O U j ( x ) ∣ 0 ⊗ 4 ⟩ , O = Z 0 Z 1 Z 2 Z 3 , (166) s_j(x)=\langle0^{\otimes4}|U_j(x)^\dagger O U_j(x)|0^{\otimes4}\rangle,\qquad O=Z_0Z_1Z_2Z_3, \tag*{(166)} s j ( x ) = ⟨ 0 ⊗ 4 ∣ U j ( x ) † O U j ( x ) ∣ 0 ⊗ 4 ⟩ , O = Z 0 Z 1 Z 2 Z 3 , (166)
and the corresponding label is c j ( x ) = sign s j ( x ) c_j(x)=\operatorname{sign}s_j(x) c j ( x ) = sign s j ( x ) , with sign ( 0 ) = + 1 \operatorname{sign}(0)=+1 sign ( 0 ) = + 1 . These labels are computed from exact teacher expectations and remain fixed throughout the learning experiments.
We generate inputs by drawing their four coordinates independently and uniformly from [ 0 , 2 π ] [0,2\pi] [ 0 , 2 π ] . We keep an input only if ∣ s j ( x ) ∣ ≥ 0.2 |s_j(x)|\ge0.2 ∣ s j ( x ) ∣ ≥ 0.2 , excluding examples for which the teacher score is close to zero. We denote the distribution of the retained inputs by D j X D_j^X D j X , it is uniform over the region that passes this check:
D j X = Unif ( { x ∈ [ 0 , 2 π ] 4 : ∣ s j ( x ) ∣ ≥ 0.2 } ) . (167) D_j^X=\operatorname{Unif}\left(\{x\in[0,2\pi]^4:|s_j(x)|\ge0.2\}\right). \tag*{(167)} D j X = Unif ( { x ∈ [ 0 , 2 π ] 4 : ∣ s j ( x ) ∣ ≥ 0.2 } ) . (167)
We use D j D_j D j for the distribution of the corresponding labeled examples ( x , c j ( x ) ) (x,c_j(x)) ( x , c j ( x )) .
To generate candidate teachers, we draw their rotation angles and input scales independently from a normal distribution with mean zero and standard deviation one. We check that their scores vary sufficiently across inputs and that both classes contain enough examples. To check whether students can learn each task, we use five preliminary student training runs per teacher. A teacher passes this check if the median validation accuracy is at least 90% at depths 1 and 2, 80% at depths 3 and 4, and 75% at depth 5. We choose three teachers at each depth from those meeting these criteria, giving 15 tasks in total. Appendix § 12 describes the screening criteria and the final teacher selection in more detail.
For each teacher, we generate 1536 training examples, 384 validation examples, and 1024 test examples using the sampling rule above. We do not force the two classes to contain equal numbers of examples. The class counts are given in Figure 10 in the Appendix § 12 .
Figure 10. Class proportions in the teacher–student datasets.
Noise model and training procedures
We apply the depolarizing channels defined in § 4.3 after every one- and two-qubit gate of the student architecture. Each channel acts only on the qubits involved in that gate. We denote the corresponding noise strengths by p 1 q p_{1q} p 1 q and p 2 q p_{2q} p 2 q and set p 1 q = p 2 q = p p_{1q}=p_{2q}=p p 1 q = p 2 q = p , with p ∈ { 0.005 , 0.01 , 0.02 } p\in\{0.005,0.01,0.02\} p ∈ { 0.005 , 0.01 , 0.02 } at every depth d = 1 , … , 5 d=1,\ldots,5 d = 1 , … , 5 . The reference circuit uses p = 0 p=0 p = 0 .
For an input x x x and circuit parameters θ \theta θ , we calculate the final density matrix ρ θ , p ( x ) \rho_{\theta,p}(x) ρ θ , p ( x ) and its mean prediction h θ , p ( x ) = Tr [ O ρ θ , p ( x ) ] h_{\theta,p}(x)=\operatorname{Tr}[O\rho_{\theta,p}(x)] h θ , p ( x ) = Tr [ O ρ θ , p ( x )] , with O O O defined in § 7.1 . Thus h θ , 0 ( x ) h_{\theta,0}(x) h θ , 0 ( x ) is the ideal circuit mean without physical gate noise. Reference and boosting predictions use N s h = 25 N_{\mathrm{sh}}=25 N sh = 25 measurement shots per circuit and input:
K ∼ Binomial ( N s h , 1 + h θ , p ( x ) 2 ) , h ^ θ , p ( x ) = 2 K N s h − 1. (168) K\sim\operatorname{Binomial}\left(N_{\mathrm{sh}},\frac{1+h_{\theta,p}(x)}{2}\right),\qquad\widehat{h}_{\theta,p}(x)=\frac{2K}{N_{\mathrm{sh}}}-1. \tag*{(168)} K ∼ Binomial ( N sh , 2 1 + h θ , p ( x ) ) , h θ , p ( x ) = N sh 2 K − 1. (168)
The reference therefore retains measurement fluctuations even though it has no physical gate noise.
We fit the circuits using a smooth hinge loss evaluated at the sampled prediction z z z :
ℓ ( y , z ) = Ψ G ( y z ; σ ) , σ = 0.5 , \ell(y,z)=\Psi_G(yz;\sigma),\qquad\sigma=0.5, ℓ ( y , z ) = Ψ G ( y z ; σ ) , σ = 0.5 ,
Ψ G ( a ; σ ) = ( 1 − a ) Φ N ( 1 − a σ ) + σ ϕ N ( 1 − a σ ) . (169) \Psi_G(a;\sigma)=(1-a)\Phi_N\left(\frac{1-a}{\sigma}\right)+\sigma\phi_N\left(\frac{1-a}{\sigma}\right). \tag*{(169)} Ψ G ( a ; σ ) = ( 1 − a ) Φ N ( σ 1 − a ) + σ ϕ N ( σ 1 − a ) . (169)
Here Φ N \Phi_N Φ N and ϕ N \phi_N ϕ N are the cumulative distribution function and density of a normal distribution with mean zero and standard deviation one. This fitting loss is separate from the criteria used to decide whether a learning target has been reached. We use this loss for fitting because its derivative remains nonzero for misclassified examples, whereas the margin loss used for comparison is constant there.
We initialize the student rotation angles independently from a normal distribution with mean zero and standard deviation 0.1. The input scales are initialized independently with mean one and the same standard deviation. These distributions give small initial rotation angles and input scales close to one, corresponding to little initial rescaling of the inputs. Each epoch processes the 1536 training examples in 24 minibatches of 64. We use Adam [10 ] with learning rate 0.01, clipping the full gradient to Euclidean norm at most one before applying the optimizer to limit the influence of unusually large gradients without restricting the parameter values.
The parameter update combines the loss derivative at the sampled prediction with the derivative of the circuit mean, calculated by JAX automatic differentiation [2 ] . We differentiate the ideal mean for the reference and explicit PEC, and the noisy mean for the boosting weak learners. Measurement fluctuations therefore affect the parameter update through the sampled loss derivative, even though the circuit-mean derivative is calculated without measurement sampling. Appendix § 13 specifies this derivative convention.
To decide when to stop fitting an individual circuit, we track the mean of its minibatch losses in each epoch. An epoch counts as an improvement when this mean is strictly below its best recorded value. The reference stops after 100 consecutive epochs without improvement, while each boosting weak learner uses a patience of 20 epochs. Both allow at most 500 epochs per fit. When fitting ends through either of these limits, we restore the parameters saved at the best epoch.
A separate rule determines when to stop adding weak learners. After each accepted round, we evaluate the normalized ensemble’s margin loss on the full training set at μ = 0.1 \mu= 0.1 μ = 0.1 , using exact noisy circuit means. Boosting stops after 20 accepted rounds without an improvement greater than 10 − 5 10^{-5} 1 0 − 5 over the best recorded value, or after 500 accepted rounds. This rule tracks the progress of the whole ensemble, whereas the epoch-based rule controls the fitting of each individual circuit. Target-based termination, shot-budget limits, and resource costs are specified in § 7.3 .
Comparison protocol and resource costs
We compare the number of circuit shots required to reach two learning targets, considered separately. The first uses the empirical margin loss defined in Eq. (46) , with μ = 0.1 \mu= 0.1 μ = 0.1 , and therefore penalizes both incorrect predictions and correct predictions with small positive margins. The second uses validation classification accuracy. For teacher j j j at depth d d d , we consider a training margin loss no greater than ε m a r ( d , j ) \varepsilon_{\mathrm{mar}}^{(d,j)} ε mar ( d , j ) and a validation accuracy of at least a d , j ∗ a_{d,j}^{*} a d , j ∗ :
R ^ t r a i n , μ ( d , j ) ( f ^ ) ≤ ε m a r ( d , j ) , μ = 0.1 , A ^ v a l ( f ^ ) ≥ a d , j ∗ . (170) \begin{aligned}
\widehat{R}_{\mathrm{train},\mu}^{(d,j)}(\hat{f}) &\leq\varepsilon_{\mathrm{mar}}^{(d,j)}, \qquad\mu= 0.1,\\
\widehat{A}_{\mathrm{val}}(\hat{f}) &\geq a_{d,j}^{*}. \tag*{(170)}
\end{aligned} R train , μ ( d , j ) ( f ^ ) A val ( f ^ ) ≤ ε mar ( d , j ) , μ = 0.1 , ≥ a d , j ∗ . (170)
Here f ^ \hat{f} f ^ is the finite-shot prediction of the reference circuit or the normalized boosting ensemble, and A ^ v a l \widehat{A}_{\mathrm{val}} A val is its validation accuracy. Both thresholds are set for each depth using separate calibration runs and kept fixed across methods, repetitions and noise strengths for the same task. Appendix § 14 gives their construction, numerical values and the details of the accuracy check.
For each learning target, we retain the first confirmed model and the resources accumulated up to its confirmation. Training can continue to seek the other target, so the two comparisons may select different reference parameters or different boosting ensembles from the same run.
We count resources in circuit shots, with one circuit execution and its measurement outcome contributing one shot. The primary cost includes measurements used for fitting and, for boosting, the full-training predictions needed to determine the ensemble coefficients and the next round’s example weights:
C r e f a l g = C r e f f i t , C b o o s t a l g = C b o o s t f i t + C b o o s t e d g e . (171) \begin{aligned}
C_{\mathrm{ref}}^{\mathrm{alg}} &= C_{\mathrm{ref}}^{\mathrm{fit}},\\
C_{\mathrm{boost}}^{\mathrm{alg}} &= C_{\mathrm{boost}}^{\mathrm{fit}} + C_{\mathrm{boost}}^{\mathrm{edge}}. \tag*{(171)}
\end{aligned} C ref alg C boost alg = C ref fit , = C boost fit + C boost edge . (171)
These quantities accumulate through the first confirmation of the target being considered. Boosting includes all fitting and edge acquisitions up to that point, including those for attempted weak learners that are not accepted into the ensemble. At 25 shots per input, one fitting update costs 64 × 25 = 1600 64 \times25 = 1600 64 × 25 = 1600 shots, and one full-training evaluation of a weak learner costs 1536 × 25 = 38 400 1536 \times25 = 38\,400 1536 × 25 = 38 400 shots.
For projected PEC, the resource assigned to a teacher task is the matched reference cost multiplied by the PEC sampling overhead:
C P E C , d , p , j p r o j = γ 2 ( n = 4 , d , p ) C r e f , d , j a l g . (172) C_{\mathrm{PEC},d,p,j}^{\mathrm{proj}} = \gamma^{2}(n = 4,d,p)\,C_{\mathrm{ref},d,j}^{\mathrm{alg}}. \tag*{(172)} C PEC , d , p , j proj = γ 2 ( n = 4 , d , p ) C ref , d , j alg . (172)
Here the first argument of γ 2 \gamma^{2} γ 2 (defined earlier in Eq. (93) ) specifies the four-qubit circuit width. The projection is applied separately to each learning target, using the reference cost for the same teacher and target. Sampled PEC instead counts each sampled corrected-circuit execution directly, without applying an additional γ 2 \gamma^{2} γ 2 multiplier. Its separate experiments and the interpretation of the projection are discussed in § 7.5 .
A run that ends without confirming a target is recorded as unsuccessful for that target, together with its consumed resources. An unconfirmed target in an unfinished run remains unresolved; a target already confirmed on that run retains its selected model and cost.
In the main reference and boosting comparison, each task has three training run repetitions. For each method and learning target, we report a teacher’s cost when at least two repetitions have confirmed successes, taking the median of all confirmed first-hit costs. These medians describe successful runs and are accompanied by the corresponding success counts. Test data do not enter target construction, fitting or model selection; predictive performance is considered separately in § 7.4 .
Resource requirements and predictive performance
Figure 2 compares the shots required by AdaBoostR \mathbb{R} R and Real AdaBoost with the Projected-PEC cost defined in § 7.3 . A teacher enters the comparison when both the reference and the relevant boosting method reach the target in at least two of three repetitions. Results based on one qualifying teacher are marked separately from summaries across two or three teachers.
Figure 2. Resources required to reach the two learning targets. The ratio of Projected-PEC to boosting cost is shown for the margin target above and the classification target below. Each teacher’s ratio uses median costs over successful repetitions. Lines connect medians across teachers meeting the two-out-of-three success requirement for both the reference and boosting. At p = 0.02 p = 0.02 p = 0.02 and d = 4 , 5 d = 4, 5 d = 4 , 5 , neither boosting method confirms the margin target in any of its nine repetitions, so no cost to reach that target is available. Vertical bars give the minimum and maximum; short ticks mark the medians. Crosses indicate one qualifying teacher, for which no range is shown. Ratios above one favour boosting. The vertical axes are logarithmic. Projected PEC is calculated from the reference cost.
Boosting becomes more favourable relative to Projected PEC as the physical noise increases. For the classification target, the advantage also tends to grow with depth, although the depth dependence is not monotonic. Boosting requires fewer shots in 39 of the 56 displayed comparisons across methods, depths, noise strengths and targets.
The ratio plot describes costs on tasks where both methods reach the target sufficiently often. Figure 3 and Figure 4 show the absolute costs together with all successful-repetition counts, including tasks that cannot enter a paired cost comparison. They show that boosting can also reach targets consistently where the reference fails on the two-out-of-three requirement. At d = 4 d = 4 d = 4 , for example, both boosting methods reach the classification target in every repetition at all three noise strengths, whereas the reference meets the requirement for only one of the three teachers. The ratios at this depth therefore describe one teacher, despite consistent boosting success on all three. There are also limits to this improvement: under the stopping rules used here, neither boosting method reaches the margin target at d = 4 d = 4 d = 4 or 5 5 5 when p = 0.02 p = 0.02 p = 0.02 .
Figure 3. Margin-target costs and successful repetitions. Teachers qualify separately for each method after at least two of three repetitions succeed. Each teacher’s cost is the median over successful repetitions. Lines and ticks show medians across teachers, bars span their minimum and maximum. A cross marks a cost based on one qualifying teacher; its value is the median over that teacher’s successful repetitions. Tables show all confirmed hit counts. Green, yellow and red cells indicate at least two, one and zero successes, respectively. The reference is reused across noise settings. Projected PEC uses reference costs. Cost axes are logarithmic.
Figure 4. Classification-target costs and successful repetitions. Costs, ranges and hit counts follow the conventions of Figure 3 . A cost is omitted only if no teacher meets the success requirement.
We next evaluate the models selected at the first confirmed attainment of each target on the test set, which is not used for fitting or model selection. For each method and teacher, we then take the median over successful training repetitions and subtract the reference median from the boosting median. Figure 5 shows these differences for the same teacher subsets as Figure 2 : 36 comparisons include at least two qualifying teachers, and a further 20 include one qualifying teacher.
Figure 5. Test accuracy of the succeeded models relative to the reference. The upper and lower panels correspond to the margin and classification targets. A teacher contributes when both the reference and the corresponding boosting method confirm that target in at least two of three training repetitions, as in Figure 2 . Small symbols show the difference between the boosting and reference median test accuracies within each teacher, in percentage points; large symbols give the median difference across two or three qualifying teachers. When only one teacher qualifies, its result is shown by a cross. The missing margin comparisons at p = 0.02 p = 0.02 p = 0.02 , d = 4 , 5 d = 4, 5 d = 4 , 5 arise because neither boosting method confirms that target in any of its nine repetitions at either depth. Positive values favour boosting; the dashed line marks equal accuracy.
The median test-accuracy difference is positive in all 36 comparisons, with gains ranging from about 0.4 to 10.2 percentage points. In particular, all 25 comparisons in this subset where boosting has a lower training cost than Projected PEC also have a positive median test-accuracy difference. Some individual teacher comparisons favour the reference, even when the median favours boosting. The reference test results describe the predictors associated with the Projected-PEC cost benchmark; the performance of explicitly sampled PEC is examined in § 7.5 .
Projected vs Sampled PEC cost
Sampled PEC estimates the noiseless circuit score by sampling the gatewise corrections and averaging the measured outcomes with their prescribed signs and weights (§ 2.2 ). The additional Pauli corrections are ideal under the noise model used here. We use the sampled PEC score in the fitting loss, retaining the simulator-supplied derivatives described in § 7.2 . Each sampled circuit counts as one raw shot, so the recorded PEC cost already includes its sampling overhead.
We use these experiments to assess how well Projected PEC describes the resources needed for learning, and whether fewer shots per prediction can preserve consistent target attainment at a lower total cost. For comparison with the 25-shot reference, the usual PEC variance bound gives an allocation scale of 25 × γ 2 ( 4 , d , p ) 25 \times\gamma^{2}(4,d,p) 25 × γ 2 ( 4 , d , p ) . This scale is related to the accuracy of an individual prediction; the learning targets may still be reached with fewer shots. Within each PEC run, the same allocation is used for fitting and target checks.
Figure 6 compares the sampled PEC first-hit cost with the projected cost for the same teacher, together with the number of completed runs reaching each target. Reducing the shots per prediction can save resources, but additional optimizer updates can offset that saving.
Figure 6. Sampled PEC resources and target attainment. Each configuration has three teachers and three repetitions per teacher. The allocation column lists the actual PEC shots per prediction and the projected allocation 25 γ 2 25\gamma^2 25 γ 2 . Percentages below these values give 100 N P E C / ( 25 γ 2 ) 100N_{\mathrm{PEC}}/(25\gamma^2) 100 N PEC / ( 25 γ 2 ) . For each teacher, the resource ratio is the median successful PEC cost divided by γ \gamma γ times the median successful reference cost. Both procedures must reach the target in at least two of that teacher’s three repetitions. Thick vertical bars show the median across qualifying teachers, and horizontal segments span their minimum and maximum ratios. These ranges are not confidence intervals. Crosses denote one qualifying teacher. Ratios below one favour sampled PEC; the dashed line marks equal costs. A missing ratio means no teacher qualifies for both procedures.
We next compare sampled PEC with the reference and both boosting methods at d = 3 d = 3 d = 3 and p = 0.01 p = 0.01 p = 0.01 (Figure 7 ). All methods use the same teacher tasks and learning targets. The figure places the two learning targets together and reports each teacher’s successful-repetition count beside the resource costs.
Figure 7. Boosting and sampled PEC at d = 3 d = 3 d = 3 , p = 0.01 p = 0.01 p = 0.01 . Each learning procedure has three completed repetitions for each of three teachers. For each teacher, the cost is the median algorithm-shot count to the first confirmed target hit. A teacher contributes when at least two of its three runs succeed. Thick vertical bars show the median across qualifying teachers, and horizontal segments show their minimum and maximum costs; these ranges are not confidence intervals. The tables report hits for each teacher. Projected PEC multiplies the reference costs by γ 2 \gamma^2 γ 2 and has no independently observed hit count. Sampled PEC shots allocation is specified per experiment and its percentage of the unrounded projection 25 γ 2 25\gamma^2 25 γ 2 , approximately 238.3 shots here.
Both boosting methods reach both targets in all nine runs, while each sampled PEC allocation includes runs that do not reach the target (Figure 7 ). Comparing costs within the same qualifying teachers before taking medians, the PEC-to-boosting cost ratios range from approximately 1.5 to 2.4 for the margin target and from 2.1 to 3.5 for classification, across the three PEC allocations and the two boosting methods. The effect of the PEC allocation differs between targets: the 240-shot setting has the lowest reported PEC median cost for the margin target but the highest for classification. Reducing the shots used for each prediction therefore does not consistently reduce the total training cost.
Boosting trajectories and theoretical bounds
We finally compare the theoretical round counts with the number of rounds needed to reach the margin target in the experiments. Let T n u m T_{\mathrm{num}} T num denote the first round at which this target is confirmed. For Real AdaBoost, we evaluate Eq. (117) using the smallest measured edge up to that round:
η ^ min = min 1 ≤ t ≤ T n u m r ^ t , \hat{\eta}_{\min} = \min_{1 \le t \le T_{\mathrm{num}}} \hat{r}_{t}, η ^ m i n = 1 ≤ t ≤ T num min r ^ t ,
T ^ r e a l ( m a r ) = ⌈ log ( 1 / ε m a r ) − log B r e a l ( μ , η ^ min ) ⌉ , μ = 0.1. (173) \widehat{T}_{\mathrm{real}}^{(\mathrm{mar})} = \left\lceil\frac{\log(1/\varepsilon_{\mathrm{mar}})}{-\log B_{\mathrm{real}}(\mu,\hat{\eta}_{\min})} \right\rceil,\qquad\mu= 0.1. \tag*{(173)} T real ( mar ) = ⌈ − log B real ( μ , η ^ m i n ) log ( 1/ ε mar ) ⌉ , μ = 0.1. (173)
Here B r e a l B_{\mathrm{real}} B real is defined in Eq. (111) . We report a finite count when η ^ min > μ \hat{\eta}_{\min} > \mu η ^ m i n > μ and B r e a l ( μ , η ^ min ) < 1 B_{\mathrm{real}}(\mu,\hat{\eta}_{\min}) < 1 B real ( μ , η ^ m i n ) < 1 . These calculations use the recorded training histories. They do not establish that the same lower edge persists in later rounds, and applying the guarantees to the implemented finite-shot updates requires further analysis.
Real AdaBoost reaches the margin target in 110 of its 135 runs. Figure 8 shows the round counts for every teacher with at least two successful runs out of three, including cases where the theoretical expression gives no finite round count. Among the 57 runs contributing to the theoretical curve, the median observed count is 3 and the median theoretical count is 120. The additional observed results show that learning can also succeed in settings where no teacher meets the condition for inclusion in the theoretical curve. Thus, the sufficient-round formula is substantially more demanding than the observed training. The number of qualifying teachers also decreases in many of the deeper or noisier settings, even where the measured margin target is reached consistently.
Figure 8. Observed and calculated boosting rounds for Real AdaBoost. Solid purple lines show the number of rounds at the attainment of the margin target; dashed purple lines show the theoretical count from Eq. (173) , evaluated using the recorded edges. At each depth and noise strength, the observed curve includes the successful runs of every teacher for which at least two of three runs reach the target, including runs without a finite theoretical count. The theoretical curve requires at least two runs of a teacher to both reach the target and give a finite theoretical count. The two curves can therefore show different runs and teachers. Lines connect medians over the runs included in each curve, and vertical bars show their minimum and maximum, not confidence intervals. A cross (×) marks a result supported by only one teacher on the corresponding curve. The ochre curve shows the PEC sampling overhead γ 2 \gamma^2 γ 2 , not a PEC round count. The vertical axis is logarithmic. Below each panel, the rows give all confirmed margin hits out of nine runs. A missing summary means that no teacher meets the inclusion rule for that curve.
For AdaBoostR, the corresponding condition in Eq. (136) is E T − 2 μ A T ≥ 2 log ( 1 / ε m a r ) E_T - 2\mu A_T \ge2\log(1/\varepsilon_{\mathrm{mar}}) E T − 2 μ A T ≥ 2 log ( 1/ ε mar ) , where E T E_T E T is the sum of squared round edges and A T A_T A T is the sum of the ensemble coefficients. This condition is not satisfied at any recorded round, although 111 of the 135 runs reach the measured margin target. It therefore gives no sufficient round index within these training histories.
To identify where the bounds become loose, we evaluate their intermediate expressions at the first confirmed margin hit of each successful run. This gives 111 AdaBoostR and 110 Real AdaBoost models
from tasks satisfying the two-of-three margin-success rule. For each model, let u i = y i F ^ T ( x i ) / A T u_i = y_i\widehat{F}_T(x_i)/A_T u i = y i F T ( x i ) / A T be the normalized signed margin and let R S , μ R_{S,\mu} R S , μ denote its empirical margin loss. On the same predictions, we evaluate the empirical margin error and exponential expression,
R S , μ m a r = 1 m ∑ i = 1 m 1 { u i ≤ μ } , B T e x p = 1 m ∑ i = 1 m exp [ A T ( μ − u i ) ] . (174) R_{S,\mu}^{\mathrm{mar}} = \frac{1}{m}\sum_{i=1}^{m} \mathbf{1}\{u_i \le\mu\},
\qquad
B_T^{\mathrm{exp}} = \frac{1}{m}\sum_{i=1}^{m} \exp[A_T(\mu-u_i)]. \tag*{(174)} R S , μ mar = m 1 i = 1 ∑ m 1 { u i ≤ μ } , B T exp = m 1 i = 1 ∑ m exp [ A T ( μ − u i )] . (174)
Together with the final edge expression B T M B_T^M B T M from Eq. (109) for Real AdaBoost or Eq. (130) for AdaBoostR, these give the sequence
R S , μ ≤ R S , μ m a r ≤ B T e x p ≤ B T M . (175) R_{S,\mu} \le R_{S,\mu}^{\mathrm{mar}} \le B_T^{\mathrm{exp}} \le B_T^M. \tag*{(175)} R S , μ ≤ R S , μ mar ≤ B T exp ≤ B T M . (175)
All three inequalities hold numerically for all 221 reconstructed models. Table 4 compares their values relative to the margin target.
Table 4. Successive upper bounds at the observed margin target. Each quantity is divided by its task’s margin target before taking the median over 111 AdaBoostR and 110 Real AdaBoost models, respectively. Values below one satisfy the target. The table includes all first-hit models from tasks with at least two successful repetitions out of three.
The increase from margin error to the exponential expression is the largest of the three increases in 206 of the 221 models. This comparison is made separately for each model, before summarizing the results. Most of this increase comes from examples whose margins already exceed μ \mu μ : their empirical margin loss and margin error are zero, but their exponential contribution remains positive. Thus, reaching the empirical margin target does not require the exponential expression to be small. This gap is already present before replacing the recorded edge sequence by its minimum.
The minimum-edge substitution adds further conservatism to the Real AdaBoost round count. When its contraction factor is close to one, the denominator in Eq. (173) becomes small, explaining the sensitivity of the largest calculated counts. The calculated round count depends on how quickly the bound decreases. When B r e a l ( μ , η ^ min ) B_{\mathrm{real}}(\mu,\widehat{\eta}_{\min}) B real ( μ , η m i n ) is close to one, the theoretical decrease per round is small. A bound that is only several times above the target can therefore require tens or hundreds of times as many calculated rounds to fall below it.
A tighter treatment of the empirical margin loss or the distribution of margins could reduce the observed gap. A predictive round guarantee would additionally require control of how these quantities evolve during training and how finite-shot predictions affect the updates.
The ochre curve in Figure 8 relates this comparison to the sufficient resource condition T A ( m a r ) < γ 2 T_A^{(\mathrm{mar})} < \gamma^2 T A ( mar ) < γ 2 in Eq. (155) . In addition to the convergence assumptions, this comparison requires the average weak-learner cost through the sufficient round budget to be no greater than the reference cost, as in Assumption B3 (§ 5.1 ). None of the displayed calculated counts falls below γ 2 \gamma^2 γ 2 , so this calculation does not certify the resource advantages observed in the experiments. Nevertheless, within the simulator-assisted protocol used here, the direct shot comparison in § 7.4 identifies settings where both boosting methods reach the same learning target at lower cost than Projected PEC. These observations support the central idea that combining noisy weak learners can require fewer measurements than compensating for noise through PEC’s sampling overhead.
Discussion
A noisy quantum circuit may retain useful information for classification even when its expectation values differ substantially from their noiseless values. Earlier work on quantum ensembles has demonstrated that this information can be used to improve predictive accuracy [13 , 26 , 6 ] . Whether this also saves circuit executions is less immediate, since training and combining several classifiers introduces a cost of its own. Our analysis and experiments make this trade-off explicit: under the stated assumptions and in the regimes identified numerically, combining noisy classifiers can cost less than using PEC to reach the same learning target.
Boosting provides a concrete realization of this task-aware alternative. It does not require the individual noisy PQCs to approximate the corresponding ideal PQC accurately. What matters is whether they retain predictive information that can be combined across boosting rounds. This changes the relevant resource question from how accurately can the ideal quantum computation be reconstructed? to how much task-relevant information remains accessible after noise?
The resource comparison shows that the theoretical estimates of the required boosting rounds can be pessimistic. In § 7.6 , evaluating the Real AdaBoost bound on the 57 training histories included in the theoretical comparison gives a median of 120 rounds, compared with 3 observed rounds.
A first direction for further work is to obtain tighter bounds on the number of boosting rounds needed to reach the margin target. § 7.6 identifies a source of overestimation: the exponential expression assigns positive contributions to examples that already satisfy the margin requirement and therefore contribute zero to the empirical margin loss. Using the distribution of margins more directly may give a tighter loss bound. To turn this improvement into a bound on the required number of rounds, one would also need to control how the margins change during boosting.
A complementary theoretical question is how useful lower bounds on the weak-learner edge can be derived directly from properties of a noisy PQC family. In the present analysis, the existence of a positive edge is a conditional weak-learning assumption. A substantially stronger result would connect the edge to circuit architecture, physical noise, the data distribution, and the adaptive distributions generated during boosting. Together with a tighter loss bound, such a result could turn the present resource comparison into a predictive criterion rather than one that must be evaluated numerically.
A second question is whether the two strategies should really be treated as competitors. An intermediate regime may be more useful in practice: modest error mitigation could improve the quality of each noisy weak learner, while boosting could remove the need to mitigate it to high precision. Determining the optimal amount of mitigation per weak learner would define a continuous trade-off between mitigation cost and ensemble complexity. A further direction is to combine boosting with adaptive shot allocation to concentrate measurements on the examples or rounds where additional precision is most valuable. The present results concern four-qubit simulations with gate-local depolarizing noise and simulator-assisted gradients. Establishing the same resource comparison on hardware would require accounting for gradient estimation, noise characterization, and measurement errors.
A third direction is to identify other application objectives for which exact observable reconstruction is stronger than necessary. Classification is a particularly clear example, but similar opportunities may arise for ranking, threshold detection, hypothesis testing, control decisions, or other tasks whose output depends only on a coarse property of a quantum observable. The relevant question is then whether task-aware post-processing can exploit information that remains useful even after the underlying quantum state or expectation value has been substantially distorted.
Another interesting question is whether boosting can remain effective in regimes where noisy PQCs become increasingly difficult to optimize as strong classifiers but still retain sufficient trainability to produce weak hypotheses with positive edge. This distinction may be relevant to barren-plateau phenomena: vanishing gradients can make high-accuracy optimization increasingly costly [MBS+18, WFC+21], whereas boosting requires each constituent PQC only to achieve a weak-learning advantage. Establishing whether an intermediate regime of weak trainability persists under barren-plateau-inducing circuit families and noise models requires a dedicated scaling analysis and is left for future work.
Overall, the present work establishes a resource comparison between two ways of using noisy quantum circuits. A stronger next step would combine task-aware robustness to quantum noise with a learning problem for which the relevant quantum features are also difficult to reproduce classically. Finding a regime in which the task is simultaneously classically hard, quantumly learnable, and robust enough for noisy weak learners would connect the resource advantage studied here to a more complete notion of practical quantum learning advantage.
Conclusions
This work reframes the treatment of noise in quantum machine learning as a task-dependent resource problem. For supervised classification, the relevant goal is not necessarily to reconstruct the output of an ideal quantum circuit, but to preserve enough information to make reliable predictions. This distinction motivates boosting noisy PQCs as an alternative strategy: rather than correcting each circuit toward its noiseless counterpart, one can combine imperfect quantum predictors at the level of the learning task.
Our theoretical framework makes this comparison explicit through a common empirical margin loss criterion and a shared generalization bound under the stated assumptions. For PEC, the chosen quasiprobability representation determines the sampling overhead, while the boosting resource depends on the weak-learner edges and the cost of constructing the ensemble. The finite-shot numerical experiments identify a depth–noise trend that generally shifts the resource comparison in favour of boosting relative to Projected PEC. Within identified regimes, AdaBoostR and Real AdaBoost can reach the same task-specific target using substantially fewer algorithmic circuit executions.
The resource advantage is accompanied by favourable observed test performance. For matched classification, all 22/22 method–depth–noise cells supported by at least two qualifying teachers have positive teacher-paired median boosting-minus-reference test accuracy differences, with a median across these cells of +2.15 percentage points. For empirical margin loss, all 14/14 cells meeting this reporting requirement have positive differences, with a median across these cells of +3.84 percentage points. The reference predictors provide the performance associated with Projected PEC. Thus, in the cells where boosting requires fewer resources, its resource advantage is accompanied by higher observed teacher-paired median test accuracy, rather than obtained by accepting worse predictive performance. These findings concern successful-run summaries on the comparable teacher tasks; they do not establish lower expected risk for every boosting model.
The explicitly sampled PEC experiments suggest that Projected PEC provides a useful approximation to the scale of the training resources required in the tested settings. We also examined whether using fewer shots per prediction than suggested by the PEC variance bound could reduce the total cost while preserving reliable target attainment. The smaller shot allocations still sometimes reached the learning targets, but were less stable, and successful training often required more resources than projected. In this comparison, boosting retained both lower observed training costs and more consistent target attainment.
The broader lesson is that quantum error mitigation should not always be treated as a mandatory preprocessing step before learning. When the application requires only a task-specific property of the quantum output, there may be substantial value in designing the learning procedure around the information that survives the noise rather than reconstructing information that the task ultimately does not use. The present resource results remain conditional on the simulator-assisted training protocol and the stated measurement-accounting convention. Establishing when this principle extends to hardware-scale problems, more realistic noise, and learning tasks with an independently established quantum-over-classical advantage is the natural next step.
Acknowledgments
V.D. acknowledges the support of the Dutch Research Council (NWO) through the NWO/NWA project Divide and Quantum (Project No. 1389.20241). V.D. also acknowledges the support of the European Union’s Horizon Europe programme through the ERC CoG BeMAIQuantum (Grant No. 101124342). This work was also supported by the Dutch National Growth Fund (NGF) as part of the QDNL program.
This publication is part of the “Quantum Inspire–the Dutch Quantum Computer in the Cloud” project (Project No. NWA.1292.19.194) of the NWA research program “Research on Routes by Consortia (ORC),” which is funded by the Netherlands Organization for Scientific Research (NWO).
The authors used ChatGPT and Codex (OpenAI; [GPT-5.6 Sol]) to assist with drafting and revising the manuscript, and with developing code for the numerical experiments and data analysis. Access to ChatGPT was provided through OpenAI’s ChatGPT for Academic Researchers programme.
Hypothesis class complexity under Pauli noise
In this appendix, we establish a common upper bound on the Rademacher-complexity contribution for noiseless PQC mean predictors, exact PEC mean predictors and normalized ensembles of noisy PQC mean predictors. Under input-independent Pauli noise and the circuit-parameter assumptions stated below, the noisy mean-prediction class is contained in the convex hull of the corresponding noiseless class. This permits the strategies to be compared using the same reference complexity term; it does not require their actual hypothesis-class complexities to be equal.
Consider a PQC architecture consisting of interleaving layers of single-qubit data-encoding rotations and trainable single-qubit unitaries of the form
U ( ϕ 1 , ϕ 2 , ϕ 3 ) = R z ( ϕ 1 ) R y ( ϕ 2 ) R z ( ϕ 3 ) , (176) U(\phi_1,\phi_2,\phi_3)=R_z(\phi_1)R_y(\phi_2)R_z(\phi_3), \tag*{(176)} U ( ϕ 1 , ϕ 2 , ϕ 3 ) = R z ( ϕ 1 ) R y ( ϕ 2 ) R z ( ϕ 3 ) , (176)
possibly interspersed with fixed entangling gates from the Clifford group (e.g., CNOT or CZ) as in Figure 9 . Such architectures are standard in variational quantum algorithms and are universal on each single-qubit subsystem up to a global phase.
Figure 9. Circuit structure for deriving the Rademacher complexity of a noisy PQC.
For the following argument, the trainable single-qubit blocks have independent parameters and can each realize an arbitrary single-qubit unitary up to global phase. The data-encoding gates are R x ( x q λ ℓ , q ) R_x(x_q\lambda_{\ell,q}) R x ( x q λ ℓ , q ) , and the allowed parameter values permit each replacement λ ℓ , q ↦ − λ ℓ , q \lambda_{\ell,q}\mapsto-\lambda_{\ell,q} λ ℓ , q ↦ − λ ℓ , q independently of the other encoding gates. We also assume a final layer of independently trainable single-qubit unitaries on every qubit, after the last data-encoding and entangling operations. These conditions ensure that the required reparameterizations remain within the same noiseless hypothesis class.
Assume that each noisy circuit location acts on a support S ℓ S_\ell S ℓ of size k ℓ ∈ { 1 , 2 } k_\ell\in\{1,2\} k ℓ ∈ { 1 , 2 } and is followed by a Pauli channel of the form
N ℓ ( ρ ) = ∑ P ∈ P S ℓ p ℓ , P P ρ P , p ℓ , P ≥ 0 , ∑ P ∈ P S ℓ p ℓ , P = 1 , (177) \mathcal{N}_\ell(\rho)=\sum_{P\in\mathcal{P}_{S_\ell}}p_{\ell,P}P\rho P,\qquad p_{\ell,P}\ge0,\qquad\sum_{P\in\mathcal{P}_{S_\ell}}p_{\ell,P}=1, \tag*{(177)} N ℓ ( ρ ) = P ∈ P S ℓ ∑ p ℓ , P P ρP , p ℓ , P ≥ 0 , P ∈ P S ℓ ∑ p ℓ , P = 1 , (177)
where P S ℓ = { I , X , Y , Z } ⊗ k ℓ \mathcal{P}_{S_\ell}=\{I,X,Y,Z\}^{\otimes k_\ell} P S ℓ = { I , X , Y , Z } ⊗ k ℓ denotes the Pauli operators supported on the qubits acted on at location ℓ \ell ℓ . Each Pauli operator is extended by the identity on qubits outside S ℓ S_\ell S ℓ . The channel probabilities are fixed independently of the input x x x . Consequently, expanding the channel sequence gives mixture weights that are the same for every input.
The gate-local depolarizing channels used in the numerical experiments are a special case of Eq. (177) . Indeed, for a support S S S of size k k k ,
D S , p ( ρ ) = ( 1 − p ) ρ + p 4 k ∑ P ∈ P S P ρ P , (178) \mathcal{D}_{S,p}(\rho)=(1-p)\rho+\frac{p}{4^k}\sum_{P\in\mathcal{P}_S}P\rho P, \tag*{(178)} D S , p ( ρ ) = ( 1 − p ) ρ + 4 k p P ∈ P S ∑ P ρP , (178)
which is equivalent to replacing the subsystem on S S S by the maximally mixed state with probability $p.
Fix an initial state ρ 0 \rho_0 ρ 0 and a Hermitian observable O O O with ∥ O ∥ ∞ ≤ 1 \lVert O\rVert_\infty\le1 ∥ O ∥ ∞ ≤ 1 . Let H \mathcal{H} H denote the class of noiseless expectation-value functions obtained by varying the admissible circuit parameters, with the architecture, initial state and observable held fixed. For a fixed parameter vector θ \theta θ , expanding all channels in Eq. (177) gives
h n o i s y ( x ) = ∑ ω π ( ω ) h ω ( x ) , π ( ω ) ≥ 0 , ∑ ω π ( ω ) = 1 , (179) h_{\mathrm{noisy}}(x)=\sum_{\omega}\pi(\omega)h_{\omega}(x),\qquad\pi(\omega)\ge0,\qquad\sum_{\omega}\pi(\omega)=1, \tag*{(179)} h noisy ( x ) = ω ∑ π ( ω ) h ω ( x ) , π ( ω ) ≥ 0 , ω ∑ π ( ω ) = 1 , (179)
where ω \omega ω specifies one Pauli insertion at every noisy circuit location and h ω h_{\omega} h ω is the noiseless predictor obtained for that fixed Pauli-insertion trajectory. For ω = ( P 1 , … , P G ) \omega=(P_1,\ldots,P_G) ω = ( P 1 , … , P G ) , where G G G is the number of noisy gate locations, the weight is π ( ω ) = ∏ g = 1 G p g , P g \pi(\omega)=\prod_{g=1}^{G}p_{g,P_g} π ( ω ) = ∏ g = 1 G p g , P g . In particular, π ( ω ) \pi(\omega) π ( ω ) does not depend on x x x .
It remains to show that these Pauli insertions can be absorbed into the parameters of the same noiseless circuit architecture. Every two-qubit Pauli operator is a tensor product of single-qubit Paulis, and the controlled-Z Z Z entanglers used here are Clifford gates. Hence conjugating a Pauli string through the entangling layer produces another Pauli string.
For the data-reuploading rotations, a single-qubit Pauli satisfies
P R x ( α ) = R x ( s P α ) P , s P ∈ { + 1 , − 1 } , (180) P R_x(\alpha)=R_x(s_P\alpha)P,\qquad s_P\in\{+1,-1\}, \tag*{(180)} P R x ( α ) = R x ( s P α ) P , s P ∈ { + 1 , − 1 } , (180)
up to an irrelevant global phase. Since the data angle is α = x q λ ℓ , q \alpha=x_q\lambda_{\ell,q} α = x q λ ℓ , q and the coefficients λ ℓ , q \lambda_{\ell,q} λ ℓ , q are trainable, the possible sign change in Eq. (180) can be absorbed by replacing λ ℓ , q \lambda_{\ell,q} λ ℓ , q with − λ ℓ , q -\lambda_{\ell,q} − λ ℓ , q .
The remaining local Pauli factors can be absorbed into the trainable single-qubit blocks. An incoming Pauli multiplied into such a block produces another single-qubit unitary, which can be represented by a new choice of that block’s parameters. Pauli insertions between the component rotations of a trainable block can be treated in the same way, since the complete product is still a single-qubit unitary. The final trainable layer absorbs any remaining local Pauli factors without changing the measured observable.
Consequently, for every fixed original parameter vector θ \theta θ and Pauli trajectory ω \omega ω , there is an admissible parameter vector θ ω \theta_\omega θ ω , independent of x x x , such that
h ω ( x ) = h θ ω , 0 ( x ) for every x . (181) h_{\omega}(x)=h_{\theta_\omega,0}(x)\qquad\text{for every }x. \tag*{(181)} h ω ( x ) = h θ ω , 0 ( x ) for every x . (181)
Here, the subscript 0 denotes evaluation without physical noise. Thus h ω ∈ H h_{\omega}\in\mathcal{H} h ω ∈ H for every trajectory appearing in Eq. (179) .
It follows that the hypothesis class induced by noisy PQCs satisfies
H n o i s y ⊆ conv ( H ) , (182) \mathcal{H}_{\mathrm{noisy}}\subseteq\operatorname{conv}(\mathcal{H}), \tag*{(182)} H noisy ⊆ conv ( H ) , (182)
where conv ( H ) \operatorname{conv}(\mathcal{H}) conv ( H ) denotes the convex hull of the noiseless hypothesis class.
Rademacher complexity is monotone under set inclusion and invariant under taking convex hulls. Therefore, for any sample size m m m ,
R m ( H n o i s y ) ≤ R m ( conv ( H ) ) = R m ( H ) (183) \mathfrak{R}_m(\mathcal{H}_{\mathrm{noisy}})\leq\mathfrak{R}_m(\operatorname{conv}(\mathcal{H}))=\mathfrak{R}_m(\mathcal{H}) \tag*{(183)} R m ( H noisy ) ≤ R m ( conv ( H )) = R m ( H ) (183)
Equation (183) establishes an upper bound on the complexity of the noisy mean-prediction class; it does not assert equality with the noiseless complexity.
For boosting, we also account for the classical sign reversal of weak learners. Using the signed class H ± = H ∪ ( − H ) \mathcal{H}_{\pm}=\mathcal{H}\cup(-\mathcal{H}) H ± = H ∪ ( − H ) defined in Eq. (48) , the normalized mean ensemble satisfies
F ~ T ∈ conv ( H n o i s y ∪ ( − H n o i s y ) ) ⊆ conv ( H ± ) . (184) \widetilde{F}_T\in\operatorname{conv}\left(\mathcal{H}_{\mathrm{noisy}}\cup(-\mathcal{H}_{\mathrm{noisy}})\right)\subseteq\operatorname{conv}(\mathcal{H}_{\pm}). \tag*{(184)} F T ∈ conv ( H noisy ∪ ( − H noisy ) ) ⊆ conv ( H ± ) . (184)
The inclusion follows because each signed noisy predictor is a convex combination of signed noiseless predictors.
For PEC with an exact quasiprobability representation, the mean prediction equals the corresponding noiseless expectation, so its mean-prediction class is H \mathcal{H} H . Therefore noiseless predictors, PEC mean predictors and normalized noisy boosting ensembles can all use the common complexity upper bound R m ( H ± ) \mathfrak{R}_m(\mathcal{H}_{\pm}) R m ( H ± ) in the margin-based generalization analysis. This is a shared upper bound, not a claim that the strategies have identical actual complexities or expected risks.
These statements concern mean prediction functions. Finite-shot prediction scores, including the reweighted Sampled-PEC estimates, require the separate measurement-error analysis described in the main text.
This argument relies on input-independent Pauli noise, Clifford entanglers and the parameter freedom specified above. It does not establish the same containment for general noise channels, such as amplitude damping, or for architectures whose parameter constraints prevent the required reparameterizations. Other noise models must be assessed separately. Some coherent errors can already be absorbed when they act directly next to sufficiently expressive trainable blocks, but this does not imply the same result for arbitrary coherent errors throughout the circuit.
Teacher selection and datasets
We first check that each candidate teacher produces scores that vary across inputs and that both labels occur sufficiently often. We then check whether students can learn the resulting task. At each depth, candidates are generated in a fixed order of random seeds. Their rotation angles and input scales are drawn independently from a normal distribution with mean zero and standard deviation one.
For each candidate, we evaluate the exact noiseless teacher score on a fixed set of M = 58,880 M = 58{,}880 M = 58 , 880 inputs in [ 0 , 2 π ] 4 [0, 2\pi]^4 [ 0 , 2 π ] 4 . These inputs are generated by Latin hypercube sampling, which spreads the sampled values across the range of each input coordinate. Writing s i s_i s i for the score at the i i i th input, we require its standard deviation over these inputs to be at least 0.18:
1 M ∑ i = 1 M ( s i − s ˉ ) 2 ≥ 0.18 , s ˉ = 1 M ∑ i = 1 M s i . (185) \sqrt{\frac{1}{M}\sum_{i=1}^{M}(s_i-\bar{s})^2} \ge0.18,\qquad\bar{s}=\frac{1}{M}\sum_{i=1}^{M}s_i. \tag*{(185)} M 1 i = 1 ∑ M ( s i − s ˉ ) 2 ≥ 0.18 , s ˉ = M 1 i = 1 ∑ M s i . (185)
At least 10% of the scores must be below − 0.2 -0.2 − 0.2 , and at least 10% must be greater than or equal to 0.2 0.2 0.2 . No more than 75% may lie in the interval [ − 0.2 , 0.2 ) [-0.2, 0.2) [ − 0.2 , 0.2 ) . We also require the fifth percentile to be below − 0.2 -0.2 − 0.2 and the 95th percentile to be above 0.2 0.2 0.2 , using linear interpolation to calculate the percentiles. There must be at least 1472 distinct inputs with scores below − 0.2 -0.2 − 0.2 and at least 1472 with scores greater than or equal to 0.2 0.2 0.2 . Together, these conditions exclude teachers with nearly constant scores and require enough examples of both labels to remain after removing scores close to zero. They provide an initial check that the teacher defines a useful classification task.
For each teacher passing these checks, we complete five preliminary student training runs. Training stops after 20 consecutive epochs without an improvement in the average training loss (patience criteria), or after maximum training limit of 500 epochs. We retain the parameters from the epoch with the lowest average training loss and evaluate accuracy on the full validation set using sampled circuit outputs. The median accuracy across the five runs must be at least 90% at depths 1 and 2, 80% at depths 3 and 4, and 75% at depth 5. These preliminary students use 1000 measurement shots per circuit and input, with depolarizing noise strengths 0.001 after one-qubit gates and 0.01 after two-qubit gates. These runs are separate from the comparison experiments and are excluded from their reported training costs. At each depth, we keep the three candidates that pass all checks. This choice is made before the methods comparison runs.
For the comparison, we generate new training, validation, and test examples. We draw inputs uniformly from [ 0 , 2 π ] 4 [0, 2\pi]^4 [ 0 , 2 π ] 4 and keep those with ∣ s j ( x ) ∣ ≥ 0.2 \lvert s_j(x)\rvert\ge0.2 ∣ s j ( x )∣ ≥ 0.2 . Each dataset uses independent random draws, separate from those used to check the teachers. We do not force equal class sizes or remove repeated inputs. The larger class contains between 50.91% and 74.87% of the training examples, depending on the teacher. Figure 10 shows the proportions of both classes in the training, validation, and test sets.
Details of circuit training
The loss is evaluated at a sampled prediction, while the derivative of the underlying circuit mean is obtained from the simulator. Let m θ ( x ) = h θ , 0 ( x ) m_\theta(x)=h_{\theta,0}(x) m θ ( x ) = h θ , 0 ( x ) for the reference and sampled PEC, and m θ ( x ) = h θ , p ( x ) m_\theta(x)=h_{\theta,p}(x) m θ ( x ) = h θ , p ( x ) for a noisy boosting weak learner. For a minibatch B \mathcal{B} B , the quantity supplied to gradient-norm clipping and Adam is
g B = ∑ i ∈ B w i , B y i Ψ G ′ ( y i h ^ i ; 0.5 ) ∇ θ m θ ( x i ) . (186) g_{\mathcal{B}}=\sum_{i\in\mathcal{B}} w_{i,\mathcal{B}} y_i \Psi'_{\mathcal{G}}\left(y_i\hat{h}_i;0.5\right)\nabla_\theta m_\theta(x_i). \tag*{(186)} g B = i ∈ B ∑ w i , B y i Ψ G ′ ( y i h ^ i ; 0.5 ) ∇ θ m θ ( x i ) . (186)
Here h ^ i \hat{h}_i h ^ i is the sampled prediction and w i , B w_{i,\mathcal{B}} w i , B is the weight multiplying its minibatch loss. The reference and sampled PEC use w i , B = 1 / ∣ B ∣ w_{i,\mathcal{B}}=1/\lvert\mathcal{B}\rvert w i , B = 1/ ∣ B ∣ . For boosting, we first convert the incoming training weights to 32-bit floating-point numbers, replace values below 2 − 52 2^{-52} 2 − 52 by 2 − 52 2^{-52} 2 − 52 , and divide all weights by their sum over the training set. After selecting a minibatch, we apply the same lower limit again and divide the selected weights by their minibatch sum. These calculations use 32-bit floating-point arithmetic, in which 2 − 52 2^{-52} 2 − 52 is exactly representable. The loss derivative is Ψ G ′ ( a ; σ ) = − Φ N ( ( 1 − a ) / σ ) \Psi^{\prime}_{G}(a;\sigma)=-\Phi_{N}((1-a)/\sigma) Ψ G ′ ( a ; σ ) = − Φ N (( 1 − a ) / σ ) .
Within each weak-learner epoch, each minibatch loss is evaluated before its corresponding parameter update. When the mean of the 24 losses is strictly lower than its best previous value, we save the parameters and optimizer state after the final update of that epoch. This mean therefore contains losses evaluated at successive parameter values during the epoch.
In this derivative rule, the sampled outcomes are held fixed and the score before clipping is assigned the derivative of m θ ( x i ) m_{\theta}(x_i) m θ ( x i ) . This is commonly called a straight-through derivative convention. In general, it gives neither the derivative of the loss evaluated at the exact mean nor an unbiased gradient of the expected finite-shot loss. It therefore specifies a simulator-assisted training procedure, rather than a measured-gradient implementation on quantum hardware.
Construction of the learning targets
For each teacher task, the margin and classification targets are constructed from two separate sets of five preliminary circuit fits. These fits use the same training and validation splits as the main comparison. Both procedures use 1000 forward shots per circuit and input, minibatches of 64 examples, Adam with learning rate 0.01, gradient clipping at Euclidean norm one, and the smooth hinge loss with σ = 0.5 \sigma=0.5 σ = 0.5 . The maximum fitting length is 500 epochs. Their stopping and target-evaluation procedures differ as described below.
The circuits used to define the margin target are fitted under gate-local physical noise p 1 q = 0.001 p_{1q}=0.001 p 1 q = 0.001 and p 2 q = 0.01 p_{2q}=0.01 p 2 q = 0.01 . Fitting stops after 20 consecutive epochs without a strict improvement in the mean minibatch fitting loss, and the parameters saved at the best epoch are restored. We then evaluate each saved circuit on the 1536 training examples using exact noiseless circuit means. The target ε m a r ( a , d ) \varepsilon_{\mathrm{mar}}^{(a,d)} ε mar ( a , d ) is the median of the five resulting unweighted empirical margin losses at μ = 0.1 \mu=0.1 μ = 0.1 . Thus, physical noise enters the fitting of these calibration models, while their contributions to the margin target are evaluated without physical noise or measurement sampling.
The classification target uses five separate reference fits with zero physical gate noise. During these fits, the training-margin target is checked after each optimizer update. Each fit contributes its first confirmed margin-target model. If the margin target is not reached, it instead contributes the terminal parameter state at the 500-epoch limit. We evaluate each selected model on the 384 validation examples using a fresh sampled prediction pass with the shot allocation stated above. All five validation accuracies enter the median, including those from fits that did not reach the margin target. These accuracies are calculated from sampled predictions, whereas the margin-target calibration uses exact circuit means.
For each task, the classification target a d , j ⋆ a^{\star}_{d,j} a d , j ⋆ is the median validation accuracy of the five reference models. A model meets the classification criterion when its validation accuracy is at least this value. Table 5 reports the required validation accuracies as percentages, together with the margin-loss targets. The calibration models are separate from the 25-shot training runs used to measure resource costs, and the targets remain fixed throughout those comparisons.
Table 5. Learning targets for the main comparison. Teacher indices are 0, 1, 2 within each depth. The training-margin target uses μ = 0.1 \mu= 0.1 μ = 0.1 .