arXiv CSopen access

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

When cheap gradients fail: the measurement cost of attacking quantum classifiers Bacui Li1,2 , Chandra Thapa2 , Tansu Alpcan1 and Udaya Parampalli3

arXiv:2607.11095v1 [quant-ph] 13 Jul 2026

1

Department of Electrical and Electronic Engineering, University of Melbourne, Parkville, Victoria 3010, Australia 2 CSIRO Data61, Marsfield, NSW 2122, Australia 3 School of Computing and Information Systems, University of Melbourne, Parkville, Victoria 3010, Australia E-mail: [email protected] Abstract. Adversarial perturbations threaten machine learning classifiers, including variational quantum classifiers. We show that finite quantum measurement statistics, that is, 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. We establish, under stated assumptions, that single-step attacks need at least quadratically many shots in the input dimension d, growing as d5/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/2 geometric floor for plateau-mitigated models and grows as d3.00 for the tested deep circuits, whose gradient norms decay with dimension absent barren-plateau mitigation; folding the measured gradient norm back in per sample recovers the parameter-free d3/2 shot-noise geometry (measured d1.46 ). Against a matched classical baseline whose attack overhead is dimension-independent (the cheapgradient principle of automatic differentiation), the quantum gradient cost ratio, a gradient’s cost in forward-inference units, grows polynomially, empirically as d3.00 , so the attacker’s relative cost diverges as the model scales. On a 156-qubit IBM processor (ibm_boston, 4-qubit circuits, d=12), a simulator–hardware comparison over a 100-input cohort reproduces the effect, the device attack tracking the ideal within a few percent at matched budgets, with the high-shot gradient faithful to the exact one (cohort-median cosine 0.98, mean 0.90). The experiments establish the scaling law of measurement-based gradient extraction; its defensive consequence operates precisely when the forward map is classically hard to simulate, since only then is a white-box attacker denied the simulate-and-backpropagate shortcut and must pay the measurement cost we quantify.

Keywords: quantum machine learning, adversarial robustness, parameter-shift rule, shot noise, variational quantum circuits, quantum measurement, finite-shot gradient estimation

Measurement cost of gradient attacks on QML

2

1. Introduction Modern machine learning models achieve high accuracy under benign conditions yet remain vulnerable to adversarial perturbations: small, deliberately crafted input changes that flip a classifier’s prediction while remaining imperceptible to a human observer [1, 2, 3]. Quantum machine learning (QML) [4], whose models are parametrized quantum circuits trained on classical or quantum data, inherits this vulnerability. Existing defenses for QML are largely dynamical : worst-case robustness degrades only polynomially in qubit count [5, 6], a bound that data-geometry refinements sharpen by exploiting the manifold structure of natural data [7] and that has been benchmarked on quantum classifiers at scale [8]; alongside these, empirical studies report that depolarization, hardware crosstalk, and label noise each enhance robustness on nearterm devices [9, 10, 11, 12]. Dowling et al. [13] organize these protections into a hierarchy of dynamical guarantees rooted in unitarity, operator scrambling, and circuit chaoticity. Every analysis in this line, however, prices the attacker’s gradient at zero: its guarantees are stated for exact expectation values. Quantum mechanics forbids the zero-cost gradient. Every observable must be reconstructed from finitely many measurements, and the parameter-shift rule (PSR) [14, 15] makes the cost explicit: each gradient component is a difference of two expectation values, each estimated from shifted-circuit measurement statistics. Such estimation is governed by the quantum Cramér–Rao bound [16, 17], which for single-copy projective measurements coincides with the classical shot-noise variance and floors the variance of any unbiased estimator built from a finite number of shots; under PSR this floor is a percomponent variance σ 2 /s for s shots. A substantial training-time literature amortizes this cost across epochs through adaptive shot-allocation schedules [18, 19, 20, 21, 22, 23]; the security side has none. The asymmetry is the point: a defender pays the shot bill once, spread across training, whereas an attacker pays it afresh for every gradient query at inference time. This sets quantum shot noise apart from the defenses a model designer adds deliberately. Algorithmic gradient obfuscation offers only a false sense of security, since adaptive attacks defeat it at negligible additional cost [24]; certified randomized-smoothing schemes [25, 26] do supply provable robustness radii, but at the price of test-time sampling overhead and radii that themselves shrink with dimension. Quantum shot noise is intrinsic to measurement: it cannot be switched off without buying more shots, and it acts on every gradient component of every query the attacker issues. Our analysis complements the dynamical-guarantee literature [13]: those results bound attack feasibility through circuit properties, whereas we quantify the physical measurement cost that any gradient-based attack incurs regardless of the circuit’s dynamical regime. It also recasts the cheap-gradient theorem [27, 28]. Classically, the gradient cost ratio, the cost of a gradient in units of one forward pass, is bounded by a small constant (≤ 5); on quantum hardware it is exactly this ratio that blows up, because unbiased gradient estimation costs Θ(d) measurements, linear in the

Measurement cost of gradient attacks on QML

3

input data dimension d, regardless of the algorithm used. This Θ(d) component cost cannot be reduced by any measurement grouping. By the expressivity–measurementefficiency trade-off for parametrized quantum circuits [29], the number of simultaneously measurable gradient components collapses to O(1) for deep, generically-entangling ansätze whose dynamical Lie algebra (the Lie algebra generated by the circuit’s gate Hamiltonians) is near-maximal, that is, fills the full su(2q ), which is also the regime in which the forward map becomes classically hard; the per-gradient measurement count is then proportional to the number of components. The exact parameter-shift family is unbiased and so falls under this Θ(d) bound: generalized parameter-shift rules for gates with richer spectra [30, 31] change only the number of shifts per component and remain unbiased, so they do not lower the exponent. Biased or stochastic surrogates instead sit outside the unbiased bound: simultaneous-perturbation (SPSA) estimators and PSR/SPSA hybrids [32, 33] and classical-shadow gradients [34] reduce the percomponent circuit count at the price of estimator variance and, for finite-difference and SPSA-type rules, bias; whether that trade lowers the exponent in the high-curvature expressive regime is governed by the model’s curvature and remains open (Appendix L; see also the empirical survey of [35]). Setting and threat model. We make the attacker precise before stating our results. We study a test-time, white-box evasion attack [36] on a trained QML classifier of classical data. A classifier f (x, θ) maps a classical input x ∈ Rd to class scores through a parametrized quantum circuit. Training is complete and the parameters θ are frozen; at inference the adversary adds a perturbation δ with ∥δ∥2 ≤ ϵ (the perturbation budget ϵ) to a single input so that f (x + δ, θ) is misclassified. A white-box adversary knows the architecture and θ; this is the strongest such attacker, so any cost it must pay, a black-box attacker pays as well. The attack direction is set by the input gradient g ∗ = ∇x L(x, y) of the loss L. On classical hardware this gradient is essentially free to compute, but on a quantum device every component of g ∗ must be reconstructed from finitely many circuit measurements. We write R for the total measurement budget (circuit executions, or shots) the attacker spends to do so. The question this paper answers is how the budget R must grow with d to keep the attack effective. Contributions. We answer this in four parts. (i) Single-step attacks. Under stated, attacker-favoring assumptions (local linearity, i.i.d. shot noise, and a small-noise regime), the single-step shot cost is R =√Θ(ϵd2 ): Θ(d2 ) at a fixed perturbation budget and Θ(d5/2 ) under the ℓ2 scaling ϵ ∝ d that norm concentration motivates; because each assumption favors the attacker, relaxing any of them only raises the cost. (ii) Iterative attacks. Casting the finite-shot Carlini–Wagner attack [2] as Stochastic Gradient Langevin Dynamics (SGLD) with inverse temperature β ∝ s [37, 38] reproduces the empirical shot sweet spot and shows that finite-shot convergence theory grants an iterative attacker no guarantee of escaping the single-step scaling (Appendix F). (iii) Simulation. Simulations up to d=784 on the MNIST and Fashion-MNIST image

Measurement cost of gradient attacks on QML

4

datasets confirm the law’s structure: folding the measured gradient norm back into the cost coefficient recovers the parameter-free d3/2 geometric baseline, and for the tested plateau-prone circuits (gradient norm decaying with dimension, ∥g ∗ ∥ ∝ d−0.73 ) the realized total budget grows approximately cubically (d3.00 and d3.07 on the two datasets), above the d5/2 floor that plateau-mitigated models (dimension-stable gradients, ∥g ∗ ∥ = Θ(1), e.g. barren-plateau-mitigated architectures) would reach. A matched classical CNN baseline has a dimension-independent gradient cost ratio ρclassical ≈ 5 (the Baur–Strassen bound), so the quantum overhead’s growth as d3.00 makes the relative gradient-extraction cost diverge polynomially with d. (iv) Hardware. On IBM’s 156qubit ibm_boston, a matched simulation-versus-experiment comparison at d = 12 over a 100-input cohort reproduces the shot-noise robustness; the high-shot gradient is faithful (cosine 0.90). The simulation reaches the exact-gradient floor (10%) as s → ∞, and the experiment plateaus a few percent above it, a residual device bias the attacker cannot remove, so the low-shot robustness reflects finite measurement and survives device imperfection. Together, these results show that shot noise induces a dimension-scaling resource asymmetry for measurement-based gradient extraction. The scaling itself is generic to noisy, gradient-free (zero-order) estimation: recovering a d-dimensional gradient from such an oracle is long known to cost Θ(d) queries, with matching information-theoretic lower bounds [39, 40, 41]. What is specific to the quantum setting is the irreducibility of that cost under our threat model. The per-query noise is the Born rule under singlecopy measurement, intrinsic to the physics rather than a software perturbation that a white-box attacker could switch off or cheaply average away [24]; and in the classicallyhard regime, quantum hardware denies the simulate-and-backpropagate shortcut even to an attacker who knows θ, leaving an exponent that no unbiased estimator can reduce, because the gradient components cannot be co-measured [29]. The shot-budget bounds concern inference-time gradient extraction only. We further assume the attacker processes one copy of the inference circuit at a time, using the same number of qubits and exploiting no cross-circuit entanglement, so that each shot resolves a single circuit execution rather than a joint multi-copy measurement. Training-time threats such as data poisoning and backdoor injection lie outside this framework and are formalized separately in Section 2.2. Table 1 summarizes the four attack regimes considered, the assumptions and tools used to bound each, and the section in which each result appears. Regime of applicability. One scoping point is essential to reading these results correctly. The defensive consequence of shot noise operates precisely when classical simulation of the model’s forward map is intractable. A white-box attacker who can simulate the circuit can also backpropagate through that simulation to obtain the input gradient at O(1) cost (Remark 1), bypassing the measurement bill entirely. The setting in which QML is expected to be useful, where its forward map offers a genuine quantum advantage, is by definition one in which that map is classically hard to reproduce. There, and only there, the attacker is denied the simulate-and-backpropagate shortcut and

Measurement cost of gradient attacks on QML

5

Table 1: Roadmap of the four attack regimes analyzed. R denotes the total shot budget required to maintain constant attack efficacy at input dimension d. The empirical total-shot exponent (denoted p1 ; fitting convention in Appendix C) exceeds the d5/2 baseline because the tested models’ gradient norms decay with dimension, violating the baseline’s ∥g ∗ ∥ = Θ(1) premise in the defender’s favor (Section 4.1). C&W is studied as a representative example of the broader, largely heuristic, multi-step attack landscape in QML. Regime

Assumption / Result tool

Single-step, fixed ϵ

local linearity, i.i.d. shots norm concentration SGLD + Raginsky [37] matched CNN baseline; ibm_boston

Single-step, ϵ ∝

√

d

Iterative (C&W exemplar) Empirical & hardware

Section

R = Θ(ϵd2 ) = Θ(d2 )

3.1

R = Θ(ϵd2 ) = Θ(d5/2 )

3.1

sufficient poly(d) budget

3.2

p1 ≈ 3.0; overhead Θ(d3.00 ) vs O(1)

4.1, 4.2

must extract every gradient component through measurement, paying the dimensiondependent cost we bound. The small systems we simulate (q ≤ 10 qubits) lie deliberately on the tractable side of this boundary, so that we can compute ground-truth gradients and isolate the scaling exponent; at those sizes a rational white-box attacker would simulate rather than measure. Our experiments should therefore be read as establishing the scaling law of measurement-based gradient extraction, not as a deployed defense at the dimensions probed. Current hardware and the cost of classical simulation place the classically-hard regime beyond what a single study can instantiate end to end, but the scaling law is what characterizes the attacker’s cost once that boundary is crossed. What transfers across the boundary is the exponent: the per-component count is fixed by the input dimension and, by the expressivity–measurement-efficiency trade-off [29], cannot be amortized by any measurement grouping, precisely because the useful regime is the expressive one. The ansätze we simulate already lie in this expressive class (deep, generically-entangling strongly-entangling-layer circuits whose dynamical Lie algebra is near-maximal), so the no-amortization premise is expected to hold for our circuit family at every tested size; only the classical hardness of the forward map awaits larger q, not the expressivity that fixes the exponent. The prefactor carries the per-observable measurement variance σ 2 , which the strong entanglement and output concentration of the expressive regime may shift; bounding it there is the boundary of our extrapolation, which we leave to future work.

Measurement cost of gradient attacks on QML

6

2. Theoretical framework and threat model This section establishes the measurement framework and shows that shot noise induces dimension-dependent gradient uncertainty, the foundation for understanding what happens when a quantum classifier is attacked with finite resources. We introduce notation and the PSR gradient-estimation pipeline including PSR unbiasedness and covariance bookkeeping (Section 2.1), formalize the threat model and the single-step attack assumptions (Section 2.2), derive the chain-rule structure of noisy gradient estimates (Section 2.3), and establish forward- versus backward-pass cost dominance (Section 2.4). 2.1. Notation and gradient estimation via PSR We consider a quantum machine learning classifier f (x, θ) : Rd → RC mapping ddimensional inputs to C class logits via a parametric quantum circuit with trainable parameters θ; Table 2 collects the symbols used throughout this section and the rest of the paper. The quantum layer employs angle encoding gates U (xi ) = eiGxi where G is a generator with two distinct eigenvalues, producing observables whose expectation values ⟨Oj ⟩ define output features. The C class logits are these expectation values directly: the model carries no trainable classical readout layer, and the only classical post-processing is the softmax cross-entropy loss, whose gradient with respect to the logits costs O(1) by automatic differentiation and so leaves the dimension-dependent measurement cost of the quantum Jacobian unchanged. This setup represents the minimal structure required for parameter-shift gradient estimation and is general: it encompasses widely-used QML architectures, including data re-uploading circuits [42], Instantaneous Quantum Polynomial (IQP) models [43], and variational quantum classifiers [44]. Any parametric gate satisfying Lie-algebraic conditions for the parameter-shift rule [15] falls within this framework, making our shot-noise analysis broadly applicable to practical QML implementations. Gradient estimation via the Parameter-Shift Rule (PSR) exploits the spectral structure of encoding gates. For a gate U (xi ) = eiGi xi whose generator Gi has two distinct eigenvalues with spectral gap ∆Gi = λ+ − λ− , the exact gradient is  ∆Gi  ∂⟨O⟩ ⟨O(x(i,+) )⟩ − ⟨O(x(i,−) )⟩ , = ∂xi 2 π x(i,±) = x ± êi , 2∆Gi

(1)

where êi is the unit vector along input coordinate i (so x(i,±) shifts only the i-th feature). For single-qubit Pauli rotations (Gi = σi /2, ∆Gi = 1), this reduces to the familiar shift a = π/2. Each shifted expectation estimated from s0 shots has variance Var[Ôj ] = (1 − ⟨Oj ⟩2 )/s0 ≤ 1/s0 for ±1-valued Pauli observables, where Ôj is the s0 -shot empirical estimate of ⟨Oj ⟩. The gradient estimate inherits this uncertainty: Var[∂ Ôj /∂xi ] = Θ(∆G2i /s0 ). Estimating the full Jacobian J ∈ RC×d requires 2C circuit

Measurement cost of gradient attacks on QML

7

evaluations per input dimension (two PSR shifts for each of C output observables), yielding 2Cd evaluations in total, each using s0 shots. When all C output observables commute (e.g., computational-basis Zi measurements, as in our experiments), the C expectation values share the same bitstrings, reducing the count to 2 evaluations per input dimension (Section 2.4). Convention. Throughout the paper, s denotes the total shots per input dimension, absorbing all per-evaluation overheads: s = 2C s0 in the non-commuting case, or s = 2 s0 when observables commute. The total shot budget is then uniformly R = ds . The per-evaluation count s0 appears only in this derivation; all subsequent scaling laws, propositions, and experiments are stated in terms of s and R = ds. The effective per-shot variance σ 2 used in later sections absorbs the constant relating s to s0 , so that the gradient noise model takes the simple form Var[ĝi ] = σ 2 /s. This measurement uncertainty propagates through backpropagation, inducing gradient noise that is the central object of our analysis. We measure perturbation size via ℓp norms ∥δ∥p and quantify robustness primarily through post–attack accuracy under an ϵ-bounded perturbation (equivalently, attack success rate), together with loss-based surrogates such as the loss surplus ∆L(s) used in our scaling bounds. Our analysis focuses exclusively on the ℓ2 norm for three reasons. (i) Shot-noise geometry: each gradient component estimated via PSR has independent Gaussian noise with variance σ 2 /s, so the total estimation error ∥ĝ − g ∗ ∥ concentrates in ℓ2 , making ℓ2 -norm constraints the natural measure of gradient fidelity. (ii) Optimal attack alignment: under ℓ2 -bounded perturbations, the optimal first-order attack direction is δ ∗ = ϵg ∗ /∥g ∗ ∥2 , aligning exactly with the normalized gradient; for other ℓp norms (p ̸= 2), the dual-norm structure yields optimal perturbations that do not align with the gradient direction (e.g. the ℓ∞ sign-gradient attack [1, 45]), complicating the analysis of how shot noise degrades attack effectiveness. (iii) Practical comparability: in classical adversarial robustness, different ℓp norms produce correlated but distinct vulnerability measures (an attack effective under ℓ∞ constraints may perform differently under ℓ2 bounds), and the ℓ2 norm provides a natural baseline for QML that directly reflects the Euclidean structure of gradient estimation noise. The attacker’s resource cost R denotes the total number of circuit executions (shots × evaluations) required to craft adversarial examples. 2.2. Threat model: gradient-based attacks We focus on physically realistic white-box, test-time (evasion) attacks on QML classifiers [36]: the classifier f (·, θ) has already been trained, its parameters θ are frozen, and the adversary’s only freedom is to craft a small input perturbation δ at inference (query) time so that f (x + δ, θ) is misclassified. Training-time adversaries (any attack that modifies θ or the training distribution) are explicitly out of scope; the resource bounds in this paper concern only the inference-time, per-sample cost of gradient

Measurement cost of gradient attacks on QML Symbol d din s R ϵ g∗ ĝ σ2 Σ Jk L(x, y) Ltrain α κvMF ζ(d) ∆Gi C βeff

8

Meaning Input dimension (number of features) Input dimension to a specific quantum layer (layer local) Shots per input dimension (total across all PSR circuit evaluations for one coordinate; see Section 2.1) Total shot budget R = ds Perturbation budget (ℓ2 -norm bound) True gradient vector ∇x L(x, y) Noisy gradient estimate from finite shots Per-shot variance of observable measurements Covariance matrix of gradient estimation error Jacobian of quantum layer k w.r.t. inputs Attacker’s loss function (rewards misclassification) Defender’s training loss Misalignment angle between ĝ and g ∗ vMF concentration parameter: κvMF ≈ s∥g ∗ ∥2 /σ 2 Landscape factor: measured ratio of the realized clean-attack loss rise to its firstorder prediction (§4.1.1); ζ(d) = 1 for a locally linear landscape Spectral gap of generator Gi (= λ+ − λ− ) Number of output classes SGLD effective inverse temperature

Table 2: Notation. Symbols used throughout the main text.

extraction. Within this evasion setting, a white-box attack further assumes complete knowledge of the model architecture and trained parameters θ, enabling the adversary to compute or estimate gradients ∇x L(x, y) for crafting perturbations (the white-box assumption still requires physical gradient extraction via quantum measurements). This represents a worst-case threat stronger than black-box scenarios.‡ Beyond gradient-based attacks. The measurement cost we bound is a tax on gradient reconstruction; it does not directly bind attacks that avoid estimating ∇x L, namely gradient-free search and transfer (surrogate) attacks, which constitute a separate threat model. Transfer is an imperfect route against quantum classifiers: variational quantum models exhibit enhanced adversarial robustness and learn features distinct from those of classical networks [8], so adversarial examples crafted on a classical surrogate transfer only partially and asymmetrically, though transfer is not eliminated [46]. A full treatment of gradient-free and transfer attacks under the finite-shot model is left to future work. Classification setup. Input samples lie in a bounded space x ∈ [0, 1]d of dimension d with labels y ∈ {1, . . . , C}. The QML classifier f (x, θ) : Rd → RC outputs logits ‡ We assume PSR-based gradient estimation; see Section 1 and Appendix L for discussion of alternative methods.

Measurement cost of gradient attacks on QML

9

(unnormalized scores) for each class; the predicted label is ŷ = arg maxc f (x, θ)c . Training minimizes a differentiable loss Ltrain (x, y; θ), typically cross-entropy after softmax normalization, though alternatives (hinge, focal) exist. Attack objective. An adversary seeks a perturbation δ that causes misclassification while remaining small to evade detection. This trade-off is formalized as a multiobjective optimization: min L(x + δ, y; θ) and ∥δ∥p , δ

s.t. x + δ ∈ [0, 1]d ,

(2)

where L is an attack loss rewarding misclassification (e.g., negative cross-entropy, difference-of-logits variants) and ∥δ∥p measures perturbation size under the ℓp norm. The constraint ensures adversarial examples remain in the input domain. Attack families and the ℓ2 FGSM. Attacks trade off the two objectives differently: fixedbudget methods (FGSM, PGD) fix ∥δ∥p = ϵ and minimize L, while minimum-norm and mixed methods (C&W) minimize ∥δ∥p or a weighted combination L + c∥δ∥2p . We use the ℓ2 -normalized single-step attack δ =ϵ·

∇x L , ∥∇x L∥2

(3)

which is optimal under ℓ2 constraints [45] and preserves the relative magnitudes of all gradient components, the property our shot-noise analysis depends on; it is the ℓ2 analog of the sign-based FGSM [1]. Throughout, “FGSM” denotes this ℓ2 variant. Attack effectiveness metrics. Throughout this paper, we evaluate attacks at a prescribed perturbation budget ϵ and report post–attack accuracy (equivalently, attack success rate) as the primary empirical outcome. On the theory side, we also track lossbased surrogates, in particular the loss surplus ∆L(s) = L(δ) − L(δ ∗ ) that appears in Proposition 3, because it connects directly to gradient misalignment under shot noise. For iterative attacks such as C&W, we report the same metrics after a fixed number of optimization steps under a fixed total shot budget. We do not perform per-sample searches for minimal perturbations, and we do not include hyperparameter tuning overhead (e.g., binary search over the C&W coefficient c) in the resource count, so accounting for this overhead would only strengthen the resource lower bounds. Single-step attacks and working assumptions. A single-step gradient-based attack with perturbation budget ϵ takes the form δ = ϵ F [∇L(x, y)] ,

(4)

Measurement cost of gradient attacks on QML

10

where F (·) : Rn → Rn maps the gradient to a perturbation (e.g. F = sign for the original FGSM, F (g ∗ ) = g ∗ /∥g ∗ ∥2 for Eq. (3)). The single-step shot-scaling analysis in Section 3.1 works under three assumptions, all favorable to the attacker: Assumption 1 (Linear local landscape). The loss landscape is locally linear around x within the perturbation ball, i.e. for any δ with ∥δ∥p ≤ ϵ, L(x+δ, y) = L(x, y)+∇L(x, y)· δ. Assumption 2 (i.i.d. Gaussian gradient components). The estimated loss-gradient components are independent normal, ĝi ∼ N (gi∗ , σ 2 /s), where s is the average perdimension shot count and σ 2 is the effective per-shot variance; the total shot budget is R = ds. Assumption 3 (Small per-component noise is much smaller than the true p noise). The ∗ 2 gradient magnitude, σ /s ≪ ∥g ∥2 , equivalently s ≫ svMF (d) := σ 2 /∥g ∗ ∥2 . A relaxation that drops Assumptions 2–3 and only requires zero-mean gradient error with tr Σ = Θ(d) is given in Section 3.1.2. 2.3. The uncertainty of gradient estimates In classical machine learning, gradient-based adversarial attacks obtain the required input gradients through automatic differentiation and backpropagation. Attackers therefore receive exact, low-variance gradients at a small constant-factor cost relative to inference (the cheap-gradient principle, ≤ 5×; Remark 1) [47, 1]. Quantum models break this convenience through finite-shot measurement uncertainty: every gradient component must be inferred from measurement statistics, so stochastic estimation becomes unavoidable even in a white-box regime, introducing irreducible uncertainty into adversarial gradient extraction. In this section, we formalize the gradient-estimation pipeline for QML attackers and quantify how shot noise disrupts the perturbations they attempt to construct. During a white-box attack, the adversary knows the architecture and trained parameters. Let L(x, y) denote the attacker’s loss for input-label pair (x, y). It differs from the training objective, but we drop any explicit model subscripts for clarity. The attacker seeks g = ∇x L(x, y), the gradient with respect to the input features. When a model contains at least one quantum subroutine whose forward map is classically intractable, the adversary cannot simulate it and must execute that subroutine on quantum hardware to estimate g, since classical simulation becomes infeasible for generic large-scale circuits [48, 49]. This is exactly the regime in which the shot-cost bounds below carry defensive force (Section 1): where the circuit is small enough to simulate, a white-box attacker would instead backpropagate through the simulation at O(1) cost, and the bounds describe the cost of measurement-based extraction rather than an operative barrier. Write the model as a composition of M layers fm so that f (x) = fM ◦fM −1 ◦· · ·◦f0 (x).

Measurement cost of gradient attacks on QML

11

Differentiating the loss with respect to x yields the multivariable chain-rule factorization g = JM (x(M ) )JM −1 (x(M −1) )...J0 (x),

(5)

where Jm is the Jacobian of the mth layer. When a quantum block participates in this composition, measurement randomness injects uncertainty into its Jacobian estimate, and that uncertainty propagates through any surrounding classical layers. For analytic tractability, we discuss a single quantum layer at position k with Jacobian Jk . Still, the same reasoning applies to architectures with multiple quantum segments: each stochastic Jacobian multiplies the deterministic Jacobians of adjacent classical modules. Define the effective Jacobian before the quantum layer as JL = Jk−1 Jk−2 · · · J0 and the effective Jacobian after it as JU = JM JM −1 · · · Jk+1 . Substituting into (5) gives ĝ = JU Jˆk JL .

(6)

Here, we also replace the analytical gradient with an estimate of the gradient and match it to Jˆk , the estimate of the Jacobian quantum layer on the RHS. Note that JU has an implicit dependence on the output of the quantum layer fk ; we treat JU as known in the propositions below because the forward pass of fk is much cheaper than its backward pass (Section 2.4, Proposition 2). Statistical properties of the gradient estimate. PSR is unbiased, E[Jˆk ] = Jk , and each Jacobian entry obtained by the two-shift differencing of Eq. (1) has variance scaling ! ∆2Gj , V[Jˆij ] = Θ sj where sj is the shots allocated to parameter j and the constant depends on the observable statistics and shot-allocation scheme [50]. Commuting outputs (e.g. simultaneous {Zi } readout) share bitstrings, correlating the rows within a Jacobian column. Noncommuting outputs measured in separate settings give independent entries when shot pools do not overlap [51, 52]. The effective gradient Ĝ = JU Jˆ JL then has mean JU µ JL ˆ and column-wise covariance with µ = E[J] Cov(Ĝ·i , Ĝ·j ) =

d X

JU Σv JU⊤ [JL ]vi [JL ]vj ,

Σv = Cov(Jˆ·v ).

(7)

v=1

The per-case covariance bookkeeping and the vec-level Kronecker form are collected in Appendix G. Consistent with PSR error analyses, the per-component gradientestimation error scales as s−1/2 (equivalently R−1/2 for total budget R = ds) [53, 54]. 2.4. Forward- versus backward-pass shot cost This subsection establishes that, for a hybrid architecture with a quantum layer fk : Rdin → Rdout surrounded by classical layers, backward-pass Jacobian estimation

Measurement cost of gradient attacks on QML

12

dominates the shot budget in high dimensions. Accounting for both forward-pass (output) and backward-pass (Jacobian) measurement noise, the gradient estimate of Eq. (6) becomes ĝ = JU (ŷk ) Jˆk JL , where ŷk is the noisy quantum output. Proposition 1 characterizes the forward contribution; Proposition 2 and Corollary 1 establish the dominance of the backward cost. Assumption 4 (Smoothness of classical post-processing). The classical layers following the quantum block are twice continuously differentiable with bounded Hessian in a neighborhood of yk , so that the Jacobian satisfies JU (ŷk ) − JU (yk ) = HU (ŷk − yk ) + O(∥ŷk − yk ∥2 ) for a bounded matrix HU . Proposition 1 (Forward-pass variance scaling). Under Assumption 4, the variance contribution from forward-pass noise satisfies V[JU (ŷk ) − JU (yk )] = Θ(1/m), where m is the number of shots per observable and the constant depends on ∥HU ∥ and the covariance structure given in equation (7). Proposition 2 (Backward-pass dominance in high dimensions). For fixed output dimension dout and large input dimension din , the backward-pass shot cost scales as Θ(din ) relative to the forward-pass cost. Corollary 1 (Backward-focused scaling analysis). In the regime din ≫ 1 with dout = O(1) (typical for classification with few classes), dimension-dependent shot scaling is governed by backward-pass Jacobian estimation. Forward-pass uncertainty is retained for completeness but contributes only a lower-order term that does not affect the dimensiondependent scaling laws derived in Section 3.1. Proposition 1, Proposition 2, and Corollary 1 are proved in Appendix G. Compatible observables. When quantum layer outputs consist of mutually commuting observables (e.g. {Zi } measured simultaneously), both forward and backward circuit evaluations reduce by a factor of dout (= C for the output layer), since all observables can be measured in a single circuit run. This optimization preserves the Θ(din ) scaling ratio in Proposition 2, as the reduction applies equally to numerator and denominator. In the commuting case the per-evaluation count drops from 2C to 2, so the per-dimension budget becomes s = 2 s0 rather than 2C s0 ; the uniform formula R = ds applies in either case (Section 2.1). Remark 1 (Classical gradient cost and comparison). For a classical neural network with input dimension d and P parameters, a single backpropagation pass computes the exact input gradient ∇x L in Θ(P ) floating-point operations. The forward pass also requires Θ(P ) operations, giving a gradient cost ratio ρclassical =

Cbwd = O(1), Cfwd

independent of d. We call ρ the gradient cost ratio: the cost of obtaining the gradient measured in units of one forward inference, that is, how many forward inferences a

Measurement cost of gradient attacks on QML

13

single gradient costs. This is a theorem, not merely an empirical observation: the Baur–Strassen result [27] and its modern treatment [28] (which terms the quantity the cost ratio) prove that the cost of computing the full gradient vector via reverse-mode automatic differentiation is at most a small constant multiple (≤ 5×) of the forward pass for any differentiable program: the cheap-gradient principle, which bounds ρ ≤ 5 for any classical program, independent of d. 2 In contrast, for a quantum classifier the forward pass requires Rfwd = Θ(dout /σfwd ) shots, independent of input dimension d (Proposition 2), while a successful√singlestep gradient attack requires Rbwd = Θ(d2.5 ) shots (Proposition 3, with ϵ ∝ d and ∥g ∗ ∥ = Θ(1)). The quantum gradient cost ratio is therefore ρquantum (d) =

Rbwd = Θ(d2.5 ). Rfwd

The structural asymmetry is that classical forward and backward passes both scale with P (and hence with d), keeping their ratio constant, whereas the quantum forward pass cost is d-independent (it depends only on the number of output classes C and the desired precision) while the backward pass scales polynomially with d. This decoupling makes the gradient cost ratio diverge: the cheap-gradient principle fails on quantum hardware, ρquantum /ρclassical = Θ(d2.5 ) at the geometric floor, realized as Θ(d3.00 ) by the tested models (Section 4.1.3). 3. Shot-budget scaling laws Scope and relaxation of the working assumptions. Assumption 1 is valid when ϵ is small √relative to the local radius of curvature 1/∥∇2 L∥. Under the natural scaling ϵ ∝ d motivated by norm concentration (Appendix H), when d increases, the ϵball with increasing radius sweeps an increasingly larger portion of input space in absolute ℓ2 terms, and empirical evidence from classical adversarial ML suggests that loss-landscape curvature typically increases in high dimensions due to the proliferation of local modes and saddle points [55, 56]; second-order terms O(ϵ2 ∥∇2 L∥) therefore become non-negligible. The net empirical cost still exceeds this baseline, but direct measurement (§4.1.1) locates the driver elsewhere: the dimensional decay of the gradient norm ∥g ∗ ∥ ∝ d−0.73 , which the cost coefficient absorbs, accounts for the empirical excess over the baseline on both datasets (Section 4.1). Local curvature itself, measured by a transverse line-scan of the ϵ-step, mildly favors the attacker: the curved landscape forgives noise-induced misalignment, so the shot-noise penalty is smaller than the linear prediction (ζ < 1, §4.1.1). The scaling laws below therefore remain shot-noise baselines whose empirical excess is gradient-norm-driven rather than curvature-driven. A relaxation that drops Assumptions 2–3 and replaces them by a covariance condition tr Σ = Θ(d) is developed in Section 3.1.2 and yields the same qualitative scaling.

Measurement cost of gradient attacks on QML

14

3.1. Single-step attacks We now derive the explicit scaling laws from the analytical framework of Section 2 (PSR unbiasedness and covariance, backward-pass cost dominance, and the single-step attack of Eq. (4) under Assumptions 1–3). Single-step methods such as FGSM draw a single noisy gradient and spend their entire perturbation budget along that direction, making them sensitive to gradient estimation errors: any misalignment induced by shot noise directly degrades attack efficacy. We derive explicit shot-scaling laws for both i.i.d. and correlated gradient-noise models. The key results are Propositions 3 and 4, which show that maintaining constant attack efficacy requires s = Θ(ϵd) shots per input dimension, corresponding to a total gradient-evaluation budget R = ds = Θ(ϵd2 ), i.e. Θ(d2 ) for √ fixed ϵ and Θ(d5/2 ) under ϵ ∝ d, and Corollary 2, which recovers the same scaling under weaker assumptions. 3.1.1. Result: shot-budget guarantees for single-step attacks New shot-scaling law. Proposition 3 (FGSM shot budget versus optimization gap). Under Assumptions 1, 2, and 3, the l2 FGSM attack requires shots per dimension   ϵd s=O ∆ ∥g ∗ ∥ and therefore total shots ϵd2 ds=O ∆ ∥g ∗ ∥ 



to achieve an optimization error L(δ) − L(δ ∗ ) = ∆. When ∥g ∗ ∥ is locally constant, this simplifies to s = Θ(ϵd/∆) and d s = Θ(ϵd2 /∆). Proof. We analyze the ℓ2 -constrained FGSM attack, where the perturbation norm directly reflects the Euclidean structure of shot-noise estimation error (Sec. 2.1 and Sec. 2.3). Under ℓ2 constraints, the optimal first-order perturbation aligns exactly with the gradient direction, enabling a clean analysis of how shot noise degrades attack effectiveness through angular misalignment. Consider the perturbation δ = −ϵĝ/∥ĝ∥ with measurement-driven gradient estimate ĝ ∼ N (∇L(x, y), Iσ 2 /s). Combining this with Assumption 1 yields L(x + δ, y) = L(x, y) − ϵ∥∇L(x, y)∥ cos(α) ,

(8)

where α is the angle between ĝ and the true gradient ∇L(x, y). Under Assumptions 1 and 2, the normalized estimator ĝn = ĝ/∥ĝ∥ follows a von Mises–Fisher law with concentration parameter κvMF ≈ s∥g ∗ ∥2 /σ 2 . Using the large-κvMF approximation from Assumption 3, d−1 (d − 1)σ 2 ≈1− . (9) E[cos α] ≈ 1 − 2κvMF 2s ∥g ∗ ∥2

Measurement cost of gradient attacks on QML

15

Substituting into (8) shows that, when the per-shot variance σ 2 is dimensionindependent (the phase-dense encoding’s generators have spectral gap ∆Gj = 1, making σ 2 flat by construction), the single-step loss surplus satisfies (d − 1)σ 2 , (10) 2s ∥g ∗ ∥ and hence, using the local linearity benchmark, the optimization gap scales as   ϵd ∗ . (11) L(δ) − L(δ ) = O s ∥g ∗ ∥ Inverting the last expression to solve for the shots per dimension that achieve a target gap ∆ yields the stated bounds. L(x + δ, y) − L(x + ϵg ∗ /∥g ∗ ∥, y) ≈ ϵ

Proposition 3 √ yields a shot-noise scaling baseline s = Θ(ϵd), which evaluates to Θ(d ) under ϵ ∝ d and ∥g ∗ ∥ = Θ(1). The three assumptions underlying this result, local linearity (Assumption 1), i.i.d. Gaussian noise (Assumption 2), and small noise (Assumption 3), are each optimistic for the attacker: local linearity means the gradient is maximally informative about the loss landscape, i.i.d. noise is the most favorable covariance structure, and the small-noise regime ensures gradient estimates are already high-quality. The ∥g ∗ ∥ = Θ(1) premise is a design property rather than an idealization: architectures built to avoid barren plateaus (quantum convolutional networks, whose gradients provably vanish at most polynomially in qubit count [57]; shallow circuits with local cost functions [58]; see [59] for a review) keep gradient magnitudes dimensionstable up to polylogarithmic factors in d, and for such models the Θ(d3/2 ) per-dimension baseline is the realized cost. Generic deep circuits without plateau mitigation enjoy an additional layer of protection: their gradient norms decay with dimension (measured directly in Section 4.1: ∥g ∗ ∥ ∝ d−0.73 , exponential in qubit count at d ≈ 2q , the plateau signature), which the coefficient’s 1/∥g ∗ ∥ factor converts into the higher realized scaling s ∝ d2.00 on MNIST (d2.07 on Fashion-MNIST), as detailed below. 3/2

Empirical scaling beyond the baseline. Proposition 3 predicts s √ = Θ(ϵd) = Θ(d3/2 ) when its coefficient is evaluated under ∥g ∗ ∥ = Θ(1) (with ϵ ∝ d). The sharpest experimental test of the law targets the coefficient with the gradient norm folded out: the measured combination dL·∥g ∗ ∥ follows d1.46 on MNIST and d1.42 on Fashion-MNIST against the parameter-free d3/2 prediction (§4.1.1), confirming the geometric factor of the bound. The bare shot requirement is then this geometric factor compounded by the model’s gradient scale: direct measurement shows ∥g ∗ ∥ ∝ d−0.73 on MNIST (d−0.65 on Fashion-MNIST) for our unmitigated deep circuits, and the resulting in-regime fits, s ∝ d2.00 and s ∝ d2.07 (Section 4.1), require no parameterization beyond the bound’s own 1/∥g ∗ ∥ factor; landscape curvature contributes a small, oppositely-signed effect (a mild attacker advantage). Remark 2 (ϵ-scaling). If ϵ is dimension-independent, maintaining constant FGSM efficacy requires Θ(d2 ) total shots. If ϵ scales with dimension according to norm concentration (Appendix H), the requirement increases to Θ(d2.5 ) or higher.

Measurement cost of gradient attacks on QML

16

Shot-noise scaling baseline. Proposition 3 derives R = Θ(ϵd2 ) as the √ baseline scaling 5/2 under Assumptions 1–3, which evaluates to Θ(d ) under ϵ ∝ d, represents an idealized lower-envelope scaling under a combination of assumptions that favor the attacker, and should therefore be interpreted as a baseline rather than a typical regime. However, each assumption represents conditions that are favorable to the attacker: (i) local linearity means the gradient is maximally informative about the loss landscape within the ϵ-ball; (ii) i.i.d. noise is the most favorable covariance structure for gradient alignment; (iii) the small-noise regime ensures gradient estimates are already high-quality. For generic QML loss landscapes, where curvature grows with dimension, noise correlations are non-trivial, and gradient signal-to-noise varies across components, departing from these assumptions will typically increase the attacker’s required shot budget. Corollary 2 illustrates one such departure: under correlated noise with tr Σ = Θ(d), Rmin = Θ(ϵ2 d2 ) = Θ(d3 ) √ the minimum sufficient total budget grows to 0.50 (MNIST) and d0.57 under ϵ ∝ d. The empirical excess over the baseline, d (Fashion-MNIST) per dimension (§3.1.1), is dominated by the measured gradient-norm decay (§4.1.1): of the three idealizations, ∥g ∗ ∥ = Θ(1) is the load-bearing one, while local curvature, measured directly, mildly favors the attacker rather than the defender. Unlike the other two, ∥g ∗ ∥ = Θ(1) is attainable by construction: plateau-mitigated architectures realize it up to logarithmic factors [57, 59], whereas generic deep circuits violate it in the √ defender’s favor. We therefore interpret R = Θ(ϵd2 ) (which gives d5/2 under ϵ ∝ d) as the shot-noise scaling baseline: it quantifies what a singlestep PSR-based attack costs against the most attacker-favorable model class, with departures driving costs higher; the plateau-prone circuits tested in Section 4.1 realize total exponents of 3.00 (MNIST) and 3.07 (Fashion-MNIST). The result strengthens the robustness claim: even under the most favorable conditions for the attacker, the cost is already R = Θ(ϵd2 ) = Θ(d5/2 ). In practice the measured gradient-norm decay drives it higher still (§4.1.1), while local curvature returns a small offsetting advantage to the attacker. Whether alternative attack strategies can exploit that curvature further while respecting the s = Θ(ϵd) = Θ(d3/2 ) shot-noise baseline remains an open question for future investigation. Estimator-independence of the exponent. The derivation uses only that each component is recovered by an unbiased estimator with per-component variance Θ(σ 2 /s), not the two-shift structure of the parameter-shift rule; the Θ(d2 ) exponent is therefore a property of unbiased gradient extraction, not of a particular estimator. Two routes could lower it, and both are closed in the expressive regime. Co-measuring several components at once is bounded by the expressivity–measurement-efficiency trade-off [29], under which a near-maximal dynamical Lie algebra forces the number of simultaneously measurable components to O(1). Estimating a directional derivative along a generic dense direction requires a quadrature exact on the circuit’s full Fourier support, which for an expressive circuit is far larger than d, so it offers no saving over the d axis-aligned probes. Parameter-shift is the canonical estimator that attains the bound [30]; biased

Measurement cost of gradient attacks on QML

17

surrogates are treated separately in Appendix L. The preceding i.i.d. analysis and the success-probability analysis that follows (Section 3.1.3) provide two complementary paths to the same quadratic scaling conclusion: the first relaxes distributional assumptions, the second strengthens the guarantee from expectation to tail probability. 3.1.2. Result: correlated-noise guarantee Corollary 2 (Minimum sufficient shot budget under correlated noise). Fix a target losssurplus tolerance ∆ (written ∆ throughout, and not to be confused with the compound symbols ∆L, ∆Gi ) on the expected single-step loss surplus. Consider an attacker who allocates a per-dimension budget of s shots and seeks to drive the expected single-step loss surplus to E[∆L] ≤ ∆. Because the surplus bound is monotonically decreasing in s (proof below), this target is met for every allocation at or above the minimum sufficient budget 4 ϵ2 tr Σ ; (12) smin (∆) = ∆2 that is, any s ≥ smin certifies the target tolerance ∆. More generally, an arbitrary per-dimension allocation s certifies the tolerance r tr Σ ∆cert (s) = 2 ϵ , (13) s which meets the target, ∆cert (s) ≤ ∆, precisely when s ≥ smin . If tr Σ scales linearly with dimension, i.e., tr Σ = Θ(d), then a dimension-explicit budget that certifies ∆ is  2   2  ϵ ϵ 2 smin = Θ d , Rmin = d × smin = Θ d . (14) 2 ∆ ∆2 Thus, under this relaxed assumption, the total gradient budget required to hold expected FGSM efficacy constant grows quadratically in d. The correlation-agnostic alignment bound and the minimum-budget computation are given in Appendix G. Discussion. Compared to the i.i.d.-based vMF analysis (whichp yields a Θ(d/s) expected cosine loss 1−E[cos α]), the relaxed expected bound scales as Θ( d/s) when tr Σ = Θ(d). Thus, keeping E[∆L] fixed forces a per-dimension minimum budget that scales as smin = Θ(ϵ2 d) and a total Rmin = Θ(ϵ2 d2 ), a conservative, assumption-light provisioning rule. In our experiments we set ϵ ∝ d0.5 ; the fitted in-regime shot law is s ∝ d2.00 , which equivalently can be written as s ∝ ϵ d1.50 after factoring out the imposed d0.5 scaling of ϵ. This empirical exponent coincides with the relaxed minimum-budget law s ∝ ϵ2 d (i.e., d2 under the same ϵ) and lies below the i.i.d./vMF law with the measured gradient norm inserted (s ∝ ϵd/∥g ∗ ∥, i.e., d2.23 given ∥g ∗ ∥ ∝ d−0.73 ), the shortfall reflecting the measured landscape factor ζ(d) < 1 and the extraction sensitivity of the fit. Table 3 summarises these regimes side by side.

Measurement cost of gradient attacks on QML

18

Table 3: FGSM shot-scaling regimes. Each row states the setting, the resulting per-dimension and total shot scaling, the assumptions required, and the source result. Setting Fixed ϵ, ∥g ∗ ∥=Θ(1), const. τ

√ ϵ∝√d, ∥g ∗ ∥=Θ(1) √ ϵ∝ d, ∥g ∗ ∥=Θ( d) √ Correlated noise, tr Σ=Θ(d), ϵ∝ d ∗ −0.73 Empirical MNIST (∥g ∥∝d measured)

s(d)

R = Θ(d·s)

Assumptions

Source

Θ(d) Θ(d3/2 ) Θ(d) O(d2 ) ≈ d2.00

Θ(d2 )

Asm. 1–3 Asm. 1–3 Asm. 1–3 tr Σ=Θ(d) only Measured; in-regime fit

Prop. 4 Prop. 3 Prop. 3 Cor. 2 §3.1.1, Sec. 4.1

Θ(d5/2 ) Θ(d2 ) O(d3 ) ≈ d3.00

3.1.3. Result: success probabilities under measurement uncertainty Having established shot-scaling requirements for expected loss in the preceding sections, we now derive explicit success-probability bounds. While expected-loss analysis captures average attack degradation, security guarantees often require bounding the probability that an attack succeeds on any given sample. Here, we translate the concentration properties of noisy gradient estimates into probabilistic robustness guarantees.

n sio

ci

de d un bo

misclassified

g∗

y ar correct class

lx

τ

ĝ x+δ

α ϵ

x

Figure 1: Geometry of a single-step shot-noise attack. The sample x lies at perpendicular distance lx from a locally linear decision boundary, with the true gradient g ∗ (blue) pointing toward it. Shot noise deflects the estimated gradient ĝ (red dashed) by angle α; the perturbation of strength ϵ (orange) follows ĝ. The attack succeeds (i.e., x+δ crosses the boundary) only when α ≤ τ = arccos(lx /ϵ). The dotted lines bound the tolerance cone of half-angle τ about g ∗ (its edges reach the boundary at radius ϵ); the grey arc marks τ measured from g ∗ , so the attack succeeds when ĝ falls inside the cone. The geometry of Fig. 1 converts the angular concentration of the noisy gradient into a success probability. Conditioning on an attackable sample at distance lx ≤ ϵ from a locally linear boundary, the single-step attack δ = −ϵĝ succeeds exactly when the estimate falls within the tolerance cone α ≤ τ = arccos(lx /ϵ). Because the normalized estimate is von Mises–Fisher with concentration κvMF ≈ s∥g ∗ ∥2 /σ 2 , the

Measurement cost of gradient attacks on QML

19

success probability is an incomplete-Gamma tail that concentrates, for large d, around √ √ ∗ s τ ∥g ∥ − σ d = const. Holding the success rate fixed (e.g. at 50%) therefore forces s = O(d) per dimension and R = O(d2 ) in total: the same quadratic law as the expectation analysis of Section 3.1.2, now as a tail guarantee rather than an expectedloss bound (Proposition 4; full derivation in Appendix G). 3.2. Multi-step attacks: resource scaling for iterative optimization Iterative attacks amortize the per-step FGSM cost only partially: each iteration refines the perturbation but requires a fresh gradient estimate, so the shot budget grows linearly with the number of steps K. Under a fixed total budget R = Kds the attacker therefore faces a bias–variance–iteration trade-off in which lowering s to buy more steps degrades per-step gradient quality. We study the Carlini & Wagner (C&W) attack [2] as a representative strong iterative attack, because its weighted-sum objective c Lmc (x+δ)+∥δ∥22 maps cleanly onto Stochastic Gradient Langevin Dynamics (SGLD), for which non-asymptotic convergence theory exists [37, 38]. Writing the finite-shot C&W update as SGLD identifies the periteration shot count with an effective inverse temperature, β = 2s/(ησ 2 ) ∝ s (Appendix F): a low shot budget gives a high-temperature, diffusive trajectory, a high budget a low-temperature, greedy descent. This β ∝ s mapping is the modeling framework we use to read the iterative experiments; it predicts the bias–variance trade-off and the empirical shot sweet spot s∗ (d) reported in Section 4.1.2. Combining the mapping with Raginsky et al.’s convergence theorem yields a sufficient total-shot budget, polynomial in d, for convergence below a target loss gap. The operative consequence is that finite-shot convergence theory gives an iterative attacker no guarantee of escaping the single-step scaling within any feasible budget. The explicit degree of this budget, the assumptions and their verification for a canonical PQC/softmax/C&W model, and the sense in which it is a conservative sufficient condition are derived in Appendix F. 4. Numerical and hardware experiments 4.1. Simulation across architectures and datasets Theory predicts a d2 floor for single-step attacks and an empirical scaling excess that exceeds it; the SGLD framework further suggests a bias–variance trade-off for iterative methods. We now test each prediction. Each experimental theme is paired with the theoretical takeaway it interrogates: (i) whether the Θ(ϵd/s) single-step law from Proposition 3 appears in practice as model and data complexity grow; (ii) whether the same scaling persists under changes of the circuit ansatz and the gradient estimator; and (iii) how the SGLD modeling framework of Appendix F.2 manifests as an observable shot-budget sweet spot.

Measurement cost of gradient attacks on QML

20

Datasets and phase-dense encoding, model architecture and training, attack √ normalization (ϵ = κ d, PSR with s shots per input dimension and total budget R = ds), the iterative-attack convention (K = 5 steps with s = R/(Kd)), and the per-(q, s) evaluation protocol are reported in Appendix A.1; the design philosophy that motivates this single-factor-at-a-time setup is summarized in Appendix A.1 (Scope and generality). Taken together, these protocol choices (PSR with budget R = ds, the √ ϵ = κ d schedule, fixed iteration count K, and a single experimental factor varied at a time) ensure that the estimated empirical gradients follow the unbiased, shotlimited model used throughout the theory section: PSR supplies the unbiased estimator √ with variance Θ(1/s) assumed in Assumption 2, the ϵ = κ d schedule instantiates the perturbation scaling invoked in the proofs of Proposition 3, and keeping JL and JU fixed isolates the role of the quantum-layer covariance in (7). Consequently, each experiment can be interpreted as a concrete instantiation of the theoretical resource laws. Each subsequent subsection varies exactly one experimental factor while holding all others fixed: Section 4.1.1 varies (q, d) and dataset choice to study how the singlestep scaling laws manifest empirically. Two robustness checks, swapping the circuit ansatz (Appendix J) and replacing PSR with finite-difference estimators (Appendix K), confirm that the observed scaling is intrinsic to measurement-based gradient estimation, holding across architectures and estimators; detailed plots and discussion are deferred to the appendices. Finally, Section 4.1.2 turns to multi-step attacks (C&W), examining how the per-iteration shot count s sets the effective SGLD temperature and thereby controls the gradient-noise–fidelity trade-off at fixed K; the experiments reveal a dimension-dependent sweet spot s∗ (d) that drifts upward with d, consistent with the noise-temperature picture of the SGLD framework of Appendix F.2. 4.1.1. Shot scaling with dimension and dataset complexity Guided by Proposition 3, we test whether the predicted 1/s dependence between per-dimension shot budget and single-step loss surplus holds empirically, and how the coefficient H(d) scales with dimension. The small-noise analysis behind the proposition fixes the structure of that coefficient: the loss gap obeys ∆L(s) = L(δ) − L(δ ∗ ) ≈

H(d) , s

H(d) =

ϵ (d − 1) σ 2 ζ(d) , 2 ∥g ∗ ∥(d)

where ζ(d) is the landscape factor, the ratio of the realized clean-attack loss rise to its first-order prediction, measured directly in §4.1.1 (ζ(d) = 1 for a locally linear loss). The H(d) ∝ ϵd ∝ d3/2 baseline of Proposition 3 is this rule evaluated under ∥g ∗ ∥ = Θ(1) and ζ(d) = 1; the experiments below measure each factor separately. Using the shared configuration √(Sec. 4.1), we sweep q ∈ {4, 5, 6, 7, 8, 9, 10} on MNIST and Fashion-MNIST under ϵ = κ d. Shot budgets are placed at log-spaced multiples h = s/s⋆ of the critical count s⋆ (d) = (d − 1)σ 2 /2∥g ∗ ∥2 at which the gradient signal-to-noise ratio reaches unity, reaching h = 12 at every dimension including d = 784, well inside the small-noise regime where the 1/s law and the CLT approximation behind Assumption 3 hold; the

Measurement cost of gradient attacks on QML

21

fit window starts at the critical count itself (h = 1), where that ratio equals one. (∥g ∗ ∥ and σ 2 enter the grid construction through preliminary probe measurements that are not part of the reported curves; Appendix A.1.) Figure 2 shows the resulting accuracy and loss curves versus shot budget and model size for both datasets. Two trends emerge: (1) within fixed q, the shortfall from the perfect-gradient attack decays as 1/s, matching O(ϵd/s); (2) across increasing q, larger models require proportionally more shots per dimension for the same shortfall. To extract H(d), we fit the loss gap through the origin, ∆L(s) = Bq /s, on the in-regime points h ≥ 1. Figure 3 plots Bq versus d on log-log axes; power-law fits yield H(d) ∝ d2.00 (95% CI [1.91, 2.08]) for MNIST and H(d) ∝ d2.07 (95% CI [1.99, 2.15]) for Fashion-MNIST, both with R2 = 0.999 (unweighted log–log OLS over the seven dimensions d ∈ {16, 25, 64, 121, 256, 484, 784}; CIs are Student-t at n−2=5 degrees of freedom). The exponent is robust to the extraction method: tightening the window to h ≥ 3 or fitting the saturating form A/(s + B) to all points moves it within [1.96, 2.00] on MNIST and [2.04, 2.07] on Fashion-MNIST. The bare coefficient sets the attacker’s budget, but it is not the theory’s sharpest observable: by the coefficient rule it compounds the geometric shot-noise factor with the model’s 1/∥g ∗ ∥, so its exponent is a joint property of the estimator and the model’s gradient scale. The next paragraphs separate the two by direct measurement; the consistent trends across both datasets already indicate that the scaling is embedded in the gradient estimator and persists across datasets. Gradient-norm baseline. The coefficient rule H(d) = ϵ(d − 1)σ 2 ζ/2∥g ∗ ∥ carries the gradient norm in its denominator, so the bare exponent of Bq conflates the shot-noise geometry with the scaling of ∥g ∗ ∥ itself. We measure that ingredient directly: the FGSM gradient norm decreases with dimension, ∥g ∗ ∥(d) ∝ d−0.73 on MNIST and ∝ d−0.65 on √ Fashion-MNIST (opposite to the d growth of the classical intuition), while the per-shot readout variance stays flat at σ 2 ≈ 3 (measured through d = 121; assumed flat above). The decay is the expected behavior for this model class: at d ≈ 2q it is exponential in qubit count, the barren-plateau signature of deep generic ansätze [59], and our test circuits employ no plateau mitigation. Folding the measured gradient norm back into the coefficient, per sample, forms the gradient-norm-independent combination dL · ∥g ∗ ∥ = 21 ϵ (d − 1) σ 2 ζ(d),

(15)

in which ∥g ∗ ∥ cancels exactly: what remains is the parameter-free geometric shot-noise cost ϵ(d − 1)σ 2 /2 ∝ d3/2 , modulated only by the landscape factor ζ(d). Evaluating Eq. (15) per sample with the measured ζi gives d1.46 on MNIST; the aggregate construction Bq · ⟨∥g ∗ ∥⟩ on Fashion-MNIST gives d1.42 (Fig. I1). Both recover the d3/2 baseline of Proposition 3: the superlinear excess of the bare coefficient over d3/2 is the measured ∥g ∗ ∥ decay, not a property of the noise geometry. The per-sample construction matters because the ingredients are correlated across samples (corr(∥g ∗ ∥, σ 2 ) ≈ +0.75); the absolute scale of the semi-analytic per-sample gap agrees with the empirically fitted

Measurement cost of gradient attacks on QML (a)

22 (b)

0.08

0.04 0.02 0.00

10

10

8

10

1k

Shots

10M

8

10

6

100k

||

0.06

||

0.175 0.150 0.125 0.100 0.075 0.050 0.025 0.000

1k

Shots

4

(c)

6

100k

10M

4

(d)

0.06 0.04 0.02 0.00

10 10

100

8 1k

10k

Shots

100k

6 1M

4

||

0.08

||

0.175 0.150 0.125 0.100 0.075 0.050 0.025 0.000

10 10

100

8 1k

10k

Shots

100k

6 1M

4

Figure 2: FGSM shot-scaling on MNIST and Fashion-MNIST. Waterfall plots versus shot budget and model size, on log-spaced grids at fixed multiples h = s/s⋆ of the critical count, reaching h = 12 at every q. Axes: x = shots per input dimension s (log scale, including both PSR shifts); depth = qubit/class count q ∈ {4, . . . , 10}; height = absolute shortfall of the s-shot attack from the perfect-gradient attack; a marker is drawn at every measured grid point. MNIST is shown in (a) accuracy and (b) adversarial loss, and Fashion-MNIST in (c) accuracy and (d) adversarial loss. Within fixed q, the shortfall decays as 1/s, matching the O(ϵd/s) scaling; across increasing q, curves decay more slowly, requiring larger shots per dimension for constant attack efficacy. The two datasets show the same qualitative trends, confirming that the 1/s scaling law and the superlinear growth of H(d) are properties of the quantum gradient estimator rather than of a particular dataset.

one to within 0.71–0.87, the shortfall being the through-origin extraction reading low at finite h. Takeaway: the single-step exponent. The experiments validate the single-step law at the level of its structure. Every factor of the small-noise rule H(d) = ϵ(d−1)σ 2 ζ/2∥g ∗ ∥ is

Measurement cost of gradient attacks on QML 104

MNIST

in-regime / coefficient

(loss ⋅ shots)

F-MNIST

.

∝ ∝

= .

( .

(

)

= .

closed-form reference ∝

23

) .

103

102

101

100 102

103

input dimension

Figure 3: Per-dimension shot-scaling coefficients. Log–log plot of the throughorigin coefficients Bq (fit window h ≥ 1) versus input dimension d. MNIST: Bq ≈ 4.7 × 10−3 d2.00 (R2 = 0.999); Fashion-MNIST: Bq ≈ 4.5 × 10−3 d2.07 (R2 = 0.999). Dotted: the aggregate reference ∝ d2.23 obtained by inserting the cohort-mean gradientnorm decay into the coefficient rule (§4.1.1). Both datasets exhibit superlinear growth far above the idealized d1.5 baseline, with Fashion-MNIST slightly steeper.

measured independently, and the parameter-free geometric prediction is confirmed: with the gradient norm folded out, the coefficient follows d1.46 (MNIST) and d1.42 (FashionMNIST) against the predicted d3/2 , the small residual carried by the measured landscape factor ζ(d) : 1.05 → 0.83 (a mild, dimension-growing attacker advantage). The simulator results are thus accounted for with no free parameters beyond the measured model properties. The bare fitted coefficient is this geometry compounded by the gradientnorm decay: for the tested plateau-prone circuits, maintaining fixed single-step efficacy costs s ∝ d2.00 per dimension and R = ds ∝ d3.00 (95% CI [2.91, 3.08]) in total on MNIST (d3.07 , [2.99, 3.15], on Fashion-MNIST), while plateau-mitigated models with ∥g ∗ ∥ = Θ(1) realize the geometric floor R = Θ(d5/2 ). An aggregate estimate that inserts the cohortmean gradient norm, instead of averaging per sample, brackets this d2.00 from above at d2.23 (Appendix I). Three reference exponents recur through the paper: the gradientnorm-free shot-noise geometry d3/2 (per dimension, measured d1.46 ); the total-budget floor R = Θ(d5/2 ) reached by plateau-mitigated models; and the realized total budget R ≈ d3.00 of the tested gradient-decaying circuits, the floor inflated by their ∥g ∗ ∥ decay. The total budget thus grows fast enough to erode the practicality of high-accuracy gradient attacks on large QML models. Architectural robustness. To verify that these scaling laws are not artifacts of a particular circuit ansatz, we repeat the (q, s) sweep under the same grid protocol for

Measurement cost of gradient attacks on QML

24

a data re-uploading variant that encodes the input twice, at the input and at middepth, within a single 200-layer circuit, for q ∈ {4, 5, 6, 7}. The in-regime fit yields c0 ∝ d1.99 , statistically indistinguishable from the single-upload d1.96 over the matched dimension range. The coefficient itself is also unchanged (pre-factor ratio 0.98): the second encoding pathway raises both the gradient norm (≈ 1.6×) and the per-shot readout variance (≈ 1.6×), and the two cancel in the coefficient rule H ∝ σ 2 /∥g ∗ ∥, a direct architectural confirmation of that structure. The residual architectural cost is the evaluation count: each input component appears in two encoding blocks, so a PSR gradient costs four shifted circuit evaluations per dimension instead of two, doubling the total budget per gradient at equal s. Architecture thus modulates the constants of the cost via the JL /JU factors and the encoding multiplicity rather than the fundamental dimension dependence. Full waterfall plots, coefficient fits, and detailed discussion are provided in Appendix J. Estimator comparison. Appendix K compares PSR against finite-difference (FD) and SPSA estimators under matched shot budgets. The key finding is that estimator choice affects constants and low-shot crossovers but not the fundamental scaling: Being an unbiased estimator, PSR dominates at moderate/large s. Full plots and discussion are given in Appendix K. Practical cost at scale. To see what the two-layer cost structure implies in practice, consider a single-step FGSM attack on a d = 784 (q=10) MNIST classifier. The smallest measured budget that brings the attack within ∼15% of its perfect-gradient accuracy drop is s ≈ 7 × 105 shots per input dimension (= 2 × 3.4 × 105 , the two PSR shifts), above the critical count s⋆ (784) ≈ 4 × 105 set by the measured gradient norm. Because all output observables are mutually commuting Zi measurements, they are obtained from the same circuit run (see the compatible-observables discussion in Section 2.4), so the total shot budget is R = ds ≈ 5 × 108 per adversarial sample. Assuming a typical circuit execution time of ∼100 µs per shot, crafting a single adversarial example requires ∼5 × 104 s ≈ 15 hours of sequential device time. Mounting a dataset-wide attack on the full MNIST test set (10,000 images) would therefore consume ∼1.5 × 105 hours ≈ 17 years of continuous device time. Parallelization can reduce wallclock time but not the total number of shots required; the aggregate quantum resource cost remains the same. These estimates further assume zero queuing, calibration, or communication overhead; real deployments would be slower still. 4.1.2. Multi-step attacks and optimal shot allocation For iterative C&W attacks at fixed iteration count K, the per-iteration shot count s is the sole control on gradient noise, setting the SGLD temperature β ∝ s through Eqs. (F.2) and (F.3). Low s (high temperature) makes each step imprecise but lets the stochasticity dislodge the iterate from shallow minima of the C&W landscape; high s (low temperature) gives accurate steps that, within a fixed K, more readily settle into the nearest local trap. An optimal

Measurement cost of gradient attacks on QML

25

budget s∗ (d) therefore emerges from this fidelity-versus-exploration trade-off, which the SGLD framework (Appendix F) predicts qualitatively through β. When K is instead free under a fixed total R = Kds, lowering s also buys more iterations, the classical bias–variance trade-off; holding K fixed isolates the noise-driven escape effect probed below. √ We examine C&W under the shared K = 5 iteration budget and ϵ = κ d. The periteration shots s are swept for qubit counts q ∈ {4, 5, 6, 7}, with adversarial effectiveness recorded as in the single-step analysis (post-attack accuracy and loss surfaces). C&W loss values are not compared across q because the tuned coefficient c is sample dependent. Tuning overhead is excluded from R, so any practical search would only strengthen the observed scaling. Empirically, increasing s from low values strengthens the attack: post-attack accuracy falls toward the exact-gradient (infinite-shot) value, and the budget s∗ (d) at which it saturates grows steeply with dimension, from s∗ ≈ 6 × 102 at d=25 to ≈ 4 × 104 at d=121, nearly two orders of magnitude and broadly consistent with the s ∝ d2 growth of the single-step law. Figure I3 plots the signed accuracy gap to that exact-shot attack; because the reference shares the swept points’ search budget, the gap is a clean measure of shot noise alone. In three of the four models (d ∈ {16, 25, 121}) the optimum drops below the exact-shot value: a moderate amount of shot noise makes the attack stronger than an exact gradient, so a noisy gradient step is here preferable to the exact one. This is the stochastic-regularization effect the SGLD picture predicts, the shot noise playing the role of Langevin exploration that escapes shallow minima of the C&W objective. The sub-floor depth is largest at small d (0.9 pp at d=25, 0.3 pp at d=16) and narrows to 0.13 pp at d=121 (all resolved at > 4σ by averaging five shot-noise realizations); only d=64 shows no sub-floor dip, descending monotonically to the exact-shot floor. Simple warm-up schedules that raise s over iterations can outperform uniform allocation at the same R, echoing classical SGLD heuristics. The four tested dimensions are too few to fit a precise exponent for the iterative case. Because s∗ climbs steeply with d while the sub-floor benefit shrinks, the budget an iterative attacker must spend to reach the exact-gradient attack, let alone improve on it, grows rapidly with dimension, mirroring the single-step cost law. The trend holds across the dimensions tested at fixed K and step size η. Takeaway. A dimension-dependent optimum s∗ (d) emerges from the gradient-noise– fidelity trade-off at fixed K: the SGLD temperature β ∝ s must be high enough for the chain to escape shallow local minima yet low enough for gradient updates to be constructive; we fix K and η instead of optimizing schedules and exclude hyperparameter-tuning overhead (e.g., binary search on c in C&W), so accounting for such costs would only make attacks more expensive in practice. Across the four dimensions tested, both s∗ (d) and Rcrit (d) rise with d in a manner qualitatively consistent with the SGLD framework of Appendix F.1. Simple warm-up/annealed shot schedules can improve effectiveness at the same R. A precise empirical scaling exponent for

Measurement cost of gradient attacks on QML

26

iterative attacks would require a broader dimension sweep and is left to future work; the SGLD analysis (Appendix F) supplies the modeling framework that accounts for this trend. 4.1.3. Classical baseline comparison The preceding quantum scaling laws quantify how attack cost grows with d, but the force of this result depends on the contrast with the classical case. We now provide that anchor by training matched classical neural networks on the same dimension ladder, perturbation budget, and datasets, measuring both the gradient cost ratio and the attack success rate. Classical model and timing protocol. The matched VGG-style CNN architecture (channel base c = 2q, parameter counts comparable to the quantum circuits), the √ d/32 matched to the quantum experiments, and the perturbation budget ϵ = per-sample CPU wall-clock timing protocol (100 warmup iterations, 500 samples × 5 repetitions, median reported) used to compute ρclassical = tbwd /tfwd are reported in Appendix A.2; attack success rates are measured separately on the full test set using a GPU. Results. Table 4 reports the measured gradient cost ratio and the quantum comparison. Two findings emerge. First, ρclassical ≈ 5.2 ± 0.6 across all d, with no systematic trend (ρ ∝ d−0.04 , exponent indistinguishable from zero), confirming the O(1) prediction of the Baur– Strassen theorem (Remark 1). Second, the quantum overhead grows polynomially: ρquantum ∝ d3.00 (95% CI [2.91, 3.08]) on MNIST and d3.07 (95% CI [2.99, 3.15]) on Fashion-MNIST, extracted from the in-regime shot-scaling fits of Section 4.1.1; the realized exponent reflects the tested models’ measured gradient-norm decay, with the d2.5 geometric floor applying to plateau-mitigated models with ∥g ∗ ∥ = Θ(1). The ratio ρquantum /ρclassical grows as Θ(d3.00 ) on MNIST and Θ(d3.07 ) on Fashion-MNIST, independent of the forward-inference normalization, and the quantum overhead exceeds the classical one for d ≳ 30 (Table 4). Figure 4 visualizes this contrast on log–log axes. The classical line is flat; the quantum curves rise with slopes matching the fitted exponents from Section 4.1.1 and run steeper than the Θ(d2.5 ) reference, the gradient-norm excess over the idealized baseline (§4.1.1). Takeaway. Against the classical baseline, quantum measurement noise imposes a gradient cost ratio that is empirically ρquantum ≈ Θ(d3 ) for the tested models (with Θ(d2.5 ) the geometric floor under ∥g ∗ ∥ = Θ(1)) while classical backpropagation gives ρclassical = O(1) (the cheap-gradient principle). The contrast is structural, it arises from the decoupling of forward and backward measurement costs in quantum systems (Remark 1), and the overhead ratio grows with every additional input dimension.

Measurement cost of gradient attacks on QML

27

Table 4: Gradient cost ratio: quantum vs. classical. Classical ρ (CPU wall-clock, median of 500 samples × 5 reps) is flat at ≈ 5; quantum ρ (polynomial fit of the shotscaling data, Section 4.1.1) grows polynomially. Rbwd = 2d c0 (d)/∆L⋆ is the shot count to reach a fixed attack-efficacy target ∆L⋆ (Appendix E); Rfwd = 100 is the forward2 inference budget (Proposition 2; C = q commuting outputs at σfwd ≈ 3, rounded up conservatively). The ratio column scales as 1/Rfwd ; the exponent is independent of Rfwd and ∆L⋆ . For d ≤ 25 the quantum overhead is at or below the classical value. Values to two significant figures. MNIST

Fashion-MNIST

d

ρcl

ρqu

ratio

ρqu

ratio

16 25 64 121 256 484 784

5.4 4.9 6.1 5.4 5.4 4.5 4.4

0.38 1.7 21 1.7 × 102 1.4 × 103 1.0 × 104 5.0 × 104

0.07× 0.3× 3.5× 31× 250× 2.3 × 103 × 1.1 × 104 ×

0.42 2.1 28 2.2 × 102 2.0 × 103 1.5 × 104 7.7 × 104

0.08× 0.4× 4.7× 41× 370× 3.4 × 103 × 1.7 × 104 ×

Classical CNN (MNIST) Classical CNN (F-MNIST) Quantum (MNIST) Quantum (F-MNIST)

105 104

Theory (

( )

103

.

)

102 101 100 10−1 101

102

103

input dimension

Figure 4: Gradient cost ratio ρ(d) on log–log axes. Classical CNN (blue): flat at ρ ≈ 5, confirming O(1) scaling (Baur–Strassen). Quantum (red/orange): polynomial growth ∝ d3.00 (MNIST), d3.07 (Fashion-MNIST). Dashed gray: Θ(d2.5 ) geometricfloor reference, anchored at the MNIST d=121 point. The quantum–classical overhead ratio grows as Θ(d3.00 ), with absolute value set by the forward-inference normalization (Table 4).

4.2. Hardware validation The theoretical predictions and simulation results above establish shot noise as a fundamental impediment to gradient-based attacks. We now test whether this robustness survives deployment on real quantum hardware, where gate errors,

Measurement cost of gradient attacks on QML

28

Table 5: Shot-noise robustness, simulation vs. experiment (d = 12, N = 100, ϵ = 1.0). Adversarial accuracy at the smallest budget, at a high budget, and at the exactgradient limit. The 10% floor is the cohort’s intrinsic-robust fraction and the s → ∞ limit of the simulation; at high budget the experiment stays a couple of percentage points above the simulation and does not reach this floor, its gradient device-biased. The low-shot gap is shot-noise–induced on both.

Simulation Experiment

Acc (s = 2) 46.3% 42.2%

Acc (s = 2048) 12.4% 14.0%

Exact floor (s → ∞) 10.0% n/a

decoherence, and readout imperfections introduce additional noise beyond idealized shotsampling statistics. The deployed model is a 4-qubit hardware-efficient classifier on 3 × 4 MNIST (d = 12), attacked with ℓ2 FGSM at ϵ = 1.0 across a logarithmic sweep of the attacker’s shot budget s on both an ideal simulator and ibm_boston. The defender is evaluated noiselessly, so device noise enters only through the attacker’s gradient; deployment, tiling, and sampling details are in Appendix B. 4.2.1. Results: shot-noise robustness on real hardware Figure 5 presents adversarial accuracy (a) and the loss gap to the full-precision attack (b) versus shot budget for simulation and experiment; Table 5 summarises the endpoints. Hardware tracks the simulator. In both simulation and experiment, adversarial accuracy rises sharply as the budget falls, from ∼42–46% at the two-shot minimum toward the intrinsic-robust floor (Fig. 5a), driven entirely by the shot budget at fixed ϵ with the critical transition near s ∼ 12. The 100-input cohort resolves the two curves well below their separation. They cross near s ∼ 12: above it the simulation attack is stronger by 1–3 percentage points, the experimental gradient running behind ideal once the shot budget is large enough to expose the device’s gate and readout error; below it the experiment is marginally stronger, consistent with the within-ball criterion, under which a more isotropic low-shot direction is slightly likelier to find a boundary crossing in the near-random regime. Only the simulation reaches the exact-gradient floor (10%) as s → ∞; at high budget the experiment plateaus a couple of percentage points above the simulation, a residual the device cannot remove because its gradient stays biased. The loss gap to the exact-optimal attack, ∆L(s) = L(δ ∗ ) − L(δs ), closes toward zero in simulation and toward this residual in experiment (Fig. 5b), the optimization-gap decay of Proposition 3. The hardware gradient is faithful. At the full 8192-shot measurement the parametershift gradient on hardware aligns with the exact gradient at a cohort-median cosine of 0.98 (mean 0.90): the typical sample is recovered almost exactly, with a few low-cosine

(a) Simulation Experiment (ibm_boston)

adversarial accuracy (%)

45 40 35 30 25 20 15 10

exact-gradient limit (10%) 10

100

1000

attacker shots per parameter, s

loss gap to exact-optimal attack, ΔL(s)

Measurement cost of gradient attacks on QML

29 (b)

0.5

0.4

0.3

0.2

0.1

0.0 10

100

1000

attacker shots per parameter, s

Figure 5: Shot-noise robustness: simulation vs. experiment on ibm_boston (d = 12, N = 100, ϵ = 1.0). (a) Adversarial accuracy and (b) loss gap to the exactoptimal attack, ∆L(s) = L(δ ∗ ) − L(δs ), versus attacker per-parameter shot budget s (log axis) under ℓ2 FGSM. The simulation reaches the exact-gradient floor (10%, dashed) as s → ∞; the experiment plateaus above it, its device-biased gradient bounded by the measured budget. Error bars are the standard error of the bootstrap mean over 200 shot-resamples (smaller than the markers). Protocol in the text and Appendix B.

samples pulling the mean down and producing the high-budget residual above. Gate errors and decoherence barely rotate the gradient once shot noise is removed; what blunts the attack at low s is the irreducible sampling uncertainty of the estimator, which isolates shot noise as the operative mechanism. As hardware fidelity improves, this device contribution shrinks while measurement uncertainty remains, so the shotnoise gap persists; and as the data dimension grows (d > 10), the quadratic shot requirement renders high-quality gradient attacks rapidly prohibitive, especially for multi-step methods whose budgets accumulate over iterations. 5. Discussion and conclusion The picture that emerges from theory and experiment is that finite quantum measurement imposes a shot-cost floor on gradient extraction, and that this floor reshapes adversarial attack efficacy as the input dimension grows. For single-step attacks we derive a simple law tying optimization error to the per-dimension shot budget, ∆L(s) ≈ H(d)/s with H(d) ∝ ϵd, which implies that maintaining fixed efficacy under growing dimension requires at least s = Θ(d) and thus a quadratic growth in total gradient shots. For multi-step C&W, mapping the finite-shot updates to SGLD and applying Raginsky et al.’s non-asymptotic convergence theory yields a sufficient total-shot budget polynomial in d (Appendix F); this certificate provides a modeling framework that correctly predicts the observed bias–variance trade-off.

Measurement cost of gradient attacks on QML

30

Experiments validate these predictions across model sizes, architectures, and estimators, and let us account for every measured exponent with no free parameters beyond the model’s own properties. The sharpest test isolates the geometry of the bound: with the gradient norm folded out, the measured combination follows the parameter-free d3/2 prediction (d1.46 on MNIST, d1.42 on Fashion-MNIST; §4.1.1), and the waterfall plots (Fig. 2) confirm the underlying 1/s decay. The bare per-dimension requirement (Fig. 3) is this geometry compounded by the model’s gradient scale, and the exponent ledger closes explicitly: the geometric floor is d3/2 per dimension (total R = ds = d5/2 ); inserting the measured gradient-norm decay ∥g ∗ ∥ ∝ d−0.73 through the bound’s 1/∥g ∗ ∥ factor would predict d3/2 · d0.73 = d2.23 per dimension; and the measured landscape factor ζ(d) < 1, local curvature returning a small advantage to the attacker, pulls this back to the observed d2.00 (d2.07 on Fashion-MNIST), a total budget of d3.00 (d3.07 ). PSR-versus-FD comparisons confirm that the choice of estimator mainly modulates constants and low-shot transients, with PSR dominating at moderate or large budgets. In the multi-step regime, we observe a reproducible sweet spot s∗ (d) that drifts upward with dimension and can be improved by simple warm-up schedules; the critical budget Rcrit (d) rises across the four tested dimensions, though we do not fit a specific exponent given the limited range. The resulting cost structure is a d5/2 geometric shot-noise floor, realized as-is by plateau-mitigated models with ∥g ∗ ∥ = Θ(1) [57, 59], and inflated to ≈d3 for the tested generic deep circuits by the gradient-norm decay traced above; alternative estimators relocate the dimension cost instead of removing it (Appendix L), and for d=784 even a single FGSM sample already requires ∼15 hours of device time (Section 4.1). The classical baseline comparison (Section 4.1.3) makes the overhead gap concrete. A matched classical CNN, trained on the same tasks with comparable parameter counts, yields ρclassical ≈ 5 across all dimensions: flat, exact, and dimension-independent, precisely as predicted by the Baur–Strassen theorem [27, 28]. Against this anchor, the quantum gradient cost ratio of the tested models, ρquantum ∝ dp1 with p1 = 3.00 (95% CI [2.91, 3.08]) on MNIST and p1 = 3.07 (95% CI [2.99, 3.15]) on Fashion-MNIST, makes the relative gradient-extraction cost diverge as Θ(dp1 ) against this dimensionindependent baseline. Classical models are fully vulnerable at all dimensions (C&W success ≥ 87%); quantum models are not intrinsically harder to fool. The defense is that the gradient information needed to fool them costs polynomially more to acquire. As scoped in Section 1, this barrier is operative where the forward map is classically hard to simulate, the setting in which QML is expected to be useful, since only there is a white-box attacker forced onto measurement-based extraction instead of free classical backpropagation; the experiments here, run on deliberately simulable systems, establish the underlying scaling law that fixes that cost. These scaling laws survive the move from simulation to real hardware. On IBM’s 156-qubit ibm_boston processor, a matched simulation-versus-experiment comparison at d = 12 over a 100-input cohort reproduces the shot-noise robustness (Section 4.2): the high-shot gradient is faithful (cosine 0.90), the simulation reaches the exact-gradient

Measurement cost of gradient attacks on QML

31

floor (10%) as s → ∞, and the experiment plateaus a few percent above it. That residual is a device bias the attacker cannot remove, so the observed low-shot robustness reflects finite measurement rather than a simulation artifact and persists under device imperfection. Improvements in gate fidelity and coherence will suppress this deviceinduced noise while leaving measurement uncertainty intact, sharpening the robustness gap rather than closing it. Our shot-budget scaling laws are independent of structural robustness guarantees such as the dynamical conditions (unitarity, scrambling, chaos) studied in [13]: those conditions bound whether certain attack classes are possible in principle, whereas our results quantify the physical measurement cost of executing any gradient-based attack in practice. The two axes are orthogonal, and the shot-cost barrier applies even to attacks that such structural conditions permit. Two practical implications follow: evaluations of QML robustness should report and normalize by shot budgets, and defenses that amplify or exploit shot sensitivity (controlled noise injection, budget-aware training, adaptive shot allocation) are promising complements to architectural choices. Several limitations bound these conclusions. We use fixed step sizes and hyperparameters, modest qubit counts q, and restricted repeats due to classical simulation cost; we focus on PSR as the primary estimator, though zero-order methods retain dimension-dependent shot requirements (Appendix L). The defensive consequence is scoped to the classically-hard regime (Section 1): at the simulable sizes tested, a white-box attacker can simulate and backpropagate to circumvent the shot requirements entirely, so the experiments establish the scaling law rather than a deployed defense. The multi-step certificate of Appendix F is sufficient rather than necessary, and the empirical exponents exceed the d5/2 baseline through the measured gradient-norm decay, with local curvature, measured directly, returning a small advantage to the attacker instead of penalizing it. These limitations motivate future work on (i) realistic hardware noise beyond shot noise, (ii) principled annealing and adaptive shot-allocation schedules for multistep attacks, (iii) model-level regularizers that widen the effective energy barriers (improving λ∗ ), (iv) extensions beyond gradient-based attacks, (v) adapting the finiteshot framework to QML regression with continuous outputs, (vi) full analysis of zero-order methods such as SPSA under shot constraints, including bias–variance– convergence trade-offs for adversarial optimization, and (vii) measuring the realized attack cost of plateau-mitigated architectures [57, 58], which the validated coefficient rule predicts sits at the d5/2 geometric floor. Scaling toward d∼50 to 100 dimensions pushes single-step requirements into millions of shots, and shot-noise robustness can be further amplified via adversarial training under low-shot conditions or architectures that increase gradient variance. We hope these scaling laws and empirical patterns provide a clear target and a common language for benchmarking adversarial robustness in the finite-shot regime.

Measurement cost of gradient attacks on QML

32

Acknowledgments This work was supported by CSIRO under grant number 27040. We acknowledge the use of IBM Quantum services for this work; in particular, hardware experiments reported in Section 4.2 were performed on the ibm_boston processor accessed through the IBM Quantum Network. The views expressed are those of the authors and do not reflect the official policy or position of IBM or the IBM Quantum team. The authors declare no competing interests. Data availability statement This study used publicly available datasets only (MNIST and Fashion-MNIST); no new training datasets were generated. The data that support the findings of this study, namely the aggregated quantum hardware run results, the low-shot bootstrap traces used in Section 4.2, and the per-dimension coefficient tables underlying Fig. 3 and Fig. 4, will be made openly available in a public archive at a later date; in the interim they are available from the corresponding author on reasonable request. Raw IBM Quantum job records and per-circuit measurement strings are available from the corresponding author on reasonable request. A cleaned and documented release of the simulation, attack, and analysis code that supports the findings of this study will be made openly available at a later date; in the interim, the code is available from the corresponding author on reasonable request.

Measurement cost of gradient attacks on QML

33

The appendices are grouped in three parts. Methods and reproducibility collects the simulation and hardware deployment protocols, the phase-dense encoding, and the classical-baseline and software details. Supporting theory collects the multi-step SGLD mapping and sufficient-budget certificate, the covariance and cost-dominance derivations and proofs, the success-probability route, and the ℓ2 -budget scaling. Robustness checks collects the architectural and estimator variations, the supporting simulation figures, and the zero-order methods. Part I: Methods and reproducibility Appendix A. Simulation protocol This subsection collects the reproducibility-critical experimental configuration that supports the simulation results in Section 4.1 (single-step shot scaling, multi-step allocation, and the classical baseline comparison). Appendix A.1. Common experimental configuration All experiments draw from a shared base configuration so that individual subsections isolate one factor at a time while adhering to the setup discussed in Section 2. • Datasets and encoding. Unless noted otherwise, we use MNIST and Fashion–MNIST with phase–dense encoding (Appendix D), mapping the downsampled input to q qubits so that d ≤ 2q and d = a2 for integer a of pixel length of the square downsampled image. Resulting in (q, d) ∈ {(4, 16), (5, 25), (6, 64), (7, 121), (8, 256), (9, 484), (10, 784)}; these dimensions span two orders of magnitude with systematic doubling, and d = 784 is the native MNIST resolution (28 × 28). The number of classes is C = q, choosing from the first q classes of each dataset and balancing the training and test splits. Data is normalized to [−π/2, π/2] before encoding √ so that the Gaussian concentration argument in Appendix H aligns with the ϵ = κ d scaling used in Proposition 3. • Models and training. Baseline classifiers employ 200 strongly-entangling layers (SEL; Fig. A1) with identical initialization and optimization hyperparameters across qubit counts. Trainable rotation parameters are drawn entrywise from N (0, 1); the default random-number-generator state was used and no fixed seed was set, and we verified that multiple independent re-runs produced consistent training trajectories and final test accuracy. Training uses Adam with cross-entropy loss; learning rate 0.001 for q ≤ 7 and the variants used for q ∈ {8, 9, 10} are documented in the released configuration files. Parameter counts are matched to the classical baseline of §Appendix A.2 so that the two pipelines compare like-for-like across d: each quantum classifier carries 200 × 3 × q trainable rotation parameters (e.g. 6,000 at q = 10), and the CNN’s channel width c = 2q yields a comparable parameter budget at every dimension (Table E1 in Appendix E). When architectural variants

Measurement cost of gradient attacks on QML

34

are tested (Appendix J), only the ansatz changes; training schedules, data splits, and normalization remain fixed, preserving the Jacobian factors JL and JU that appear in the variance expression (7). A deep, generically-entangling stack of this kind generates a near-maximal dynamical Lie algebra (the highly expressive class for which the expressivity–measurement-efficiency trade-off [29] forces few simultaneously measurable gradient components), so the no-amortization premise of the single-step bound is met by construction at every q, independently of whether the tested instance is classically simulable. √ • Attack normalization. For attacks, we set the perturbation radius to ϵ = κ d, matching the Gaussian norm concentration rationale in Appendix H. Gradients are estimated with the parameter–shift rule (PSR) using an average of s shots per input dimension, giving total budget R = ds per query. Loss surplus ∆L(s) = L(δ)−L(δ ∗ ) and post–attack accuracy are the primary metrics, mirroring the optimization error in Proposition 3 and the SGLD framework of Appendix F.2. • Shot-grid provisioning. For the single-step sweeps, per-dimension shot budgets are placed at up to eight log-spaced multiples h = s/s⋆ of the critical count s⋆ (d) = (d − 1)σ 2 /2∥g ∗ ∥2 , spanning h ∈ [0.3, 12] (d = 784 omits the lowest subcritical multiples), so that every dimension reaches h = 12, well inside the smallnoise regime. The ∥g ∗ ∥ and σ 2 values entering the grid construction come from preliminary per-sample probe runs used only to set the grids; they are not part of the reported attack curves. Coefficient fits use the window h ≥ 1, i.e. from the critical count s⋆ upward. • Iterative attacks. When studying C&W, we retain the same ϵ schedule and distribute a fixed total budget R over K iterations with per–dimension per–iteration shots s = R/(Kd). Unless otherwise specified, we use K = 5 steps and a constant learning rate; tuning overhead (e.g., binary search on the C&W coefficient c) is excluded from R. • Evaluation protocol. For each (q, s) pair, we attack 200 balanced test samples (rounded as needed). Reported quantities average over all attacked samples without multiple gradient re-sampling to keep the classical cost tractable. Scope and generality. The design space of QML models, spanning circuit ansätze, encoding schemes, depths, datasets, and attack configurations, is vast, and exhaustive coverage is computationally infeasible. Our experimental methodology, therefore, isolates individual factors (architecture, estimator, iteration count) while holding others fixed, enabling controlled comparisons that reveal how each factor modulates the underlying scaling laws. The consistent 1/s decay and superlinear growth of the coefficient observed across all tested configurations suggest that the shot-noise constraints are a fundamental feature of measurement-based gradient estimation. While future work may extend the parameter ranges or introduce additional circuit families,

Measurement cost of gradient attacks on QML

35

(a) |0⟩ |0⟩ |0⟩

H H .. . H

Φ(x)

SEL layer 1

···

SEL layer L=200

.. .

200 trainable layers (b)Contents of one SEL layer U U U U Single-qubit rotation U ≡ U (ϕ1 , ϕ2 , ϕ3 ) (a general SU (2) Eulerangle rotation) on every wire, followed by a ring of CNOTs whose stride cycles with the layer index ℓ.

Figure A1: Simulation ansatz. (a) The simulation pipeline (Appendix A): Hadamards on each of q ∈ {4, . . . , 10} wires, a phase-dense encoding Φ(x) of the d-dimensional input (d up to 784), 200 strongly-entangling layers (SEL), and single-qubit Pauli-Z readouts. (b) Contents of one SEL layer: a column of trainable single-qubit rotations U ≡ U (ϕ1 , ϕ2 , ϕ3 ) followed by a ring of CNOTs whose stride cycles with ℓ. Each layer carries an independent set of trainable angles.

the methodological principle of varying one factor at a time against a shared baseline ensures that conclusions about scaling behavior remain interpretable and generalizable. Appendix A.2. Classical baseline: model and timing protocol For each (q, d, C) configuration, we train a VGG-style CNN with width scaled by qubit count (c = 2q base channels) so that parameter counts remain comparable to the quantum circuits (Table E1 in Appendix E). The perturbation √budget matches the √ quantum experiments exactly: ϵ = d/32, giving a constant ϵ/ d = 0.03125 across all d. The gradient cost ratio is defined as ρclassical = tbwd /tfwd , with wall-clock timing a proxy for this dimensionless arithmetic-cost ratio. To obtain stable measurements that reflect the intrinsic arithmetic cost ratio (rather than GPU kernel-launch artifacts; see Appendix E), we time per-sample forward and backward passes on CPU with 100 warmup iterations followed by 500 samples × 5 repetitions, reporting the median. The backward pass computes the gradient by reverse-mode automatic differentiation with respect to the input, yielding the exact gradient an attacker would use. Attack success rates are measured separately via standard FGSM and C&W attacks on the full test set using a GPU.

Measurement cost of gradient attacks on QML (a) |0⟩ |0⟩ |0⟩ |0⟩

36

3 RX uploads (3×4=12 features)

HWE HWE HWE RX RX RX ×3 ×3 ×3

margin readout

HWE ×6

15 HWE layers (b)Contents of one HWE layer U U

U U

RZZ RZZ

U

U RZZ

U

U

Single-qubit rotation U ≡ U (ϕ1 , ϕ2 , ϕ3 ) on every wire, a two-step brick of parametric RZZ entanglers (even pairs, then odd pair), and a closing column of U rotations.

Figure B1: Hardware ansatz. (a) Hardware deployment on ibm_boston (Appendix B): a 4-qubit hardware-efficient ansatz (HWE) encoding d = 12 features on q = 4 qubits. Three RX(x) feature-upload blocks (four features each, one per qubit) are interleaved with HWE entangling layers: three layers before the first upload, three after each upload, and three more closing the circuit, for 15 HWE layers in total. Only the two middle qubits are measured: the binary label is the margin ⟨Zq1 ⟩ − ⟨Zq2 ⟩ between them, while the outer qubits are entangled but left unread. The reduced depth keeps the transpiled circuit within the device coherence budget. (b) Contents of one HWE layer: a column of trainable single-qubit rotations U ≡ U (ϕ1 , ϕ2 , ϕ3 ), a two-step brick of parametric RZZ entanglers (even pairs, then odd pair), and a closing column of U rotations. Each layer carries an independent set of trainable angles.

Appendix B. Hardware experimental setup This subsection collects the deployment, attack-execution, and bootstrap-sampling protocol used for the hardware experiments reported in Section 4.2. We deploy a 4-qubit hardware-efficient classifier (HWE; Fig. B1) on 3 × 4 downsampled MNIST (d = 12), trained on an ideal noiseless simulator with the parametershift rule (PSR) and transferred to ibm_boston without retraining; three RX featureupload blocks encode the d = 12 features on the q = 4 qubits. We retain HWE rather than the 200 strongly-entangling layers of §Appendix A so the transpiled depth stays within the device coherence budget. We attack with ℓ2 FGSM at ϵ = 1.0 and sweep the attacker’s per-parameter shot budget s on a logarithmic grid; each parameter spends s shots across its two PSR shift circuits (so s ≥ 2), and R = d · s is the total. The 2d+1 PSR shift circuits run in parallel across 20 disjoint 4-qubit tiles (one input per tile), each measured once as a wide circuit

Measurement cost of gradient attacks on QML

37

at 8192 physical shots with dynamical decoupling and gate/measurement twirling, from which the budget-s gradients are bootstrap-resampled. From these counts we bootstrap-resample the per-shift measurements to synthesize the budget-s gradient (each parameter using its two parameter-shift circuits, so the minimum budget is s = 2). The simulation’s s → ∞ limit uses the exact gradient; on hardware the gradient retains the device bias, so the attack is bounded by the measured budget, short of the exact-gradient limit. The defender margin at the perturbed point is evaluated on an exact statevector, so device noise enters only through the attacker’s gradient. A sample is attacked if any point on the ϵ-ball segment along the noisy gradient direction is misclassified; we report the mean adversarial accuracy over 200 bootstrap resamples, with error bars giving its standard error (below 0.5% at every budget). We compare ibm_boston (median two-qubit error ∼0.12%, T2 ∼320 µs, readout ∼0.35%, stable across the measurement window) against the ideal statevector simulator, on inputs pre-selected by correct noiseless classification (the full 100-input cohort, measured in five tile-batches of 20). Appendix C. Software stack and statistical fitting Simulation and hardware experiments were run on Linux (Ubuntu via WSL) with Python 3.11. Quantum components used PennyLane 0.42 (with PennyLaneLightning 0.42 and PennyLane-Qiskit 0.42), Qiskit 1.2, Qiskit-Aer 0.16 (Qiskit-AerGPU 0.15), Qiskit-IBM-Runtime 0.29, and Qiskit-Machine-Learning 0.8. Classical learning used PyTorch 2.10 (CUDA 12.8 build) with torchvision 0.25, alongside the standard scientific-Python stack. Power-law exponents are obtained by an unweighted log–log ordinary-least-squares fit of the per-dimension coefficient c0 (d) (through-origin slope of the loss gap versus 1/s on the in-regime points h ≥ 1) against d ∈ {16, 25, 64, 121, 256, 484, 784}, yielding a slope p2 ; the total-shot exponent reported in the body is p1 = p2 + 1 (since R = d · s and s ∝ c0 (d)). The 95% confidence interval is the Student-t interval on the regression slope with n−2=5 degrees of freedom (the +1 shift does not change its half-width). Appendix D. Phase-dense encoding details Standard angle encoding injects one feature per qubit per encoding layer via singlequbit rotations RZ(xj ), yielding a capacity of at most q features per layer. To encode d features with only q qubits in a single encoding step, we employ a phase-dense encoding defined by d  X 
Uenc (x) = exp i xj |j⟩⟨j| = diag ei x1 , . . . , ei xd , 1, . . . , 1 , j=1

where {|j⟩} denotes the 2q -dimensional computational basis. Each classical feature xj is assigned to a distinct basis state, giving an encoding capacity of d ≤ 2q .

Measurement cost of gradient attacks on QML

38

This matches the experimental configurations (q, d) ∈ {(4, 16), (5, 25), (6, 64), (7, 121), (8, 256), (9, 484), (10, 784)}; when d < 2q , unused basis-state phases are set to zero. PSR compatibility. The generator associated with feature xj is the projector Gj = |j⟩⟨j|, whose spectrum is {0, 1} with spectral gap ∆Gj = 1. Since each Gj has exactly two distinct eigenvalues, the parameter-shift rule (Eq. 1) applies directly:   ∂⟨O⟩ = 21 ⟨O(x + π2 ej )⟩ − ⟨O(x − π2 ej )⟩ , ∂xj requiring two shifted circuit evaluations per input dimension. Hardware depth caveat. Any decomposition of Uenc into a standard hardware gate set such as {CNOT, U3 } requires Θ(2q ) gates, i.e., circuit depth exponential in q. This is unavoidable: encoding d ≤ 2q independent phases into computational-basis amplitudes demands at least d parameterized gates. In our experiments, classical statevector simulation sidesteps this constraint entirely. On near-term hardware, the exponential depth limits phase-dense encoding to small q; however, the shot-noise scaling laws derived in the paper depend only on the number of input features d and the PSR structure (two shifted evaluations per feature), not on the physical gate depth. Alternative hardware-friendly encodings that inject fewer than 2q features per layer would simply require more encoding repetitions (as in the data re-uploading variant) to achieve the same capacity, without altering the per-dimension shot cost. Preprocessing. MNIST and Fashion-MNIST images are downscaled via average pooling to d = a2 pixels (with a chosen so that d ≤ 2q ), then normalized to [−π/2, π/2] before encoding. This normalization ensures that the Gaussian concentration argument in √ Appendix H aligns with the ϵ = κ d scaling used in Proposition 3. Data re-uploading variant. For the re-uploading architecture tested in Appendix J, the same phase-dense encoding layer appears at the input and again after 100 entangling layers within the 200-layer circuit, yielding two encoding repetitions. Each repetition re-encodes the full input x, so each feature influences the circuit output through two pathways, raising both the gradient norm and the per-shot readout variance; the two effects offset in the cost coefficient, while the PSR evaluation count per input dimension doubles (Appendix J). Appendix E. Classical baseline: experimental details This appendix provides full methodology and supplementary data for the classical neural network baseline reported in Section 4.1.3.

Measurement cost of gradient attacks on QML

39

Table E1: Matched classical CNN configurations. Channel base, parameter counts, and depth selected to match the quantum experiments at each input dimension. q

d = n2

channels (c, 2c)

classical params

quantum params (≈ 600q)

4 5 6 7 8 9 10

16 25 64 121 256 484 784

8, 16 10, 20 12, 24 14, 28 16, 32 18, 36 20, 40

1,316 2,025 2,886 3,899 5,064 6,381 7,850

2,400 3,000 3,600 4,200 4,800 5,400 6,000

Architecture. Table E1 lists the classical CNN configurations. The VGG-style architecture uses two convolutional stages (Conv–ReLU–MaxPool) followed by adaptive average pooling and a single linear classifier: Conv(1, c, 3) → ReLU → MaxPool(2) → Conv(c, 2c, 3) → ReLU → MaxPool(2) → GAP(1) → Linear(2c, C),

with c = 2q (channel base scaled by qubit count). This keeps parameter counts in the same order of magnitude as the quantum re-upload circuits. CPU timing rationale. Wall-clock timing is a proxy for the dimensionless gradient cost ratio ρ = tbwd /tfwd , a ratio of arithmetic cost rather than absolute throughput. GPU timing at batch_size=1 is dominated by kernel-launch latency (∼0.9 ms each direction), collapsing ρ to ≈ 1 and hiding the true arithmetic ratio. At batch_size=200, forward parallelization (∼0.008 ms/sample) outpaces the sequential backward pass (∼0.12 ms/sample), inflating ρ to ≈ 15. Neither reflects the O(1) FLOP ratio. Persample CPU timing avoids these GPU scheduling artifacts and yields a stable ρ ≈ 5, consistent with the Baur–Strassen bound of ≤ 5× for computing a single loss-to-input gradient [27, 28]. Training and attacks still run on GPU; only the timing measurement uses CPU. Quantum overhead extraction. The quantum ρ values in Table 4 come from the experimental data, not from the d3.00 fit. Backpropagation returns the classical attacker an exact gradient; the quantum attacker buys gradient accuracy with shots, the fit ∆L ≈ c0 (d)/s giving the shortfall of the s-shot attack from the perfect-gradient ideal. The quantum backward cost is the shot budget that brings the attack within a fixed tolerance ∆L⋆ of that ideal, the efficacy classical backpropagation reaches at its ≤ 5× inference overhead. Each qubit count’s fit (Section 4.1.1) yields a perdimension coefficient c0 (d) (units: loss · shots); reaching tolerance ∆L⋆ per component costs c0 (d)/∆L⋆ shots, so with the Parameter-Shift Rule’s two shifted evaluations per input dimension Rbwd = 2d c0 (d)/∆L⋆ . We set ∆L⋆ to one unit of attack loss, a fixed tolerance common to all d, at which the in-regime 1/s law of Section 4.1.1 is evaluated;

Measurement cost of gradient attacks on QML

40

Table E2: Classical attack success across dimensions. Full results for FGSM and C&W on both datasets and every input dimension. d

dataset

clean acc

FGSM

C&W

tfwd (ms)

tbwd (ms)

ρ

16 25 64 121 256 484 784

MNIST MNIST MNIST MNIST MNIST MNIST MNIST

92.0 95.5 97.9 98.1 96.4 94.4 93.0

50.1 50.7 21.4 15.6 22.1 32.9 54.7

100.0 99.9 99.9 98.5 89.4 86.4 87.0

0.039 0.042 0.043 0.052 0.051 0.064 0.077

0.225 0.258 0.248 0.268 0.266 0.308 0.330

5.51 5.08 6.43 5.41 5.27 4.78 4.30

16 25 64 121 256 484 784

F-MNIST F-MNIST F-MNIST F-MNIST F-MNIST F-MNIST F-MNIST

88.2 83.6 87.1 80.3 79.7 81.3 82.0

57.0 64.6 50.0 55.2 59.6 59.4 67.4

100.0 100.0 94.6 94.0 99.9 97.1 96.0

0.045 0.052 0.042 0.046 0.049 0.069 0.077

0.256 0.230 0.240 0.244 0.270 0.296 0.329

5.35 4.76 5.74 5.48 5.57 4.27 4.59

a looser tolerance lowers the quantum cost. The forward cost is Rfwd = 100. Both ∆L⋆ and Rfwd shift the quantum curve vertically and leave the scaling exponent unchanged. Classical gradient cost ratio isolated. Figure E1 shows the classical overhead across all 14 configurations with a constant fit ρ̄ = 5.2 ± 0.57 and a power-law fit yielding ρ ∝ d−0.04 ; an exponent indistinguishable from zero. MNIST Fashion-MNIST ( ): ̄ = .

10

fit:  ∝

8

− .



6 4 2 0 101

102

103

input dimension

Figure E1: Classical gradient cost ratio ρclassical (d). Dashed gray: constant fit ρ̄ = 5.2 ± 0.57. Dotted: power-law fit ρ ∝ d−0.04 , confirming O(1) scaling. Both MNIST (circles) and Fashion-MNIST (triangles) overlap, showing no dataset dependence.

Full attack success data. Table E2 reports all 14 configurations.

Measurement cost of gradient attacks on QML

41

Part II: Supporting theory and derivations Appendix F. Multi-step Carlini–Wagner attacks as stochastic gradient Langevin dynamics This appendix gives the SGLD mapping summarized in Section 3.2 and the sufficientbudget certificate it yields. The certificate is a sufficient condition for guaranteed attacker convergence to a target error ∆, derived from Raginsky et al.’s convergence theorem [37]: it upper-bounds a budget that suffices, not one that is necessary, and so serves as a modeling framework consistent with the empirical evidence of Section 4.1 rather than as a lower bound on attacker cost. Appendix F.1. The C&W–SGLD mapping The C&W attack jointly minimizes misclassification loss and perturbation size, minimize c Lmc (x + δ) + ∥δ∥22 , δ

(F.1)

where c balances the two objectives and is assumed well-tuned. Solving (F.1) by gradient descent with PSR-estimated gradients, the finite-shot update splits into the deterministic gradient and a measurement-noise term. Modeling the per-dimension shot noise as isotropic with the per-shot variance σ 2 of Section 2.1, so that its covariance is (σ 2 /s)I, the update reads p ξ ∼ N (0, I), (F.2) δt+1 = δt − η ∇δ L(δt ) + 2η/β ξ, which is exactly a gradient Langevin (SGLD) iteration once the injected-noise scale is matched to the shot noise. Equating the two noise scales gives the change of variable β=

2s , ησ 2

(F.3)

so the effective inverse temperature is linear in the per-iteration shot budget, β ∝ s. A low budget is a high-temperature, exploratory trajectory; a high budget is a lowtemperature, greedy descent. This coupling is the modeling framework used to read the iterative experiments (Section 4.1.2). Appendix F.2. Sufficient-budget certificate Raginsky et al. [37, 38] bound the expected optimality gap E[L(δK )] − L(δ ∗ ) of the gradient Langevin iterate under three assumptions on the loss δ 7→ L(δ): M -smoothness, R 2 (m, b)-dissipativity, and an initialization law with finite κ0 = log Rd e∥δ∥ p0 (δ) dδ. The C&W loss (F.1) with p = 2 satisfies all three for a canonical PQC/softmax/C&W model. The quantum layer is smooth because unitary encoding e−iHj xj has input derivatives bounded by the encoding-Hamiltonian norms ∥Hj ∥ [60] (the property that also underlies the trace-distance robustness guarantee of [13]), and the ∥δ∥22 regularizer

Measurement cost of gradient attacks on QML

42

supplies dissipativity; the initialization condition holds for a point mass at δ = 0 or any √ N (0, σ02 Id ) with σ0 < 1/ 2. Verifying these for the model yields d-dependent constants M = O(cd + 1), b = O(c2 d2 ), B = O(c), and gradient-noise variance σg2 = O(c2 σΣ2 d/s), with m = 1 and κ0 dimension-independent, where the bounded measurement-covariance condition ∥Σv ∥ ≤ σΣ2 keeps the observable norm O(1) under unitary conjugation. Combining the bound with the change of variable (F.3) translates the convergence requirement into a per-iteration condition s ≥ O((d/∆) log(d/∆)) ησ 2 , the theoretical analog of the empirical sweet spot s∗ (d), and, with the iteration count the same argument requires, a total budget  5 ! d16 log15 (d/∆) log(d/∆) − log λ′∗ (d) ησ 2 , (F.4) R = Kds = O ∆19 λ′∗ (d) where λ′∗ (d) is the uniform spectral gap of the Langevin diffusion at the error-matching temperature. Two points make this informative despite being only sufficient. First, Raginsky’s bound is monotone in each of M, b, B, 1/m, and the verified QML constants above grow polynomially in d, so substituting them can only enlarge the budget: the exponent 16 obtained under d-independent constants is a lower estimate of the certified degree. Second, the spectral gap satisfies λ∗ ≳ poly(d, β)−1 e−β∆F in multi-well landscapes, and this exponential-in-β factor drives the high degree once β is set to its error-matching value; for landscapes with favorable geometry λ∗ is far larger, which is why the empirical Rcrit (d) of Section 4.1.2 sits far below the worst-case certificate. The certificate is thus loose by construction and is not a lower bound on attacker cost; it establishes only that current finite-shot convergence theory grants an iterative attacker no guarantee of beating the single-step scaling within any feasible budget. What the mapping contributes instead is the β ∝ s modeling framework, which predicts the observed bias–variance trade-off and the sweet spot s∗ (d) (Section 4.1.2). Appendix G. Supporting derivations and proofs Appendix G.1. Gradient-estimate covariance bookkeeping This expands the covariance structure summarized after Eq. (7). With PSR variance V[Jˆij ] = Θ(∆2Gj /sj ), the commuting case (shared bitstrings at fixed shift index j, disjoint shot pools across different j) gives Cov(Jˆij , Jˆi′ j ′ ) = V[Jˆij ] Cov(Jˆij , Jˆi′ j ′ ) ̸= 0

if i′ = i, j ′ = j,

(G.1)

if j ′ = j, i′ ̸= i,

(G.2)

Cov(Jˆij , Jˆi′ j ′ ) = 0

if j ′ ̸= j.

(G.3)

and the non-commuting case makes all partial derivatives independent. Writing Viv = ˆ L is V(Jˆiv ), the full vectorized covariance of Ĝ = JU JJ   Cov vec(Ĝ) = (JL⊤ ⊗ JU ) diag(vec(V )) (JL⊤ ⊗ JU )⊤ , which for JL = Id reduces entrywise to the Hadamard-square weighting V[Ĝ·v ] = JU⊙2 V·v .

Measurement cost of gradient attacks on QML

43

Appendix G.2. Proofs for the cost-dominance and correlated-noise results These complete the statements in Sections 2.4 and 3.1.2. Proof of Proposition 1. By Taylor expansion (Assumption 4), JU (ŷk ) − JU (yk ) ≈ HU (ŷk − yk ) to leading order. The readout error ŷk − yk is zero-mean Gaussian with covariance Σy = Θ(1/m) per observable (standard shot-noise scaling). For the Gaussian linear transformation, V[HU (ŷk − yk )] = HU Σy HU⊤ = Θ(1/m).

Proof of Proposition 2. Forward-pass estimation requires dout observable measurements, 2 2 each needing m = Θ(1/σfwd ) shots to achieve target variance σfwd . Total forward shots: 2 Rfwd = Θ(dout /σfwd ). Backward-pass Jacobian estimation via PSR requires 2din dout circuit evaluations (one for each partial derivative at two shifted parameter values), each needing s = 2 2 Θ(1/σbwd ) shots. Total backward shots: Rbwd = Θ(din dout /σbwd ). The ratio is   2 Rbwd σfwd = Θ din 2 . Rfwd σbwd 2 2 For comparable precision targets σfwd = Θ(σbwd ), backward cost dominates by a factor of din .

Proof of Corollary 1. Immediate from Proposition 2: as din → ∞ with fixed dout , the ratio Rbwd /Rfwd diverges linearly. Proof of Corollary 2. We relax the independence assumption and allow arbitrary correlations in the gradient error. The following derivation requires only that the error has a well-defined covariance matrix Σ with finite trace; no Gaussianity or small-noise assumption is needed. For concreteness, write the one-shot gradient error model with covariance Σ and average s shots per input dimension: ĝ = g ∗ + ξ,

ξ ∼ N (0, Σ/s).

(G.4)

Using the deterministic geometry bound cos α ≥ (1 − ρ)/(1 + ρ) ≥ 1 − 2ρ with ρ = ∥ξ∥/∥g ∗ ∥ and Cauchy–Schwarz, we obtain the correlation-agnostic expected alignment guarantee s p E[∥ξ∥2 ] tr Σ E[cos α] ≥ 1 − 2 = 1−2 . (G.5) ∗ ∥g ∥ s ∥g ∗ ∥2 Only Σ ⪰ 0 with finite trace p is required p for this defensive effect to manifest; a one2 line justification is E ∥ξ∥ ≤ E ∥ξ∥ = tr Σ/s by Cauchy–Schwarz, substituted into cos α ≥ 1 − 2∥ξ∥/∥g ∗ ∥.

Measurement cost of gradient attacks on QML

44

For single-step FGSM under Assumption 1, the expected loss surplus relative to the ideal direction obeys r  ∗  tr Σ . (G.6) E[∆L] = E ϵ∥g ∥(1 − cos α) ≤ 2ϵ s Since the right-hand side is decreasing in s, setting it equal to ∆ and solving shows that the bound E[∆L] ≤ ∆ holds for every s ≥ smin (∆) = 4ϵ2 tr Σ/∆2 ; thus smin is the minimum sufficient per-dimension budget, and the dimension-explicit form follows from tr Σ = Θ(d). Appendix G.3. Single-step success-probability route This derivation underlies the tail guarantee stated at the end of Section 3.1.3; the geometry is shown in Fig. 1. First, we consider a one-step gradient-based attack that saturates the perturbation limit ϵ in one step by letting δ = −ϵĝ. Suppose that we consider the adversarial error rate, the percentage of incorrectly classified samples in the testing data, as the benchmark criterion for adversarial performance. Our performance will depend on both the model and the data structure. We shall first consider a single data point near the model boundary and measure the probability of the attack successfully perturbing the sample to cross the model boundary, as shown in Fig. 1. Here, we adopt the assumption 1 and 2 from the previous section and denote the distance from a sample to the linear boundary as lx . Under these assumptions, and conditioning on an attackable sample with lx ≤ ϵ (otherwise no perturbation of budget ϵ can reach the boundary), we notice that only if the angle α between the estimated gradient and the true gradient is smaller than τ = arccos(lx /ϵ), the perturbed sample can cross the boundary and become an adversarial sample. To further evaluate the robustness caused by the uncertainty of the gradient measurement during attacks, we consider the probability that the measurement-based attack δ = −ϵĝ is successful. A successful attack will perturb the sample across the nearest model boundary, that is, α ≤ τ . As established above, the normalized gradient estimate ĝn follows a von Mises-Fisher distribution with concentration parameter κvMF ≈ s∥g ∗ ∥2 /σ 2 (cf. Equation 9). Thus, the probability of the attack being successful P (∥ĝn − gn∗ ∥ < τ ) with some threshold τ is shown to be   sτ 2 ∥g ∗ ∥2 Z τ γ d−1 , 2 2 2σ
P (∥ĝn − gn∗ ∥ < τ ) = fr (r) dr = , (G.7) d−1 Γ 2 0 where γ(·, ·) is the incomplete Gamma function and Γ(·) is the Gamma function [61]. If we assume that we are processing high-dimensional data so that d is large, the probability will be further simplified via vMF angular concentration of the normalized

Measurement cost of gradient attacks on QML gradient estimate (and the small-angle approximation 1 − cos τ ≈ τ 2 /2) to  √ √ √  2 s τ ∥g ∗ ∥ − σ d  , P (∥ĝn − gn∗ ∥ < τ ) ≈ Φ σ

45

(G.8)

√ where Φ(·) is the CDF of the standard normal distribution and the factor 2 p arises from the CLT approximation of Gamma((d−1)/2, 1), whose standard deviation is (d−1)/2. The result reveals a key resource-dimension trade-off: to maintain the same attack success probability as dimension d increases, the attacker must proportionally increase the shots per dimension s. An important implication of this result is that maintaining a fixed attack success probability as the dimension d increases requires a proportional increase in the number of shots per input dimension s. √ √ s τ ∥g ∗ ∥ − d σ = Constant . (G.9) Consider the success rate threshold of 50%. We obtain the following new success-rate bound. Proposition 4 (FGSM shot budget for 50% success). Under Assumptions 1, 2, and 3, with ∥g ∗ ∥ = Θ(1) (constant relative geometry), consider a sample x in d dimensions. To maintain a 50% success rate under an ℓ2 FGSM attack, the shots per dimension must scale as   d s=O 2 , (G.10) τ where the tolerance angle satisfies cos τ = lx /ϵ (with lx ≤ ϵ for the sample to be attackable) and lx is the shortest distance from x to the decision boundary. Now, we combine (G.10) and the assumptions that σ and τ do not change significantly for data with higher dimensions. We found that the shots per dimension s = O(d), and the total number of shots R for all dimensions scale quadratically with the dimension d, i.e., R = O(d2 ) in the most optimistic attacker scenario (constant relative geometry). For future quantum models, this quadratic overhead can become an important limiting factor for measurement-based attacks, making reliable boundary crossing increasingly resource-intensive in high dimensions. Appendix H. Dimension scaling of the ℓ2 perturbation budget √ This appendix justifies the convention ϵ = κ d used throughout the scaling experiments for the adversarial ℓ2 budget (the single-dimension hardware demonstration of Section 4.2 fixes ϵ at one budget instead). The scaling has two complementary readings. (i) Per-coordinate A uniform per-coordinate bound |δi | ≤ κ √ imperceptibility. √ directly implies ∥δ∥2 ≤ κ d, so ϵ = κ d is the ℓ2 envelope of any attack whose per-pixel magnitude is capped at the imperceptibility scale κ. (ii) Detectability-matched scale. An

Measurement cost of gradient attacks on QML

46

adversarial perturbation whose ℓ2 norm matches the typical ℓ2 norm of natural Gaussian input noise at scale √ σ = κ is statistically indistinguishable from benign noise under an ℓ2 detector, so ϵ = κ d is the largest budget that remains below the natural-noise floor. The second reading is quantified by the standard χ2d concentration, which we include for completeness. Assume image (or feature) noise is i.i.d. Gaussian across dimensions: η ∼ N (0, σ 2 Id ). Then ∥η∥22 /σ 2 ∼ χ2d . Standard concentration for the chi-square law yields, for all t ≥ 0 (see, e.g., [62, 63]): √ √
Pr ∥η∥2 ≥ σ( d + 2t) ≤ e−t , (H.1) √ √
Pr ∥η∥2 ≤ σ( d − 2t) ≤ e−t . (H.2) Equivalently, with probability at least 1 − δ, the noise ℓ2 norm lies in the band p p √ √

σ d − 2 log(1/δ) ≤ ∥η∥2 ≤ σ d + 2 log(1/δ) . √ Thus, an ℓ2 perturbation whose magnitude scales as ϵ = κ d matches the typical Gaussian growth and keeps a fixed tail probability when κ is chosen relative to σ (e.g., p
take κ = σ for median scale, or κ = σ 1 + 2 log(1/δ)/d for a (1 − δ) upper-quantile). In particular, thresholds of the form p √
ϵflag (δ) = σ d + 2 log(1/δ) flag ℓ2 noise levels that√ are unlikely under N (0, σ 2 Id ) at significance δ. This justifies the concise heuristic ϵ = κ d in the main text and provides a principled way to tie κ to σ and a desired false-alarm rate δ. Part III: Robustness checks Appendix I. Supporting figures for the simulation results This appendix collects the secondary figures and the landscape-curvature probe supporting the single-step and multi-step simulation results of Section 4.1: the gradientnorm-folded coefficient, the local-linearity (landscape-factor) measurement, and the multi-step C&W shot-budget sweep. The Fashion-MNIST shot-scaling waterfall is now shown alongside MNIST in Fig. 2 (panels c, d). Probing local linearity at the attack scale. Assumption 1 treats the loss as linear over the ϵ-step; the landscape factor quantifies the departure. For each input we step a distance ˆ ϵ along d(α) = cos α û∗ + sin α t̂, rotating from the gradient direction û∗ (α = 0) toward a random orthogonal direction t̂, and record the excess over the first-order prediction, ˆ ∆(α) = L(x + ϵd(α)) − L(x) − ϵ∥g ∗ ∥ cos α; here L is the exact (noiseless) loss, so the scan isolates landscape geometry rather than shot noise. We sweep α over a uniform grid on [0, 75◦ ] and average ∆(α) over eight random transverse directions t̂ per sample.

Measurement cost of gradient attacks on QML .

MNIST (per-sample) ∝ F-MNIST (aggregate) ∝

⋅ ‖ ‖ (normalised to =

)

geometric baseline ∝

47

.

.

102

101

100 102

input dimension

Figure I1: Gradient-norm-independent coefficient. The combination dL · ∥g ∗ ∥ of Eq. (15) (the 1/s loss-gap coefficient with the measured gradient norm folded back in) versus input dimension d, normalised to d=16, against the geometric d3/2 baseline (dotted). MNIST (per-sample, line-scan ζi ): d1.46 ; Fashion-MNIST (aggregate Bq · ⟨∥g ∗ ∥⟩): d1.42 . Folding ∥g ∗ ∥ back into the coefficient recovers the shot-noise baseline on both datasets, leaving only the mild landscape factor ζ(d). A linear landscape gives ∆ ≡ 0, and the on-axis value defines ζ = 1 + ∆(0)/ϵ∥g ∗ ∥ per sample. Measured at every dimension (Fig. I2), ζ holds near unity through d = 121 and falls monotonically to 0.83 at d = 784. This high-d curvature favors the attacker: the loss is concave along the gradient at the ϵ-scale and flatter transversely (the deficit ∆(α) is most negative on-axis and relaxes toward zero off-axis), so a shot-noisy attack that tilts off the true gradient lands in a less-saturated direction and loses less loss-rise than the linear prediction. Curvature thus broadens the cone of effective attack directions and lowers the shot-noise penalty (ζ < 1), a small, dimension-growing advantage rather than a cost. Aggregate bracket on the single-step exponent. The directly fitted coefficient d2.00 (MNIST) factors as the per-sample geometry, d1.46 , times the gradient norm, which enters with effective exponent 0.54. The aggregate reference d2.23 folds the cohort-mean inverse norm 1/⟨∥g ∗ ∥⟩ ∝ d0.73 into the bare d3/2 geometry and overstates the norm contribution: σ 2 and ∥g ∗ ∥ are positively correlated across samples (+0.75), so low-norm samples carry low variance and the per-sample ratio σ 2 /∥g ∗ ∥ grows more slowly than 1/⟨∥g ∗ ∥⟩. The 0.23 separation is this norm-exponent damping (0.73 → 0.54, contributing 0.19) plus the 0.04 offset between the bare d3/2 and the measured d1.46 geometry (ζ and finite-window extraction), so d2.23 brackets the per-sample law d2.00 from above, as an aggregated estimate should.

Measurement cost of gradient attacks on QML (b)

0.05

0.06

0.00

0.04

−0.05 = = = = = = =

−0.10

−0.15

0

10

20

30

40

50

transverse angle  (deg)

60

70

() / ‖ ‖

() / ‖ ‖ (deviation from linear)

(a)

48

0.02

0.00 near boundary (margin ≤ . far (margin > .

−0.02 0

10

20

30

40

, =

)

50

60

transverse angle  (deg)

, =

)

70

Figure I2: Landscape non-linearity at the attack scale. (a) Median transverse line-scan ∆(α)/ϵ∥g ∗ ∥ versus tilt angle α for d = 16 → 784: the deviation from the firstorder prediction is flat at low d and grows strongly negative along the attack direction as d increases; the α=0 intercept equals ζ − 1 (+0.05 → −0.17). (b) Splitting samples by distance to the decision boundary at d = 121: far-from-boundary samples carry the larger transverse deviation; the split washes out by d = 784, where the non-linearity is a global property of the landscape.

Appendix J. Robustness of a different architecture: data re-uploading This appendix provides a detailed experimental comparison that supports the architectural robustness paragraph in Section 4.1.1. We repeat the (q, s) sweep from Section 4.1.1, under the same grid protocol, for a data re-uploading variant of that circuit, which re-encodes the input at mid-depth rather than encoding once at the input: the angle-encoding layer appears at the input and again after 100 entangling layers, two encoding repetitions within a fixed 200-layer depth. We fix the dataset to MNIST and vary q ∈ {4, 5, 6, 7}, so that the only experimental difference is the circuit structure itself, isolating how the architecture-dependent Jacobian factors JL and JU in (7) shift variance constants. The re-uploading model’s own measured gradient norm (∥g ∗ ∥ ∝ d−0.81 , 1.5–1.8× the single-upload values) and readout variance (σ 2 ≈ 4.7, 1.4– 1.8× the single-upload σ 2 ≈ 3, consistent with variance accumulating over the two encoding blocks) set its critical counts s⋆ (d), so the relative budgets h = s/s⋆ ∈ [0.3, 12] are matched between the two architectures. Figure J1 presents the re-uploading curves alongside Fig. 2 for direct comparison. The qualitative behavior is strikingly similar: both architectures exhibit the characteristic 1/s decay within each qubit count, precisely the signature predicted by Proposition 3. To quantify this similarity, we apply the same in-regime through-origin fitting procedure from Section 4.1.1. Figure J2 overlays the fitted coefficients c0 for both

Measurement cost of gradient attacks on QML

49

3 2 1 0

Acc. gap (pp)

4

−1 7 100

6 1k

Shots

10k

5 100k

4

Figure I3: C&W shot-budget sweet spot. Signed accuracy gap of the finite-shot attack to the exact-shot (s → ∞) attack (percentage points, pp) versus shots per dimension s (log scale) and model size q; the grey line is the exact-shot reference. Below it, finite shots make the attack stronger than an exact gradient (the SGLD sweet spot; see text). Markers are means over five shot-noise realizations on the full test set; bars are ±1 SEM. architectures on log–log axes over the matched range d ∈ {16, 25, 64, 121}. Two key observations emerge. First, the exponents are statistically indistinguishable: d1.99 (R2 = 0.991) for re-uploading versus d1.96 (R2 = 0.997) for single-upload on the matching rungs. Second, the coefficients coincide (per-dimension pre-factor ratio 0.89– 1.09, geometric mean 0.98): the second encoding pathway raises the gradient norm and the per-shot readout variance by nearly identical factors (≈ 1.6× each), and the two cancel in the coefficient rule c0 ∝ σ 2 /∥g ∗ ∥. The architectural cost surfaces elsewhere: each input component appears in both encoding blocks, so one PSR gradient consumes four shifted circuit evaluations per dimension instead of two, doubling the total shot budget per gradient at equal s without touching the coefficient or the exponent. These results directly corroborate Section 4.1.1: the super-linear coefficient growth measured on single-upload MNIST reappears on the re-uploading variant within fitting uncertainty, and together with the Fashion-MNIST exponent (Section 4.1.1) we have three independent configurations all exhibiting growth far above the d1.5 theoretical floor. The coefficient coincidence is itself informative: it confirms the structure c0 ∝ σ 2 /∥g ∗ ∥ on an independent architecture, since both measured ingredients moved by a common factor and the coefficient did not move. The consistency across datasets and architectures strongly suggests that the scaling law is an intrinsic property of PSR-based gradient estimation on quantum circuits. For practitioners, this implies that more expressive

Measurement cost of gradient attacks on QML (a)

50

(b)

0.12 0.08 0.06 0.04 0.02 0.00

7 10

7

6 100

1k

Shots

100k

6

10

5 10k

||

0.10

||

0.175 0.150 0.125 0.100 0.075 0.050 0.025 0.000

100

1k

Shots

4

5 10k

100k

4

in-regime / coefficient

(loss ⋅ shots)

Figure J1: Re-uploading ansatz: FGSM waterfall on MNIST. Same convention as Fig. 2: (a) accuracy and (b) loss shortfall from the perfect-gradient attack versus shot budget (log scale) for q ∈ {4, 5, 6, 7}. The re-uploading architecture qualitatively mirrors the single-upload baseline, confirming the 1/s decay persists across circuit families. 102

single-upload

∝

re-uploading

∝

. .

(

= .

)

(

= .

)

101

100 102

input dimension

Figure J2: Architectural robustness: re-uploading vs. single-upload coefficient scaling. Log–log plot of the in-regime coefficients c0 versus input dimension d over the matched range d ∈ {16, 25, 64, 121}, comparing re-uploading (orange, ∝ d1.99 ) to singleupload (blue, ∝ d1.96 ; cf. Fig. 3). The exponents are statistically indistinguishable and the pre-factors coincide (geometric-mean ratio 0.98): the re-uploading circuit’s larger readout variance is offset by its larger gradient norm in c0 ∝ σ 2 /∥g ∗ ∥. Lines show leastsquares power-law fits.

circuit families may multiply the per-gradient evaluation count, but the polynomial explosion in total budget with dimension persists regardless of ansatz.

Measurement cost of gradient attacks on QML (a)

(b) 80

PSR FD = .

75

−0.90

FD = . FD = . FD = /

70 65

−0.95 −1.00

−

Adv. accuracy (%)

51

60

−1.05 −1.10

55

−1.15

50

−1.20

45 101

102

Shots

101

102

Shots

Figure K1: Estimator comparison under data re-uploading (q = 6). (a) Adversarial accuracy (%) and (b) negative adversarial loss −Ladv , both versus shots s, for PSR and FD at several step sizes h under matched total shot budgets.

Appendix K. Estimator comparison: parameter-shift versus finite differences We assess how the choice of gradient estimator interacts with the shot budget and the variance model in (7). Building on the baseline architecture at q = 6 qubits, we contrast PSR, which is unbiased but potentially higher-variance at low s, with a two-point finitedifference (FD) estimator with step size h. In FD, we treat the quantum layer as a black box and choose h ≪ 1 to avoid parameter clipping from periodic gate ranges. We enforce identical total shot budgets across methods so that variance-bias trade-offs, rather than raw sampling volume, drive the outcome; analytically, this isolates the shift from the unbiased PSR covariance in Assumption 2 to the biased estimator that perturbs the mean term E[Ĝ] = JU µ JL from Section 2.3. To visualize these effects, we report two-panel summaries for data re-uploading and single-upload models. In each figure, the left panel plots adversarial loss versus shots per dimension s, and the right panel plots post-attack accuracy versus s, comparing PSR with FD at several step sizes h. Figure K1 covers the data re-uploading case; Figure K2 covers the single-upload case. Across the shared (s, h) sweep, the re-uploading architecture (Fig. K1) exhibits a small low-shot crossover: FD’s reduced variance can outweigh its O(h2 ) bias when s is tiny, after which PSR’s unbiased gradients dominate as κvMF ∝ s∥g ∗ ∥2 /σ 2 increases per (9). For the single-upload variant (Fig. K2), PSR leads for all s; here, the FD surrogate provides no advantage because the analytic PSR effectively acts as a large-step finite difference without incurring bias. Both behaviors are consistent with Proposition 3 and with the covariance structure in (7), which predicts that reducing estimator bias (PSR) is the dominant lever once shot noise shrinks below the true gradient magnitude. Taken together, the results indicate that the choice of estimator primarily affects constants and low-shot transients. Under moderate and large shot budgets, PSR’s unbiasedness yields superior alignment with the true gradient and better attack efficacy

Measurement cost of gradient attacks on QML (a)

(b) −1.24

60 55

−1.26

PSR FD = . FD = .

50

−1.28

−

Adv. accuracy (%)

52

FD = . FD = .

45

−1.30

40

−1.32

35

−1.34 101

100

Shots

101

100

Shots

Figure K2: Estimator comparison under single upload (q = 6). (a) Adversarial accuracy (%) and (b) negative adversarial loss −Ladv , both versus shots s, for PSR and FD at several step sizes h under matched total shot budgets.

at fixed R = ds. In the limit of a large number of shots and low variance (Assumption 3), the attacker will prefer the unbiased PSR method. Thus, the inclusion of FD as a gradient estimator does not affect the overall scaling behavior of the attack, and the fundamental shot-dimension law holds, as at least a quadratically increasing amount of shot resources, R = ds, is required to maintain constant adversarial performance as the data/model dimension d increases. Takeaway. Estimator choice changes constants and low-shot crossovers but not the core scaling: PSR dominates at moderate/large s because it satisfies the unbiased, shotlimited model assumed in Assumptions 2–3, while FD can transiently help at tiny s via bias-variance trade-offs that momentarily shrink the covariance in (7). Appendix L. Zero-order gradient estimation under finite shot budgets The bounds of Section 3.1 assume an unbiased, first-order estimator, the parameter-shift rule. A natural objection is that a zero-order estimator such as SPSA (simultaneousperturbation stochastic approximation) sidesteps the Θ(d) circuit count by probing the loss along one random direction, using two circuit evaluations regardless of d. Classically this √ saving is real: zero-order estimators built from random directions cost only a d factor over first-order methods [39, 41], with matching information-theoretic lower bounds under fixed-smoothness assumptions [64]. Whether the saving survives the finiteshot, high-curvature regime of expressive quantum circuits is the question this appendix frames. Notation. Throughout this appendix s denotes shots per circuit evaluation, matching the per-evaluation count s0 of Section 2.1; the paper’s per-dimension convention follows from spaper = 2s for commuting-observable PSR.

Measurement cost of gradient attacks on QML Method PSR SPSA

Circuit Evals 2d 2

53

Gradient Variance Bias 2 Θ(σ /s) per component 0 2 2 Θ(dσ /(c s)) total O(c2 )

Table L1: PSR vs. SPSA under finite shots. Comparison of circuit count, gradient variance, and bias.

The SPSA gradient estimate [65, 33] is ˆ SPSA f (θ) = f (θ + c∆) − f (θ − c∆) ∆ , ∇ 2c

∆ ∼ Rademacherd ,

(L.1)

with finite-difference step c > 0. It uses two evaluations independent of d, but each is a quantum expectation value read from finitely many shots, so fˆ(θ) ∼ N (f (θ), σ 2 /s) and the shot noise survives; the random projection ∆ moves it into the estimator’s variance and spreads it across all d coordinates,  2   2 dσ dσ 2 ˆ Var[∇SPSA ] = E∆ 2 + O(c ) = O 2 + bias2 , (L.2) cs cs ˆ SPSA ] − ∇f = which still scales as d/s. The finite-difference step also carries a bias E[∇ O(c2 ∥∇2 f ∥) [65]. Table L1 collects the trade-off. The two knobs pull against each other: bias forces c small and variance forces s large, so reaching a fixed gradient accuracy costs s = Θ(d/c2 ) shots and the total budget climbs back toward PSR’s Θ(ds). √ In a low-curvature loss the bias term is mild and the trade can still net the classical d advantage [41]; in the high-curvature regime characteristic of expressive circuits the bias grows with ∥∇2 f ∥ and that advantage is no longer guaranteed. The only adversarial-QML study to use hybrid (zero-order) gradients, by Majumder et al. [66], reports feasibility on a single problem instance without shotbudget or dimension-scaling analysis, so the question stays empirically open. Our scaling law fixes the exponent for the unbiased regime (Section 3.1); whether a biased zero-order estimator can lower it for expressive, classically-hard models, and how the optimal step c∗ (d, s) trades bias against variance, is left to future work.

Measurement cost of gradient attacks on QML

54

[1] Goodfellow I J, Shlens J and Szegedy C 2014 3rd International Conference on Learning Representations, ICLR 2015 - Conference Track Proceedings Publisher: International Conference on Learning Representations, ICLR URL https://arxiv.org/abs/1412.6572v3 [2] Carlini N and Wagner D 2017 Proceedings - IEEE Symposium on Security and Privacy 39–57 ISSN 10816011 iSBN: 9781509055326 Publisher: Institute of Electrical and Electronics Engineers Inc. URL https://arxiv.org/abs/1608.04644v2 [3] Szegedy C, Zaremba W, Sutskever I, Bruna J, Erhan D, Goodfellow I and Fergus R 2013 Intriguing properties of neural networks ICLR [4] Melnikov A, Kordzanganeh M, Alodjants A and Lee R K 2023 Advances in Physics: X 8 2165452 ISSN 23746149 publisher: Taylor & Francis URL https://www.tandfonline.com/doi/abs/10. 1080/23746149.2023.2165452 [5] Liu N and Wittek P 2020 Physical Review A 101 062331 ISSN 24699934 publisher: American Physical Society URL https://journals.aps.org/pra/abstract/10.1103/PhysRevA.101. 062331 [6] Liao H, Convy I, Huggins W J and Whaley K B 2021 Physical Review A 103 042427 ISSN 24699934 publisher: American Physical Society URL https://journals.aps.org/pra/abstract/10. 1103/PhysRevA.103.042427 [7] Mahloujifar S, Diochnos D I and Mahmoody M 2018 33rd AAAI Conference on Artificial Intelligence, AAAI 2019, 31st Innovative Applications of Artificial Intelligence Conference, IAAI 2019 and the 9th AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019 4536–4543 ISSN 2159-5399 iSBN: 9781577358091 Publisher: AAAI Press URL https://arxiv.org/abs/1809.03063v2 [8] West M T, Erfani S M, Leckie C, Sevior M, Hollenberg L C L and Usman M 2023 Physical Review Research 5 023186 ISSN 26431564 publisher: American Physical Society (APS) URL https://journals.aps.org/prresearch/abstract/10.1103/PhysRevResearch.5.023186 [9] Du Y, Hsieh M H, Liu T, Tao D and Liu N 2021 Physical Review Research 3 023153 publisher: American Physical Society URL https://link.aps.org/doi/10.1103/PhysRevResearch.3. 023153 [10] Kundu S, Choudhury N, Das S, Raha A and Basu K 2024 QNAD: Quantum Noise Injection for Adversarial Defense in Deep Neural Networks 2024 IEEE International Symposium on Hardware Oriented Security and Trust (HOST) pp 1–11 iSSN: 2765-8406 URL https://ieeexplore.ieee. org/abstract/document/10545406 [11] Ahmed T, Kashif M, Marchisio A and Shafique M 2025 Scientific Reports 15 33654 ISSN 20452322 publisher: Nature Publishing Group URL https://www.nature.com/articles/s41598025-17769-6 [12] Zhang H F, Chen Z Y, Wang P, Guo L L, Wang T L, Yang X Y, Zhao R Z, Zhao Z A, Zhang S, Du L, Tao H R, Jia Z L, Kong W C, Liu H Y, Vasilakos A V, Yang Y, Wu Y C, Guan J, Duan P and Guo G P 2026 Science China Physics, Mechanics & Astronomy 69 arXiv:2505.16714 [quant-ph] URL http://arxiv.org/abs/2505.16714 [13] Dowling N, West M T, Southwell A, Nakhl A C, Sevior M, Usman M and Modi K 2026 npj Quantum Information 12 16 URL https://doi.org/10.1038/s41534-025-01129-3 [14] Mitarai K, Negoro M, Kitagawa M and Fujii K 2018 Physical Review A 98 032309 ISSN 2469-9926, 2469-9934 URL https://link.aps.org/doi/10.1103/PhysRevA.98.032309 [15] Schuld M, Bergholm V, Gogolin C, Izaac J and Killoran N 2019 Physical Review A 99 032331 ISSN 2469-9926, 2469-9934 URL https://link.aps.org/doi/10.1103/PhysRevA.99.032331 [16] Helstrom C W 1969 Journal of Statistical Physics 1 231–252 ISSN 1572-9613 URL https: //doi.org/10.1007/BF01007479 [17] Braunstein S L and Caves C M 1994 Physical Review Letters 72 3439–3443 publisher: American Physical Society URL https://link.aps.org/doi/10.1103/PhysRevLett.72.3439 [18] Scriva G, Astrakhantsev N, Pilati S and Mazzola G 2024 Physical Review A 109 032408 arXiv:2308.00044

Measurement cost of gradient attacks on QML

55

[19] Kübler J M, Arrasmith A, Cincio L and Coles P J 2020 Quantum 4 263 publisher: Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften URL https://quantumjournal.org/papers/q-2020-05-11-263/ [20] Bittel L, Watty J and Kliesch M 2022 Fast gradient estimation for variational quantum algorithms arXiv:2210.06484 [quant-ph] URL http://arxiv.org/abs/2210.06484 [21] Ito K and Fujii K 2023 SantaQlaus: A resource-efficient method to leverage quantum shotnoise for optimization of variational quantum algorithms arXiv:2312.15791 [quant-ph] URL http://arxiv.org/abs/2312.15791 [22] Kreplin D A and Roth M 2024 Quantum 8 1385 publisher: Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften URL https://quantum-journal.org/papers/q2024-06-25-1385/ [23] Ma Z, Gokhale P, Zheng T X, Zhou S, Yu X, Jiang L, Maurer P and Chong F T 2021 Adaptive Circuit Learning for Quantum Metrology 2021 IEEE International Conference on Quantum Computing and Engineering (QCE) pp 419–430 URL https://ieeexplore.ieee. org/document/9605341/ [24] Athalye A, Carlini N and Wagner D 2018 Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples Proceedings of the 35th International Conference on Machine Learning (PMLR) pp 274–283 iSSN: 2640-3498 URL https : / / proceedings.mlr.press/v80/athalye18a.html [25] Cohen J M, Rosenfeld E and Kolter J Z 2019 Certified adversarial robustness via randomized smoothing Proceedings of the 36th International Conference on Machine Learning (ICML) (Proceedings of Machine Learning Research vol 97) (PMLR) pp 1310–1320 [26] Wong E and Kolter J Z 2018 Provable defenses against adversarial examples via the convex outer adversarial polytope Proceedings of the 35th International Conference on Machine Learning (ICML) (Proceedings of Machine Learning Research vol 80) (PMLR) pp 5286–5295 arXiv:1711.00851 [27] Baur W and Strassen V 1983 Theoretical Computer Science 22 317–330 [28] Griewank A and Walther A 2008 Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation 2nd ed (SIAM) [29] Chinzei K, Yamano S, Tran Q H, Endo Y and Oshima H 2025 npj Quantum Information 11 79 arXiv:2406.18316 [30] Wierichs D, Izaac J, Wang C and Lin C Y Y 2022 Quantum 6 677 URL https://quantumjournal.org/papers/q-2022-03-30-677/ [31] Banchi L, Branford D and Waghela C 2026 Quantum Science and Technology Accepted manuscript; arXiv:2510.05289 [quant-ph] URL https://doi.org/10.1088/2058-9565/ae73ad [32] Periyasamy M, Plinge A, Mutschler C, Scherer D D and Mauerer W 2024 Guided-SPSA: Simultaneous Perturbation Stochastic Approximation Assisted by the Parameter Shift Rule 2024 IEEE International Conference on Quantum Computing and Engineering (QCE) vol 01 pp 1504–1515 URL https://ieeexplore.ieee.org/document/10821406/ [33] Hoffmann T and Brown D 2022 Gradient Estimation with Constant Scaling for Hybrid Quantum Machine Learning arXiv:2211.13981 [quant-ph] URL http://arxiv.org/abs/2211.13981 [34] Heidari M, Naved M A, Honjani Z, Xie W, Grama A J and Szpankowski W 2024 Quantum Shadow Gradient Descent for Variational Quantum Algorithms arXiv:2310.06935 [quant-ph] URL http://arxiv.org/abs/2310.06935 [35] Lockwood O 2022 An Empirical Review of Optimization Techniques for Quantum Variational Circuits arXiv:2202.01389 [quant-ph] URL http://arxiv.org/abs/2202.01389 [36] Biggio B, Corona I, Maiorca D, Nelson B, Šrndić N, Laskov P, Giacinto G and Roli F 2013 Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 8190 LNAI 387–402 ISSN 03029743 iSBN: 9783642409936 Publisher: Springer, Berlin, Heidelberg URL https://link.springer.com/chapter/10.1007/ 978-3-642-40994-3_25

Measurement cost of gradient attacks on QML

56

[37] Raginsky M, Rakhlin A and Telgarsky M 2017 Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis Proceedings of the 2017 Conference on Learning Theory (PMLR) pp 1674–1703 iSSN: 2640-3498 URL https://proceedings.mlr.press/v65/ raginsky17a.html [38] Xu P, Chen J, Zou D and Gu Q 2018 Global Convergence of Langevin Dynamics Based Algorithms for Nonconvex Optimization Advances in Neural Information Processing Systems 31 (NeurIPS 2018) (arXiv) arXiv:1707.06618 [stat] URL http://arxiv.org/abs/1707.06618 [39] Nesterov Y and Spokoiny V 2017 Foundations of Computational Mathematics 17 527–566 [40] Jamieson K G, Nowak R D and Recht B 2012 Query complexity of derivative-free optimization Advances in Neural Information Processing Systems (NeurIPS) vol 25 pp 2672–2680 arXiv:1209.2434 [41] Duchi J C, Jordan M I, Wainwright M J and Wibisono A 2015 IEEE Transactions on Information Theory 61 2788–2806 [42] Pérez-Salinas A, Cervera-Lierta A, Gil-Fuster E and Latorre J I 2020 Quantum 4 226 (Preprint 1907.02085) URL https://quantum-journal.org/papers/q-2020-02-06-226/ [43] Havlíček V, Córcoles A D, Temme K, Harrow A W, Kandala A, Chow J M and Gambetta J M 2019 Nature 2019 567:7747 567 209–212 ISSN 1476-4687 publisher: Nature Publishing Group URL https://www.nature.com/articles/s41586-019-0980-2 [44] Schuld M, Bocharov A, Svore K M and Wiebe N 2020 Physical Review A 101 032308 (Preprint 1804.00633) URL https://link.aps.org/doi/10.1103/PhysRevA.101.032308 [45] Madry A, Makelov A, Schmidt L, Tsipras D and Vladu A 2018 6th International Conference on Learning Representations, ICLR 2018 - Conference Track Proceedings Publisher: International Conference on Learning Representations, ICLR URL https://arxiv.org/abs/1706.06083v4 [46] Lu S, Duan L M and Deng D L 2020 Physical Review Research 2 033212 ISSN 26431564 publisher: American Physical Society URL https://journals.aps.org/prresearch/abstract/10. 1103/PhysRevResearch.2.033212 [47] Baydin A G, Pearlmutter B A, Radul A A and Siskind J M 2018 Journal of Machine Learning Research 18 1–43 arXiv:1502.05767 [48] Feynman R P 1982 International Journal of Theoretical Physics 21 467–488 ISSN 1572-9575 URL https://doi.org/10.1007/BF02650179 [49] Bernstein E and Vazirani U 1997 SIAM Journal on Computing 26 1411–1473 ISSN 0097-5397 publisher: Society for Industrial and Applied Mathematics URL https://epubs.siam.org/ doi/10.1137/S0097539796300921 [50] van der Vaart A W 1998 Asymptotic Statistics (Cambridge University Press) URL https://www. cambridge.org/core/books/asymptotic-statistics/A3C7DAD3F7E66A1FA60E9C8FE132EE1D [51] Yen T C, Ganeshram A and Izmaylov A F 2023 npj Quantum Information 9 URL https: //www.nature.com/articles/s41534-023-00683-y [52] Crawford O, van Straaten B, Wang D, Parks T, Campbell E and Brierley S 2021 Quantum 5 385 URL https://quantum-journal.org/papers/q-2021-01-20-385/ [53] Mari A, Bromley T R and Killoran N 2021 Phys. Rev. A 103 012405 URL https://link.aps. org/doi/10.1103/PhysRevA.103.012405 [54] Kaminishi E, Mori T, Sugawara M et al. 2026 Scientific Reports 16 9390 URL https://doi.org/ 10.1038/s41598-026-40123-3 [55] Dauphin Y N, Pascanu R, Gulcehre C, Cho K, Ganguli S and Bengio Y 2014 Identifying and attacking the saddle point problem in high-dimensional non-convex optimization Advances in Neural Information Processing Systems (NeurIPS) vol 27 pp 2933–2941 arXiv:1406.2572 [56] Li H, Xu Z, Taylor G, Studer C and Goldstein T 2018 Visualizing the loss landscape of neural nets Advances in Neural Information Processing Systems (NeurIPS) vol 31 arXiv:1712.09913 [57] Pesah A, Cerezo M, Wang S, Volkoff T, Sornborger A T and Coles P J 2021 Physical Review X 11 041011 [58] Cerezo M, Sone A, Volkoff T, Cincio L and Coles P J 2021 Nature Communications 12

Measurement cost of gradient attacks on QML

57

[59] Larocca M, Thanasilp S, Wang S, Sharma K, Biamonte J, Coles P J, Cincio L, McClean J R, Holmes Z and Cerezo M 2025 Nature Reviews Physics 7 174–189 [60] Kverne C, Akewar M, DiBrita N S, Huo Y, Patel T and Bhimani J 2026 Variational quantum algorithms are lipschitz smooth Preprint, under review at ICLR 2026 openReview: beg6QFuff4 [61] Mardia K V and Jupp P E 1999 Tests on von Mises Distributions Directional Statistics (John Wiley & Sons, Ltd) pp 119–142 ISBN 978-0-470-31697-9 section: 7 URL https://onlinelibrary. wiley.com/doi/abs/10.1002/9780470316979.ch7 [62] Laurent B and Massart P 2000 Annals of Statistics 28 1302–1338 [63] Vershynin R 2018 High-Dimensional Probability: An Introduction with Applications in Data Science Cambridge Series in Statistical and Probabilistic Mathematics (Cambridge University Press) [64] Alabdulkareem A and Honorio J 2021 Information-theoretic lower bounds for zero-order stochastic gradient estimation IEEE International Symposium on Information Theory (ISIT) pp 2316–2321 arXiv:2003.13881 [65] Spall J C 1992 IEEE Transactions on Automatic Control 37 332–341 ISSN 0018-9286 [66] Majumder R, Khan S M, Ahmed F, Khan Z, Ngeni F, Comert G, Mwakalonge J, Michalaka D and Chowdhury M 2021 arXiv preprint arXiv:2108.01125 (Preprint 2108.01125)