AQKA: Active Quantum Kernel Acquisition Under a Shot Budget

Estimating an N × N quantum kernel from circuit fidelities requires Theta(N2 S) measurement shots, the dominant bottleneck for deployment on near-term hardware. Existing budget-saving methods (Nystr"om-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 npairs) on sparse-sensitivity KRR, with the gap growing from +8 to +25 pts over uniform as N scales 225→1000 and reaching +26--32 pts on an textttibmpittsburgh (156-qubit Heron) hardware kernel; Nystr"om-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: sijstar propto |gij|√Kij(1-Kij) with explicit gradient gij for KRR (Lemma~1, |βiαj+βjαi|√Kij(1-Kij)) and SVM via the envelope theorem (|ηi^*ηj^*|√Kij(1-Kij)); a corrected sparsity-aware Cauchy--Schwarz rate ρ ≤ 2m/N matching empirics (vs. the naive m2/N2); an explicit-constant plug-in regret bound (Theorem~2); and a tighter SVM ceiling ρSVM ≤ msv2/N2. We close with the first multi-seed live online adaptive shot allocation on quantum hardware: +17.0 ± 4.8 pts at N=20 on textttibmaachen (3.5σ, 5 seeds), with the advantage holding at N=30 at higher budget on textttibmberlin (+14.0 ± 8.5 pts, 5 seeds).