- 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?
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 Zij with E[Zij]=Kij. The dual gradient is the weighted kernel sum gi(α)=1−λ−1yi∑jαjyjKij. Draw one partner J with probability αJ/A and measure the pair once. This gives gi=1−λAyiyJZiJ,E[gi∣α,i]=gi(α),∣gi∣≤1+λ−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 shots per entry before optimizing. Unbiasedness removes that layer. Standard stochastic-approximation theory then prices training directly in shots (Theorem 1: O(Nϵ−4) for decision error ϵ). The optimizer pays to cover O(N) examples instead of Θ(N2) entries. This gives the linear-versus-quadratic separation in §5. We rewrote contribution 1 to say this:
W2 (the strongest RSCA variant). Each optimization step of shared-shot RSCA uses one fresh shot, and all L step-size schedules share it. The control is a one-time measurement of r=4 landmark columns before training. All of its shots count toward RSCA's budget: 12.3k of 165.7k (7.4%) at N=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=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 N (slopes 0.72–1.19). At N=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=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=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.974K. The device noise is thus below the paper's 1% setting, under which §5 shows that RSCA keeps its lead at large N.
Revision: The revised PDF rewrites contribution 1 and adds the new results to §5 and a new Appendix F.