AQKA: Active Quantum Kernel Acquisition Under a Shot Budget

Estimating an $N\times N$ quantum kernel from circuit fidelities requires $\mathrm{\Theta }(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 \emph{which} entries to measure but allocate shots \emph{uniformly} within their chosen subset, ignoring how much each entry drives the downstream classifier. We close this gap with two contributions. $\mathbf{\text{First,}}\mathbf{\text{a}}\mathbf{\text{complete}}\mathbf{\text{regime}}\mathbf{\text{decomposition}}$ for shot-budgeted quantum kernel learning: a principled menu of when each allocator wins. Our method, \emph{AQKA}, dominates the budget-limited regime ($B\lesssim 16n_{\mathrm{p}\mathrm{a}\mathrm{i}\mathrm{r}\mathrm{s}}$) on sparse-sensitivity KRR, with the gap \emph{growing} from $+8$ to $+25$ pts over uniform as $N$ scales $225\to 1000$ and reaching $+26$–$32$ pts on an $\mathtt{\text{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. $\mathbf{\text{Second,}}\mathbf{\text{a}}\mathbf{\text{closed-form}}\mathbf{\text{pair-level}}\mathbf{\text{acquisition}}\mathbf{\text{theory}}$: $s_{ij}^{\star }\propto \mathrm{\mid }{g}_{ij}\mathrm{\mid }\sqrt{K_{ij}(1-K_{ij})}$ with explicit gradient $g_{ij}$ for KRR (Lemma~1, $\mathrm{\mid }{\beta }_i{\alpha }_j+{\beta }_j{\alpha }_i\mathrm{\mid }\sqrt{K_{ij}(1-K_{ij})}$) and SVM via the envelope theorem ($\mathrm{\mid }{\eta }_i^{\ast }{\eta }_j^{\ast }\mathrm{\mid }\sqrt{K_{ij}(1-K_{ij})}$); a \emph{corrected} sparsity-aware Cauchy–Schwarz rate $\rho \le 2m\mathrm{/}N$ matching empirics (vs.\ the naive $m^2\mathrm{/}{N}^2$); an explicit-constant plug-in regret bound (Theorem~2); and a tighter SVM ceiling ${\rho }^{\mathrm{S}\mathrm{V}\mathrm{M}}\le m_{\mathrm{s}\mathrm{v}}^2\mathrm{/}{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 $\mathtt{\text{ibm\_aachen}}$ ($3.5\sigma$, 5 seeds), with the advantage holding at $N=30$ at higher budget on $\mathtt{\text{ibm\_berlin}}$ ($+14.0\pm 8.5$ pts, 5 seeds).