Today's quantum processors can only run shallow circuits before noise erases the computation, so one practical way to get an accurate quantum classifier is to combine many shallow circuits into an ensemble. Supervised Learning Guarantee for Quantum AdaBoost (Supervised Learning Guarantee for Quantum AdaBoost) shows that a boosted ensemble of shallow, noisy circuits can beat even a noiseless single circuit. The ensemble has a cost, though. Every prediction has to run every circuit, and each circuit has to be measured hundreds or thousands of times ("shots") to estimate its output. Shots are the real currency on a quantum device, and an ensemble multiplies them by the number of members. The ensemble is also trained offline, so it cannot follow a data stream that changes over time.
We propose to treat the classifier's margin, meaning how far a score sits from the decision boundary, as a statistical quantity measured with shots, and to spend shots only where the margin is in doubt. The learner is a passive-aggressive (PA) online rule: a closed-form update that leaves the model unchanged when a sample is classified with enough margin and otherwise moves the weights by the smallest amount that fixes it. It learns a linear readout over a fixed bank of shallow circuits. We make two changes. During learning, an update fires only when the measured margin is confidently too small, not whenever a noisy estimate dips below the threshold. During prediction, circuits are measured one at a time in order of their readout weight, with shots allocated by that weight, and measurement stops as soon as the sign of the score is statistically certified. If this works, an M-circuit ensemble costs roughly the shots of a few circuits on easy inputs, keeps its full accuracy on hard ones, and adapts online when the data drifts.
Core Claim
One quantity governs both failure modes of naive quantum PA learning. The first is spurious updates during training. The second is wasted shots at inference. That quantity is the measured margin relative to its shot-noise standard deviation. Let $z_i(x)\in[-1,1]$ be the expectation value of a fixed observable on shallow circuit $i$ applied to input $x$. Let $w$ be the readout weights and $f(x)=\sum_{i=1}^{M} w_i z_i(x)$ the score. If circuit $i$ gets $n_i$ shots, the estimate $\hat f$ has variance
$$\sigma^2(x)=\sum_{i=1}^{M}\frac{w_i^2\,(1-z_i(x)^2)}{n_i}.$$
The standard PA rule of Online Passive-Aggressive Algorithms triggers whenever $y\hat f<1$. A sample with true margin just above 1 therefore triggers with probability near one half. Those triggers produce random-walk updates that erode what the model has learned, which is the stability problem identified as Gap 5 in the research file. Our gated rule updates only when $y\hat f + \kappa\,\hat\sigma < 1$, where $\kappa$ sets a confidence level. It uses the PA-II step $\tau=\hat\ell/(\|\hat z\|^2+\hat\sigma^2+1/2C)$, so measurement variance enters the step the same way the slack penalty already does.
At inference we minimize total shots subject to certifying the sign of $f$. We use the standard optimal allocation for a weighted sum of independent estimates, $n_i\propto|w_i|\sqrt{1-z_i^2}$, together with a sequential stopping test. Together these give
$$N_{\text{total}}(x)\;\approx\;c_\delta\,\frac{\big(\sum_i |w_i|\sqrt{1-z_i(x)^2}\big)^2}{f(x)^2}\;\le\;c_\delta\,\frac{\|w\|_1^2}{f(x)^2},$$
where $c_\delta$ grows like $\log(1/\delta)$ for error probability $\delta$. The bound follows from a Hoeffding-type concentration bound applied to the allocated estimate. Two predictions follow. The cost per input scales with the inverse squared margin rather than with $M$ times a fixed shot count. Inference cost is controlled by the $\ell_1$ norm of the readout, so a sparsifying shrinkage step after each PA update should reduce shots directly. This is the sense in which the update rule itself compresses the ensemble.
Positioning Against Prior Work
Two lines of work motivate the proposal. Quantum AdaBoost (Supervised Learning Guarantee for Quantum AdaBoost) establishes that ensembles of shallow circuits are the right answer to depth limits under noise. It evaluates every member with fixed shots and retrains offline. We keep its circuits as our bank and replace both its offline reweighting and its fixed-cost vote. Evaluating the noise resilience of variational quantum algorithms shows that deviation grows roughly linearly with depth and noise until a chaotic regime sets in. That result constrains us to circuits shallow enough to stay in the linear regime.
Three works supply the method. The PA updates and their relative loss bounds come from Online Passive-Aggressive Algorithms, which assumes features are evaluated exactly. Our contribution is to remove that assumption. The deployment pattern of a frozen feature extractor with a PA-patched linear head comes from Getting Passive Aggressive About False Positives: Patching Deployed Malware Detectors. That system patched hard false positives after an average of 2.51 errors, but it is fully classical and its features cost nothing to evaluate. In our setting every feature evaluation costs shots, so the economics of the head change. Shot variance in shallow quantum classifiers, and the result that shot counts must grow quadratically with effective error rates under depolarizing noise, come from Robust quantum classifier with minimal overhead. That paper fixes shots per evaluation and trains offline. We let shots vary per input and per member.
Two further works offer competing ways to remove inference overhead, and we treat them as competitors rather than ingredients. Quantum Relational Knowledge Distillation distills quantum kernels into a classical student, which drops the quantum device at test time but is static and batch-trained. Averaging Weights Leads to Wider Optima and Better Generalization compresses an ensemble into one set of weights. It relies on Euclidean averaging, which does not carry over to periodic circuit angles. Our method avoids that problem by never averaging circuit parameters: only the classical readout is learned online. Incremental Data-Uploading for Full-Quantum Classification supplies a second family of bank circuits. It interleaves feature blocks with trainable layers to get expressive shallow encoders, reaching 56–60% on MNIST against 33–40% for standard re-uploading.
Research Program
The work has three parts.
The first part builds the circuit bank. One bank is the members produced by running Quantum AdaBoost offline on an initial data window. The other is a set of incremental-data-uploading encoders with frozen, pre-trained parameters and varied block orderings. In both cases the readout is the only thing learned online, which mirrors the frozen-extractor design of the malware-patching work.
The second part analyzes the gated PA rule. We will extend the relative loss bound of the original PA paper to the case of noisy margins. The aim is a bound whose extra term grows with the number of spurious triggers, plus a proof that gating at level $\kappa$ suppresses those triggers at a rate set by a Gaussian tail in $\kappa$. We will also characterize the price of gating. Truly violated samples whose violation is smaller than about $\kappa\hat\sigma$ are missed, so adaptation lags drift by an amount controlled by the training shot budget. That gives an explicit three-way tradeoff between training shots, stability and plasticity.
The third part implements certified sequential inference. Members are ordered by $|w_i|$ and shots are allocated as above. Measurement uses a batched sequential test that stops when the confidence interval on $\hat f$ excludes zero, with a hard shot cap for inputs that sit near the boundary. We also study an $\ell_1$ shrinkage step after each PA update and measure how much it trades accuracy for shots, since the cost formula says $\|w\|_1$ is the lever.
Baselines
The naive reference is standard PA-II on the same circuit bank, with every member measured at a fixed shot count during both training and inference. It shows what happens when measurement noise is ignored. We sweep fixed shot counts so that every method is compared on the same accuracy-versus-total-shots curve rather than at a single operating point.
The strongest existing quantum ensemble is Quantum AdaBoost evaluated at fixed shots per member. The cited paper reports a peak MNIST test accuracy of 97.5% (Supervised Learning Guarantee for Quantum AdaBoost). We will reproduce its task setup and noise models (depolarizing, amplitude damping, phase damping) before comparing. On a static stream, beating it means matching its accuracy to within statistical error at a substantially lower average inference shot count; we target a several-fold reduction. On drifting streams, it is retrained on a sliding window at equal total quantum budget, and beating it means lower cumulative online error.
The strongest online competitor is online stochastic gradient descent on hinge or logistic loss over the same noisy features, with its step-size schedule tuned on the same validation stream and the same number of tuning trials as our $\kappa$ and $C$. Small steps average out shot noise implicitly, so this is the most direct threat to the gating mechanism. Gated PA must beat it on cumulative mistakes or on forgetting at an equal training shot budget.
The strongest competitor for inference cost is static pruning: keep the top-$k$ members by $|w_i|$ and measure them with fixed shots, with $k$ and the shot count chosen so the average shot cost matches ours. Beating it means a higher accuracy at matched average shots. Our method can only win if the per-input savings predicted by the margin formula are real.
The ablations switch off one ingredient at a time: gating, sequential stopping, the weight-proportional allocation (replaced by uniform allocation), and the $\ell_1$ shrinkage. Each isolates one claimed source of gain.
Why not just…?
Why not just use enough shots that noise stops mattering? That is the naive baseline at large shot counts. It does remove spurious updates, but it pays the worst-case cost on every input and every member. That is exactly the overhead that Gap 1 identifies and that Robust quantum classifier with minimal overhead shows grows quadratically with effective error rate. The accuracy-versus-shots curves settle this. If the fixed-shot curve meets ours at low cost, the idea fails.
Why not just run online SGD with a small learning rate? This is a real threat, because averaging over many small steps also suppresses noise. The cost is plasticity: a step size small enough to absorb shot noise also slows recovery after drift. Gating, by contrast, makes no update on confidently correct samples and takes full corrective steps on confidently wrong ones. Our drift experiments measure recovery time after an abrupt shift at equal training shots. If tuned SGD matches gated PA on both stability and recovery, we will report that the PA-specific machinery is unnecessary and keep only the inference contribution.
Why not just distill the ensemble into a classical model? Quantum Relational Knowledge Distillation reports 95.38% on MNIST with zero quantum cost at test time, so on static classical data, distillation may simply win. Our target is the regime it does not cover: inputs that drift, and quantum-native inputs such as ANNNI ground states, where the input is itself a quantum state and cannot be handed to a classical student. On the drifting MNIST stream we include a QRKD student retrained periodically, and we report both where it beats us and where it fails.
Why not just use one deeper circuit? Evaluating the noise resilience of variational quantum algorithms shows that noise pushes deep circuits into a chaotic regime. Incremental Data-Uploading for Full-Quantum Classification finds that deepening by plain re-uploading stays at 33–40% on MNIST. We include a single circuit with the same total gate count as a reference point, but we expect it to lose under realistic noise.
Proposed Experiments
All experiments use exact density-matrix simulation with the three noise channels from the noise-resilience study. A small subset will be re-run with hardware-calibrated noise.
The streams are as follows. On MNIST and Fashion-MNIST, the binary class pair switches at unannounced points. A Shuffled-MNIST stream changes the pixel permutation mid-stream; it was used as a locality test by the incremental-uploading paper. An ANNNI phase-classification stream sweeps the coupling parameter across phase boundaries. Quantum AdaBoost used ANNNI as a benchmark, but no reported result was found on Lacuna for ANNNI accuracy, so we will establish our own reference there.
The metrics are cumulative online mistakes, the spurious-update rate (updates on samples whose noiseless margin is at least 1), forgetting on a held-out set from the earlier distribution, recovery time after each shift, and test accuracy as a function of average and 95th-percentile inference shots.
Four checks decide the outcome. First, the spurious-update rate of ungated PA should approach one half for samples near the margin and fall sharply with gating, and the theory predicts how sharply. Second, shots per test input should track $\|w\|_1^2/f(x)^2$; plotting the measured cost against this predictor tests the core mechanism directly. Third, at matched average shots, our method must beat static top-$k$ pruning in accuracy. If it does not, adaptive stopping adds nothing over pruning. Fourth, on drifting streams, gated PA must recover faster than tuned SGD without forgetting more.
There is a known way this could fail: if most test inputs sit near the boundary, adaptive stopping gains little. We will report the margin distribution for each benchmark so readers can see where the method should and should not help.
References
- Supervised-learning guarantee for quantum AdaBoost
- Online Passive-Aggressive Algorithms
- Evaluating the noise resilience of variational quantum algorithms
- Getting Passive Aggressive About False Positives: Patching Deployed Malware Detectors
- Robust quantum classifier with minimal overhead
- Quantum Relational Knowledge Distillation
- Averaging Weights Leads to Wider Optima and Better Generalization
- Incremental Data-Uploading for Full-Quantum Classification