cs.AIJun 1, 2026

Measurement-Budget Allocation in Quantum Learning with Finite-Shot Generalization Guarantees

Authors: Ferhat Ozgur Catak

Organizations: Department of Electrical Engineering and Computer Science, University of Stavanger, Norway

Abstract

On near-term quantum hardware, estimating a Born probability requires repeated circuit executions. A quantum learning experiment with a fixed measurement budget BB must therefore decide how many distinct training states nn to use and how many shots SS to spend on each. We study this trade-off for binary quantum classifiers whose measurement operator MM is learned from the training data and evaluated with fresh measurement outcomes. We prove a distribution-free generalization bound for bounded, LL-Lipschitz losses with a sample term of order d/n\sqrt{d/n} and a shot term of order (log⁡n)/S\sqrt{(\log n)/S}; under B=nSB=nS the two terms move in opposite directions. Minimizing a closed-form surrogate of the bound gives the allocation rule n∗=22dB/log⁡(4B/δ)n^* = 2\sqrt{2dB/\log(4B/δ)}, S∗=B/n∗S^* = B/n^*, whose bound value is within 0.1% of the exact numerical minimum on all budgets we evaluate, and a worst-case rate of B−1/4B^{-1/4}. PennyLane simulations with 2- and 4-qubit variational circuits on nine synthetic benchmarks show that the empirical gap stays below the bound in all configurations, although the bound is vacuous at the simulated budgets and becomes non-vacuous only for larger budgets (e.g., B≳5000B \gtrsim 5000 for d=4d=4). For a loss that is concave in the score, the empirical gap is U-shaped under a fixed budget and the measured shot contribution matches its analytical value; for the absolute loss, shot noise is unbiased and no shot-limited regime appears. The rule can be used to plan finite-shot evaluations before an experiment is run.

Figures & tables

Explore similar work

May 14, 2026

AQKA: Active Quantum Kernel Acquisition Under a Shot Budget

Estimating an N×NN \times N quantum kernel from circuit fidelities requires Θ(N2S)Θ(N^2 S) measurement shots, the dominant bottleneck for deployment on near-term hardware. Existing budget-saving methods (Nyström-QKE, ShoFaR, kernel-target alignment) sub-sample which entries to measure but allocate shots uniformly within their chosen subset, ignoring how much each entry drives the downstream classifier. We close this gap with two contributions. First, a complete regime decomposition for shot-budgeted quantum kernel learning: a principled menu of when each allocator wins. Our method, AQKA, dominates the budget-limited regime (B≲16npairsB \lesssim 16 n_{\mathrm{pairs}}) on sparse-sensitivity KRR, with the gap growing from +8+8 to +25+25 pts over uniform as NN scales 225→1000225{\to}1000 and reaching +26+26--3232 pts on an ibm\_pittsburgh (156-qubit Heron) hardware kernel; Nyström-QKE wins at saturating budgets on planted-sparse via low-rank reconstruction; ShoFaR is competitive only at extreme low budgets. Second, a closed-form pair-level acquisition theory: sij⋆∝∣gij∣Kij(1−Kij)s_{ij}^{\star} \propto |g_{ij}|\sqrt{K_{ij}(1-K_{ij})} with explicit gradient gijg_{ij} for KRR (Lemma1, ∣βiαj+βjαi∣Kij(1−Kij)|β_iα_j+β_jα_i|\sqrt{K_{ij}(1-K_{ij})}) and SVM via the envelope theorem (∣ηi∗ηj∗∣Kij(1−Kij)|η_i^*η_j^*|\sqrt{K_{ij}(1-K_{ij})}); a corrected sparsity-aware Cauchy--Schwarz rate ρ≤2m/Nρ\le 2m/N matching empirics (vs.\ the naive m2/N2m^2/N^2); an explicit-constant plug-in regret bound (Theorem2); and a tighter SVM ceiling ρSVM≤msv2/N2ρ^{\mathrm{SVM}} \le m_{\mathrm{sv}}^2/N^2. We close with the first multi-seed live online adaptive shot allocation on quantum hardware: +17.0±4.8+17.0 \pm 4.8 pts at N=20N{=}20 on ibm\_aachen (3.5σ3.5σ, 5 seeds), with the advantage holding at N=30N{=}30 at higher budget on ibm\_berlin (+14.0±8.5+14.0 \pm 8.5 pts, 5 seeds).
Nov 4, 2026

Noise-regularized training of quantum circuit Born machines under a finite shot budget

Quantum circuit Born machines (QCBMs) can learn distributions that are hard to sample from classically, but their value depends on generalizing from finite training data. Here, we study how hardware noise affects this generalization. We show that, for any noise process, the generalization gap of a QCBM trained with the maximum mean discrepancy is bounded by the complexity of the distributions the noisy model can reach. Scrambled local Pauli noise contracts this complexity but biases the model towards the uniform distribution, so residual noise acts as a regularizer whose optimal strength can be intermediate. We propose GENIE, a framework that realizes a chosen noise level with capped error mitigation and selects it during training from held-out data within a fixed execution budget, with provably bounded regret. In simulations on synthetic and census data, GENIE stays close to the best of four noise-control strategies, whereas every fixed noise level falls short in many settings.
Jul 13, 2026

When cheap gradients fail: the measurement cost of attacking quantum classifiers

Adversarial perturbations threaten machine learning classifiers, including variational quantum classifiers. We show that finite quantum measurement statistics (shot noise) act as a built-in defense against gradient-based test-time attacks whose cost scales unfavorably for the attacker. Because every gradient component must be inferred from repeated circuit executions under any unbiased gradient-estimation rule, white-box extraction consumes a dimension-dependent measurement budget that measurement grouping cannot remove in expressive circuits. Under stated assumptions, single-step attacks need at least quadratically many shots in the input dimension dd, growing as d5/2d^{5/2} under norm-concentration scaling, with a sufficient-budget analysis for iterative attacks via stochastic gradient Langevin dynamics. Simulations up to 784 input dimensions validate the law: the realized total budget is the d5/2d^{5/2} geometric floor for plateau-mitigated models and grows as d3.00d^{3.00} for the tested deep circuits, whose gradient norms decay with dimension absent barren-plateau mitigation; folding the measured gradient norm back in recovers the parameter-free d3/2d^{3/2} shot-noise geometry. Against a matched classical baseline whose attack overhead is dimension-independent (the cheap-gradient principle of automatic differentiation), the quantum gradient cost ratio grows empirically as d3.00d^{3.00}, so the attacker's relative cost diverges as the model scales. Experiments on a 156-qubit IBM processor (ibm_boston, 4-qubit circuits, d=12d=12) reproduce the effect: at matched budgets the device attack tracks the ideal within a few percent, with the high-shot gradient faithful to the exact one. The defense operates precisely when the forward map is classically hard to simulate: only then is a white-box attacker denied the simulate-and-backpropagate shortcut and must pay the measurement cost we quantify.