acceptodds
Under review as a conference paper at ICLR 2027

One Shot Is a Gradient: Raw-Measurement Optimization for Quantum Kernel Machines

Abstract

A quantum kernel is observable only through shots: destructive circuit runs that each return one bit whose mean is the kernel entry. Standard training averages many shots per kernel entry, typically estimating the whole Gram matrix before optimizing, so measurement grows with the N² pairs of training examples. Yet a stochastic optimizer never needs the matrix. It needs an unbiased gradient, which a single shot already provides, or a yes/no hinge decision, which sequential shots can certify. We therefore train the exact kernel SVM directly from raw shots. Raw-Shot Coordinate Ascent (RSCA) turns each shot into an unbiased coordinate gradient of the SVM dual, with a low-rank control variate that reduces noise without changing the solution. Aggregate-Margin-Oracle (AMO) Pegasos samples an example's margin until an anytime-valid test certifies its hinge decision. At fixed regularization, decision error ε costs Õ(minNε⁻⁴, ε⁻⁶) shots, linear in N or independent of it. AMO becomes cheaper when few margins lie near the hinge, and a lower bound for each decision shows that no sequential test avoids this margin dependence. In shot-level simulations on MNIST with up to N = 1024 examples, RSCA's shot cost grows at most linearly in N. At N = 1024 it reaches a fixed error target with 2.5–3× fewer shots than our strongest entry-estimating baseline, fewer than one shot per pair, and its lead survives 1% depolarizing and readout noise. Strict AMO certifies every hinge decision at the per-decision cost that the lower bound predicts.

Primary area:
optimization
Keywords:
quantum kernel methods, support vector machines, stochastic optimization, variance reduction, confidence sequences, shot complexity, Pegasos, kernel learning

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_2RGEOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposed training quantum kernel SVMs directly from raw quantum measurement outcomes rather than first estimating the full kernel matrix. The authors argued that standard quantum-kernel pipelines unnecessarily spend many shots estimating individual kernel entries before optimization. The authors provide stochastic-optimization bounds for RSCA and AMO. Experiments are conducted in shot-level simulation using balanced MNIST digit pairs.

Critical strengths

The paper identifies a sensible systems-level inefficiency in the standard quantum-kernel pipeline. Estimating all kernel entries accurately before optimization can indeed be wasteful. This paper explored algorithms to solve this challenge.

The distinction between entry estimation and optimization-directed measurement is clearly presented. The paper contains a reasonably complete theoretical analysis.

Critical weaknesses

The title “One Shot Is a Gradient” is technically misleading. In the main contributions, the first contribution: A shot is a gradient. Suitably weighted, one destructive measurement outcome is an unbiased stochastic gradient of the exact SVM dual, and a sequence of outcomes certifies a hinge decision. Training never needs the Gram matrix. It seems to not clearly justify why a short is a gradient. These statements seem to not really construct a main contribution.

The strongest practical RSCA method does not operate from one-shot information alone.

The empirical evaluation is narrow.

Questions for authors

Would the authors be able to better justify the title? “One Shot Is a Gradient” seems mathematically inaccurate.

How does the method behave for entangling quantum feature maps?

Can the authors provide a real-hardware experiment?

1 comment
AuthorsOpenReview ↗

Response to Reviewer 2RGE

We thank the reviewer for the clear assessment.

W1/Q1 (title, contribution 1). The title abbreviates a precise statement about the SVM dual. A shot is one measured bit ZijZ_{ij} with E[Zij]=Kij\mathbb E[Z_{ij}]=K_{ij}. The dual gradient is the weighted kernel sum gi(α)=1−λ−1yi∑jαjyjKijg_i(\alpha)=1-\lambda^{-1}y_i\sum_j\alpha_jy_jK_{ij}. Draw one partner JJ with probability αJ/A\alpha_J/A and measure the pair once. This gives g^i=1−AλyiyJZiJ,E[g^i∣α,i]=gi(α),∣g^i∣≤1+λ−1\widehat g_i=1-\tfrac{A}{\lambda}y_iy_JZ_{iJ},\qquad \mathbb E[\widehat g_i\mid\alpha,i]=g_i(\alpha),\qquad |\widehat g_i|\le1+\lambda^{-1} (Eq. 4). One weighted outcome is therefore an unbiased, bounded stochastic gradient coordinate of the exact dual. This is the same sense in which one training example is a stochastic gradient in SGD.

Why this is a main contribution: existing pipelines take the kernel entry as the unit of measurement. They need about δ−2\delta^{-2} shots per entry before optimizing. Unbiasedness removes that layer. Standard stochastic-approximation theory then prices training directly in shots (Theorem 1: O~(Nϵ−4)\widetilde O(N\epsilon^{-4}) for decision error ϵ\epsilon). The optimizer pays to cover O(N)O(N) examples instead of Θ(N2)\Theta(N^2) entries. This gives the linear-versus-quadratic separation in §5. We rewrote contribution 1 to say this:

A shot is a gradient. The dual gradient is a weighted sum of kernel entries, and each entry is the mean of one measured bit. If we draw a partner by its dual weight and measure the pair once, the outcome is an unbiased stochastic gradient coordinate of the exact SVM dual (Eq. 4). A sequence of outcomes certifies a hinge decision. Standard stochastic-optimization theory then counts the shots that training needs, and no kernel entry is ever estimated.

W2 (the strongest RSCA variant). Each optimization step of shared-shot RSCA uses one fresh shot, and all LL step-size schedules share it. The control is a one-time measurement of r=4r=4 landmark columns before training. All of its shots count toward RSCA's budget: 12.3k of 165.7k (7.4%) at N=1024N=1024. Eq. 7 keeps every direction unbiased for any control, and App. D.3 gives the guarantee for this variant. The control adds variance reduction on top of one-shot gradients, as in SVRG. It is our contribution 2. In the paper's synthetic study (Table 2), RSCA without a control, which reuses each bit at both endpoints, already matches the cached baseline (median error 0.0353 against 0.0356 at about 19.7k shots); the shared-shot control lowers the error to 0.0277. On MNIST, shared-shot RSCA needs 2.5–3.0× fewer shots than the cached baseline on every pair at N=1024N=1024.

W3/Q2 (evaluation breadth, entangling maps). We reran the MNIST protocol on all three digit pairs with eight entangling feature maps. These are the ZZ map of Havlíček et al. (2019) and the IQP map, each on 4–12 qubits. Baselines and the step constant are unchanged, and the runs use fresh evaluation seeds. The Gram spectra have participation ratios from 1.9 to 25.8. In all 24 map–pair cells, RSCA's shots to error 0.3 grow linearly in NN (slopes 0.72–1.19). At N=1024N=1024, RSCA needs 2.7–3.1× fewer shots than the cheapest cached configuration in 22 cells and 1.6× fewer in the other two. With 4 to 64 landmarks (ZZ maps, 4–8 qubits), RSCA's error at T=150NT=150N stays between 0.23 and 0.31.

Q3 (real hardware). We ran the full pipeline on ibm_marrakesh (156-qubit Heron processor). The setting is MNIST 3 vs 8 with N=64N=64, the paper's 20 evaluation seeds, and 577k shots. Shared-shot RSCA draws its pairs uniformly, independently of the iterate. We therefore drew its schedule before training and measured it in two batched jobs, with no device round trips. Every pair received at least 10 shots, enough for all cached configurations. Training then used only device bits. In all 14 trained configurations (2 RSCA and 12 cached), the device's decision error is consistent with the simulator on the same seeds: no configuration differs significantly (all sign-test p-values ≥ 0.26). RSCA reaches error 0.213 at 10.2k shots, against 0.191 in simulation. Its test accuracy is 0.84 (exact SVM: 0.843). The measured kernel follows 0.009+0.974K0.009+0.974K. The device noise is thus below the paper's 1% setting, under which §5 shows that RSCA keeps its lead at large NN.

Revision: The revised PDF rewrites contribution 1 and adds the new results to §5 and a new Appendix F.

Reviewer_1B1WOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes two methods for training a fixed-kernel SVM directly from raw quantum measurement outcomes without constructing the full Gram matrix. RSCA uses individual shots to obtain unbiased stochastic gradients of the dual objective, with a frozen control variate to reduce variance. AMO uses sequential confidence intervals to decide whether a sampled margin requires a hinge update, up to a specified tolerance. The paper provides shot-complexity guarantees and reports measurement savings over entry-estimating baselines in simulated experiments.

Critical strengths
  1. The paper addresses an important bottleneck in quantum kernel learning. Using shots directly for optimization is a natural and appealing alternative to estimating the full Gram matrix.
  2. The methods retain the original SVM objective. In particular, the Nyström approximation serves as a control variate rather than restricting the predictor to an approximate kernel representation.
  3. The analysis connects optimization accuracy to measurement cost and explains AMO’s dependence on the distance to the hinge. The experiments include control-construction shots, ablations, and noise and drift studies, which help clarify the source of the reported gains.
Critical weaknesses
  1. The experiments are limited to one-qubit synthetic states and a four-qubit product feature map on PCA-reduced MNIST. These settings are useful for testing shot efficiency, but they do not establish whether the gains persist for larger entangling feature maps or on real hardware.
  2. The main efficiency metric is the number of shots rather than end-to-end training time. The implemented shared-shot RSCA variant requires O(LNr) classical work per round, and its advantage over cached estimates becomes smaller at higher accuracy or weaker regularization. The practical trade-off therefore needs further evaluation.
Questions for authors
  1. Do the shot savings persist for entangling feature maps with larger qubit counts and different kernel spectra? How sensitive is the control variate’s effectiveness to these changes?
  2. Could you report end-to-end runtime, including classical updates and circuit execution overhead, and identify the regimes where raw-shot optimization is preferable to caching kernel estimates?
1 comment
AuthorsOpenReview ↗

Response to Reviewer 1B1W

We thank the reviewer for the precise summary.

W1/Q1 (entangling maps, larger qubit counts, kernel spectra). The shot savings persist. We reran the full MNIST protocol on all three digit pairs with eight entangling feature maps. These are the ZZ map of Havlíček et al. (2019) and the IQP map, each on 4–12 qubits. Both implementations agree with Qiskit to 10−1410^{-14}. Bandwidths were chosen by validation accuracy on development seeds of 3 vs 8 and reused. Baselines and the frozen step constant are unchanged; all runs use fresh evaluation seeds 200–219. The table gives RSCA's shot saving over the cheapest cached configuration at error 0.3 and N=1024N=1024 (medians over seeds; seeds with a degenerate exact dual are skipped, App. F.1):

mapparticipation ratio (3 vs 8)3 vs 82 vs 30 vs 1
ZZ, 4 qubits2.03.1×2.9×2.7×
ZZ, 64.11.6×3.0×2.8×
ZZ, 89.13.1×3.1×2.9×
ZZ, 1025.83.1×3.1×3.0×
ZZ, 12 (γ = 0.05)6.33.1×3.1×2.9×
IQP, 41.93.1×3.1×2.9×
IQP, 82.53.1×3.1×3.0×
IQP, 125.13.1×1.6×3.1×

In 22 of the 24 cells, RSCA reaches the target at its shortest horizon: 165.7k shots, against 455k–516k for caching. Its cost grows linearly in NN, with slopes 0.72–1.19 (caching: 1.14–1.68). As in the paper, the cheapest cached configuration touches nearly every pair, so it costs about N2/2N^2/2 shots. On 2 vs 3 and 0 vs 1, RSCA even reaches error 0.2 at 165.7k shots in 11 of 16 cells, again about 3× fewer. In a bandwidth sweep at N=512N=512 (participation ratio 1.3 to 22), RSCA's error at T=150NT=150N stays at 0.18–0.25.

Q1 (control sensitivity). We measure the control by E[(ZIJ−Bc,IJ)2]/E[ZIJ2]\mathbb E[(Z_{IJ}-B_{c,IJ})^2]/\mathbb E[Z_{IJ}^2] over uniform pairs (smaller is better; ZZ maps, N=1024N=1024):

qubitsr=4r=4r=8r=8r=16r=16r=64r=64
40.320.320.330.38
60.560.530.520.53
80.920.870.800.75

The ratio grows as the spectrum spreads, but the kernel entries shrink too. The absolute residual second moment therefore stays between 0.18 and 0.26 in all twelve cells. This quantity drives the per-shot variance (Eq. 24, App. D.3). RSCA's error at T=150NT=150N stays between 0.23 and 0.31, so four landmarks suffice. Eq. 7 holds for any control, so the control's quality changes only this variance and never the target.

W1/Q2 (real hardware, end-to-end runtime). We ran the full pipeline on ibm_marrakesh (156-qubit Heron processor). The setting is MNIST 3 vs 8 with N=64N=64, the paper's 20 evaluation seeds, and 577k shots. Shared-shot RSCA draws its pairs independently of the iterate, so we measured its schedule before training in two batched jobs. Every pair received at least 10 shots, enough for all cached configurations. Training then used only device bits. In all 14 trained configurations (2 RSCA and 12 cached), the device's decision error is consistent with the simulator on the same seeds (no significant difference; all sign-test p ≥ 0.26). RSCA reaches 0.213 at 10.2k shots, against 0.191 in simulation. Its test accuracy is 0.84 (exact SVM: 0.843). The device kernel follows 0.009+0.974K0.009+0.974K, which corresponds to less noise than the paper's 1% setting.

A fit to all five device jobs (three timing jobs, two measurement jobs) gives a QPU charge of 2.0 s per job + 0.92 ms per binding + 0.23 ms per shot. At N=1024N=1024 on 3 vs 8, where both methods reach error ≈0.09:

shotsdistinct circuitsQPU time (model)classical time
RSCA165.7k136k165 s12.9 s (85 µs/round, one core)
cached506k504k582 s8.2 s (5N rounds, one core)

QPU charge plus classical time is about 178 s against 590 s. RSCA's classical work does not depend on the qubit count. Pure one-shot RSCA (Eq. 4) needs no control and takes 36 µs per round.

Q2 (regimes). The deciding quantity is the budget relative to the number of pairs.

  • Raw-shot optimization is preferable when the target needs fewer than about N2/2N^2/2 shots, i.e., less than one shot per pair. This is large NN at moderate accuracy. At N=1024N=1024, RSCA needs 2.5–3.0× fewer shots on all three MNIST pairs. On the entangling maps, it needs 2.7–3.1× fewer in 22 of 24 cells and 1.6× fewer in the other two. The lead grows with NN. For target 0.3, the crossover lies between N=256N=256 and 512512 (Fig. 3a).
  • Caching becomes competitive when the target needs about N2/2N^2/2 shots or more, because cached entries are then reused. This happens at small NN, at high accuracy, or under weak regularization. Examples are target 0.1 at N=512N=512 on two pairs, λ=0.02\lambda=0.02 at N=1024N=1024 on two pairs, and target 0.2 on the 3 vs 8 entangling maps.

Revision: The revised PDF adds these results to §5 and a new Appendix F (entangling maps, control sensitivity, hardware run, runtime and regime table).

Reviewer_xfcsOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper trains the exact kernel SVM directly from raw shots. Raw-Shot Coordinate Ascent (RSCA) turns each shot into an unbiased coordinate gradient of the SVM dual, using a low-rank control variate to reduce noise without changing the solution.

Critical strengths
  1. Rigorous and insightful mathematical formulations.
  2. Clear and easy to follow (good paper writing).
  3. The proposed method is novel.
Critical weaknesses
  1. Too few evaluations.
  2. Did not discuss the hardware/simulator used in the experiments.
Questions for authors
  1. What hardware/simulator was used in the experiments?
  2. How large is the quantum circuit? How far is it from being used with practical hardware?
3 comments
AuthorsOpenReview ↗

Response to Reviewer xfcs

We thank the reviewer for the positive assessment.

W2/Q1 (hardware/simulator). The paper's experiments use our own shot-level simulator. It is written in NumPy and runs on CPUs; no GPU and no third-party circuit simulator is involved. The evaluator computes the exact kernel. For the product map it uses a closed form, and for the entangling maps it uses 2q2^q-dimensional statevectors. Each training query (i,j)(i,j) returns a fresh Bernoulli(KijK_{ij}) bit. This is exactly the output distribution of an ideal overlap circuit, and the methods see only these bits. A device enters training only through this bit, so the simulation is exact for any ideal circuit that realizes KK. Device noise enters through the effective kernel of the noisy inversion test (§5, App. E). We have now also run the method on real hardware (below).

Q2 (circuit size, distance to hardware).

  • Size. The MNIST product map uses 4 qubits. Each overlap circuit applies RY(xk)R_Y(x_k) and then RY(−zk)R_Y(-z_k) to qubit kk, then measures all qubits. The outcome is 1 when all qubits read 0. Compiled for an IBM Heron processor, the circuit has 8 X\sqrt X gates, 16 virtual RZR_Z gates, no two-qubit gates, and depth 7.
  • On hardware today. We ran the full pipeline on ibm_marrakesh (156-qubit Heron processor). The setting is MNIST 3 vs 8 with N=64N=64 and the paper's 20 evaluation seeds. The run used 577k shots in two batched jobs and 184 s of QPU time. Every pair received at least 10 shots, enough for all 12 cached configurations as well as RSCA. In all 14 trained configurations (2 RSCA and 12 cached), the device's decision error is consistent with the simulator on the same seeds: no configuration differs significantly (all sign-test p-values ≥ 0.26). RSCA's test accuracy is 0.84 (exact SVM: 0.843). The device kernel follows 0.009+0.974K0.009+0.974K.
  • What scales. The main costs are shots and distinct circuits, and RSCA reduces both. A fit to the device jobs gives a QPU time of 2.0 s per job + 0.92 ms per circuit binding + 0.23 ms per shot. At N=1024N=1024, this gives 165 s for RSCA against 582 s for the cached baseline.

W1 (more evaluations). We added three evaluations.

  1. Eight entangling feature maps (ZZ and IQP, 4–12 qubits) on all three MNIST digit pairs. RSCA's shots to error 0.3 grow linearly in NN. At N=1024N=1024, RSCA needs 2.7–3.1× fewer shots than the cheapest cached configuration in 22 of 24 cells (1.6× in the other two).
  2. A sweep over 4–64 landmarks for the control variate. RSCA's error stays between 0.23 and 0.31, so four landmarks suffice.
  3. The hardware run and the runtime model above.

Revision: The revised PDF describes the simulator in §5 and adds the new results to §5 and a new Appendix F.

Thanks for the response. I will keep my score since I already lean toward acceptance.

Thank you for the follow-up and for your positive assessment.

Comments on the paper

2 comments
AuthorsOpenReview ↗

Summary of revisions

We thank all reviewers. The revised PDF marks every change in blue.

  • §1: Contribution 1 now states why one weighted outcome is an unbiased stochastic gradient and what follows from it.
  • §5: A description of the shot-level simulator, and a summary of the entangling-map and hardware results.
  • §6: Updated to point to the new results.
  • Appendix F (new): F.1 entangling ZZ and IQP feature maps on 4–12 qubits and three digit pairs; F.2 control-variate sensitivity (4–64 landmarks); F.3 hardware run on ibm_marrakesh (156-qubit Heron processor); F.4 runtime model and regime table.

All new simulations reuse the paper's protocol, baselines, and the frozen step constant of shared-shot RSCA. The entangling-map runs use fresh evaluation seeds.

AuthorsOpenReview ↗

Summary of the discussion

We thank the reviewers and the Area Chair. As the discussion period closes, we summarize how the revision addresses each concern. In short, we ran every experiment the reviewers asked for. RSCA's shot savings persist on eight entangling feature maps, and the full pipeline runs on real hardware with results consistent with the simulator. Details are in our replies and in the revised PDF (changes in blue, new Appendix F).

  1. Entangling maps: RSCA needs fewer shots in all 24 cells at N=1024N=1024 (1B1W W1/Q1, 2RGE W3/Q2, xfcs W1). We reran the full MNIST protocol on all three digit pairs with eight entangling feature maps (ZZ and IQP, 4–12 qubits; participation ratios 1.9–25.8). RSCA's shots to error 0.3 grow linearly in NN in all 24 cells. At N=1024N=1024, RSCA needs 2.7–3.1× fewer shots than the cheapest cached configuration in 22 cells and 1.6× fewer in the other two (App. F.1).

  2. Control variate: four landmarks suffice (1B1W Q1). On the ZZ maps with 4–8 qubits at N=1024N=1024, RSCA's error at T=150NT=150N stays between 0.23 and 0.31 for 4 to 64 landmarks. Eq. 7 keeps every direction unbiased for any control, and the control's shots are charged to RSCA's budget: 7.4% of its shots at N=1024N=1024 (App. F.2).

  3. Real hardware: consistent with the simulator (1B1W W1, 2RGE Q3, xfcs Q2). We ran the full pipeline on ibm_marrakesh (156-qubit Heron processor): MNIST 3 vs 8, N=64N=64, the paper's 20 evaluation seeds, 577k shots. Training used only device bits. In all 14 trained configurations, the device's decision error is consistent with the simulator on the same seeds (all sign-test p ≥ 0.26; App. F.3).

  4. End-to-end runtime: about 178 s against 590 s at N=1024N=1024 (1B1W W2/Q2). A QPU-time model fitted to the device jobs gives 165 s for RSCA against 582 s for the cached baseline at N=1024N=1024 on 3 vs 8; with classical time included, about 178 s against 590 s. Raw-shot optimization is preferable when the target needs fewer than about N2/2N^2/2 shots, and caching becomes competitive beyond that (App. F.4).

  5. Title: one shot gives an unbiased stochastic gradient (Eq. 4) (2RGE W1/Q1, W2). Eq. 4 shows that one weighted outcome is an unbiased, bounded stochastic gradient coordinate of the exact SVM dual, in the same sense that one training example is a stochastic gradient in SGD. This removes per-entry estimation, so training pays to cover O(N)O(N) examples instead of Θ(N2)\Theta(N^2) entries (Theorem 1, §5). Contribution 1 now states this. The strongest variant uses one fresh shot per step; its control is a one-time measurement whose shots are included in every reported count.

  6. Simulator and circuit size: 4 qubits, depth 7 (xfcs W2/Q1, Q2). §5 now describes the shot-level simulator. The 4-qubit overlap circuit of the MNIST product map compiles for the Heron processor to depth 7 with no two-qubit gates (App. F.3).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.