AQKA: Active Quantum Kernel Acquisition Under a Shot Budget

Abstract

Estimating an $N\times N$ quantum kernel from circuit fidelities requires $\hat{I}˜(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. \textbf{First, a complete regime 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{pairs}}$) 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 \texttt{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. \textbf{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, $|{\hat{I}}_i^2\hat{I}{\pm }_j+{\hat{I}}_j^2\hat{I}{\pm }_i|\sqrt{K_{ij}(1-K_{ij})}$) and SVM via the envelope theorem ($|\hat{I}{\cdot }_i^{\ast }\hat{I}{\cdot }_j^{\ast }|\sqrt{K_{ij}(1-K_{ij})}$); a \emph{corrected} sparsity-aware Cauchy--Schwarz rate $\ddot{I}\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 $\ddot{I}{}^{\mathrm{SVM}}\le m_{\mathrm{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 \texttt{ibm\_aachen} ($3.5\ddot{I}ƒ$, 5 seeds), with the advantage holding at $N=30$ at higher budget on \texttt{ibm\_berlin} ($+14.0\pm 8.5$ pts, 5 seeds).