AQKA: Active Quantum Kernel Acquisition Under a Shot Budget

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