betaFeedback

WorksPhysics and Astronomy

Beyond Error Mitigation: Using Boosting for Noisy Quantum Machine Learning

Abstract

Quantum error mitigation (QEM) can recover information about ideal quantum computations from noisy circuit executions, but may require a large sampling overhead. Fundamental lower bounds show that recovering noiseless observables without problem-specific information can require superpolynomially many samples, with exponential overhead for broad classes of noisy circuits. However, problem-specific information can reduce the number of samples needed to obtain the required answer. We investigate this possibility in supervised quantum machine learning, where labeled examples provide information about the function to be learned. Binary classification provides such a setting, since correct prediction depends on the sign and margin of the classifier output rather than on accurate reconstruction of every noiseless expectation value. We develop a theoretical and empirical framework for comparing boosting of noisy parameterized quantum circuits with probabilistic error cancellation (PEC), requiring both methods to reach the same learning target. For the specified circuit architectures under Pauli noise, we establish a common hypothesis-class complexity bound: matching empirical margin loss gives the same upper bound on expected classification risk. We derive resource criteria and evaluate AdaBoostR and Real AdaBoost in finite-shot teacher-student simulations across circuit depth and physical noise strength. Under the same classification-accuracy target, boosting requires fewer circuit executions as depth and noise increase. Boosting also achieves higher test accuracy than the corresponding reference. For the supervised-learning problems studied, these results demonstrate a task-dependent resource advantage: exploiting information retained in noisy outputs can avoid the cost of ideal-output reconstruction without sacrificing observed classification performance.

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, 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:

  1. 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.

  1. 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.

  1. 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 nn denote a problem size (e.g. number of qubits, input dimension, circuit size), X⊆RN\mathcal{X} \subseteq\mathbb{R}^{N} define the input space and C⊆{c:X→{−1,+1}}\mathcal{C} \subseteq\{c:\mathcal{X}\to\{-1,+1\}\} be a concept class consisting of binary labeling functions, where N(n)N(n) is polynomially bounded in nn. Training examples are generated by drawing inputs x∼Dx \sim\mathcal{D} independently from an unknown but fixed distribution D\mathcal{D} over X\mathcal{X} and assigning labels deterministically according to y=c(x)y=c(x).

Given the above and a labeled sample S={(xi,c(xi))}i=1m(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\} that generalizes well to new samples drawn from the same distribution D\mathcal{D}.

Definition 1. (Efficient Weak Learner) Let C\mathcal{C} be a concept class over X⊆RN\mathcal{X}\subseteq\mathbb{R}^{N}. A (possibly randomized) learning algorithm A\mathcal{A} is called an efficient weak learner for C\mathcal{C} if there exist polynomials pp and qq such that for every distribution D\mathcal{D} over X\mathcal{X}, every target concept c∈Cc\in\mathcal{C}, and every confidence parameter δ∈(0,1)\delta\in(0,1), the following holds:

Given m=p(n,1δ)m = p(n, \frac{1}{\delta}) i.i.d. labeled samples S={(xi,c(xi))}i=1mS = \{(x_i,c(x_i))\}_{i=1}^m with xi∼Dx_i \sim\mathcal{D} on input, the algorithm A\mathcal{A} runs in time polynomial in nn and 1/δ1/\delta and outputs, with probability at least 1−δ1-\delta, a hypothesis hh such that

Pr⁡x∼D[h(x)=c(x)]≥12+ηPAC,ηPAC=1q(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)}

The quantity ηPAC\eta_{\mathrm{PAC}} is the advantage in classification accuracy over random guessing.

Definition 2. (Efficient Strong Learner) Let C\mathcal{C} be a concept class over X⊆RN\mathcal{X} \subseteq\mathbb{R}^N. A (possibly randomized) learning algorithm A\mathcal{A} is called an efficient strong learner for C\mathcal{C} if there exist polynomial pp such that for every accuracy parameter ϵ∈(0,1)\epsilon\in(0,1), every confidence parameter δ∈(0,1)\delta\in(0,1), every distribution D\mathcal{D} over X\mathcal{X}, and every target concept c∈Cc \in\mathcal{C}, the following holds:

Given m=p(n,1ϵ,1δ)m = p(n,\frac{1}{\epsilon},\frac{1}{\delta}) i.i.d. labeled samples S={(xi,c(xi))}i=1mS = \{(x_i,c(x_i))\}_{i=1}^m with xi∼Dx_i \sim\mathcal{D} on input, the algorithm A\mathcal{A} runs in time polynomial in nn, 1/ϵ1/\epsilon, and 1/δ1/\delta and outputs, with probability at least 1−δ1-\delta, a hypothesis hh such that

Pr⁡x∼D[h(x)=c(x)]≥1−ϵ(2)\Pr_{x\sim\mathcal{D}}[h(x)=c(x)] \ge1-\epsilon \tag*{(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 hnoiseless(x)=tr⁡(Oρnoiseless(x))h^{\mathrm{noiseless}}(x) = \operatorname{tr}(\mathcal{O}\rho^{\mathrm{noiseless}}(x)) denote the noiseless PQC expectation for an observable satisfying ∥O∥∞≤1\lVert\mathcal{O} \rVert_\infty\le1. PEC represents the noiseless channel as a linear combination of implementable noisy channels {Oν}\{\mathcal{O}_\nu\}:

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)}

where γ\gamma is the ℓ1\ell_1 norm of the quasiprobability coefficients in the circuit-level decomposition. In a gatewise implementation of PEC, each noiseless gate channel Ug\mathcal{U}_g at location g∈[G]g \in[G] is decomposed as

Ug=∑νgζg,νgOg,ν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}|.

The complete sampled circuit is indexed by ν=(ν1,…,νG)\boldsymbol{\nu} = (\nu_1,\ldots,\nu_G), where GG is the number of noisy gate locations. Its quasiprobability norm is

γ=∏g=1Gγg.(4)\gamma= \prod_{g=1}^{G} \gamma_g. \tag*{(4)}

A single PEC sample is constructed by drawing a complete circuit index ν\nu with probability

pν=∣ζν∣γ,ζν=∏g=1Gζg,νg,p_{\nu} = \frac{|\zeta_{\nu}|}{\gamma}, \qquad\zeta_{\nu} = \prod_{g=1}^{G} \zeta_{g,\nu_g},

executing the corresponding noisy circuit Oν\mathcal{O}_{\nu}, and measuring OO to obtain an outcome Zν∈[−1,1]Z_{\nu} \in[-1,1]. The reweighted outcome is

Z^PEC=γsign⁡(ζν)Zν.(5)\widehat{Z}_{\mathrm{PEC}} = \gamma\operatorname{sign}(\zeta_{\nu}) Z_{\nu}. \tag*{(5)}

The empirical PEC estimator based on NshN_{\mathrm{sh}} shots is

h^PEC(x)=1Nsh∑k=1NshZ^PEC(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)}

Provided that the quasiprobability decomposition is constructed from an accurate description of the physical noisy operations, the estimator is unbiased:

E[h^PEC(x)]=hθnoiseless(x)(7)\mathbb{E}\left[\widehat{h}_{\mathrm{PEC}}(x)\right] = h_{\theta}^{\mathrm{noiseless}}(x) \tag*{(7)}

Since Z∈[−1,1]Z \in[-1,1], the reweighted PEC outcomes satisfy Z^PEC∈[−γ,γ]\widehat{Z}_{\mathrm{PEC}} \in[-\gamma,\gamma]. Thus, PEC enlarges the range of a single measurement outcome by a factor γ\gamma and the variance scale by γ2\gamma^2:

E[(Z^PEC)2]≤γ2,Var⁡(Z^PEC)≤γ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)}

Because the PEC samples are independent and bounded, Hoeffding’s inequality applies. For any ϵ>0\epsilon> 0 and confidence parameter δsh∈(0,1)\delta_{\mathrm{sh}} \in(0,1),

Pr⁡(∣h^PEC(x)−hθnoiseless(x)∣≥ϵ)≤2exp⁡(−2Nshϵ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)}

It therefore suffices to choose

NshPEC≥2γ2ϵ2log⁡2δsh.(10)N_{\mathrm{sh}}^{\mathrm{PEC}} \geq\frac{2\gamma^2}{\epsilon^2}\log\frac{2}{\delta_{\mathrm{sh}}}. \tag*{(10)}

shots to estimate each expectation value within accuracy ϵ\epsilon with confidence 1−δsh1-\delta_{\mathrm{sh}}.

References

  1. [1]Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Physical Review A, 70(5):052328, 2004.DOI
  2. [2]James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Yash Katariya, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milne, and Qiao Zhang. JAX: composable transformations of Python+NumPy programs. https://github.com/jax-ml/jax, 2018.
  3. [3]Marcello Benedetti, Erika Lloyd, Stefan Sack, and Mattia Fiorentini. Parameterized quantum circuits as machine learning models. Quantum Science and Technology, 4(4):043001, 2019.DOI
  4. [4]Peter L. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3:463–482, 2002.DOI
  5. [5]Zhenyu Cai, Ryan Babbush, Simon C. Benjamin, Suguru Endo, William J. Huggins, Ying Li, Jarrod R. McClean, and Thomas E. O’Brien. Quantum error mitigation. Reviews of Modern Physics, 95:045005, 2023.DOI
  6. [6]Jiachen Chen, Yaozu Wu, Zhen Yang, Shibo Xu, Xuan Ye, Daili Li, Ke Wang, Chuanyu Zhang, Feitong Jin, Xuhao Zhu, Yu Gao, Ziqi Tan, Zhengyi Cui, Aosai Zhang, Ning Wang, Yiren Zou, Tingting Li, Fanhao Shen, Jiarun Zhong, Zehang Bao, Zitian Zhu, Zixuan Song, Jinfeng Deng, Hang Dong, Pengfei Zhang, Wei Zhang, Hekang Li, Qiujiang Guo, Zhen Wang, Ying Li, Xiaoting Wang, Chao Song, and H. Wang. Quantum ensemble learning with a programmable superconducting processor. npj Quantum Information, 11:83, 2025.arxiv.org/abs/2503.11047
  7. [7]Suguru Endo, Simon C. Benjamin, and Ying Li. Practical quantum error mitigation for near-future applications. Physical Review X, 8(3):031027, 2018.DOI
  8. [8]Yoav Freund and Robert E. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1):119–139, 1997.DOI
  9. [9]William J. Huggins, Sam McArdle, Thomas E. O’Brien, Joonho Lee, Nicholas C. Rubin, Sergio Boixo, K. Birgitta Whaley, Ryan Babbush, and Jarrod R. McClean. Virtual distillation for quantum error mitigation. Physical Review X, 11:041036, 2021.DOI
  10. [10]Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015.arxiv.org/abs/1412.6980
  11. [11]Michael J. Kearns and Umesh V. Vazirani. An Introduction to Computational Learning Theory. MIT Press, 1994.DOI
  12. [12]Ying Li and Simon C. Benjamin. Efficient variational quantum simulator incorporating active error minimization. Physical Review X, 7(2):021050, 2017.
  13. [13]Qingyu Li, Yuhan Huang, Xiaokai Hou, Ying Li, Xiaoting Wang, and Abolfazl Bayat. Ensemble-learning error mitigation for variational quantum shallow-circuit classifiers. Physical Review Research, 6(1):013027, 2024.
  14. [15]Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. MIT Press, 2 edition, 2018.DOI
  15. [16]Richard Nock and Frank Nielsen. A real generalization of discrete AdaBoost. Artificial Intelligence, 171(1):25–41, 2007.DOI
  16. [17]John Preskill. Quantum computing in the NISQ era and beyond. Quantum, 2:79, 2018.DOI
  17. [18]Yihui Quek, Daniel Stilck França, Sumeet Khatri, Johannes Jakob Meyer, and Jens Eisert. Exponentially tighter bounds on limitations of quantum error mitigation. Nature Physics, 20:1648–1658, 2024.
  18. [19]Robert E. Schapire. The strength of weak learnability. Machine Learning, 5:197–227, 1990.
  19. [20]Robert E. Schapire and Yoram Singer. Improved boosting algorithms using confidence-rated predictions. Machine Learning, 37(3):297–336, 1999.
  20. [21]Maria Schuld, Ryan Sweke, and Johannes Jakob Meyer. Effect of data encoding on the expressive power of variational quantum-machine-learning models. Physical Review A, 103:032430, 2021.DOI
  21. [22]Kristan Temme, Sergey Bravyi, and Jay M. Gambetta. Error mitigation for short-depth quantum circuits. Physical Review Letters, 119(18):180509, 2017.DOI
  22. [23]Ryuji Takagi, Suguru Endo, Shintaro Minagawa, and Mile Gu. Fundamental limits of quantum error mitigation. npj Quantum Information, 8:114, 2022.DOI
  23. [24]Leslie G. Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134–1142, 1984.
  24. [26]Yabo Wang, Xin Wang, Bo Qi, and Daoyi Dong. Supervised-learning guarantee for quantum AdaBoost. Physical Review Applied, 22(5):054001, 2024.DOI

Paper details

vlnc:W_bkhu2ujv
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

ChatGPT, Codex

View statement
Looking for related papers…
Contents