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

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.