AQKA: Active Quantum Kernel Acquisition Under a Shot Budget

arXiv:2605.14672v1 Announce Type: new Abstract: Estimating an N imes N quantum kernel from circuit fidelities requires Theta(N^2 S) measurement shots, the dominant bottleneck for deployment on near-term hardware. Existing budget-saving methods (Nystrom-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. extbf{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{o1000 and reaching +26--32 pts on an exttt{ibm_pittsburgh} (156-qubit Heron) hardware kernel; Nystrom-QKE wins at saturating budgets on planted-sparse via low-rank reconstruction; ShoFaR is competitive only at extreme low budgets. extbf{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 (Lemma1, |eta_ialpha_j+eta_jalpha_i|sqrt{K_{ij}(1-K_{ij})}) and SVM via the envelope theorem (|eta_i^eta_j^|sqrt{K_{ij}(1-K_{ij})}); a corrected sparsity-aware Cauchy--Schwarz rate rho le 2m/N matching empirics (vs. the naive m^2/N^2); an explicit-constant plug-in regret bound (Theorem2); and a tighter SVM ceiling rho^{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 exttt{ibm_aachen} (3.5sigma, 5 seeds), with the advantage holding at N{=}30 at higher budget on exttt{ibm_berlin} (+14.0 pm 8.5 pts, 5 seeds).

Source: arXiv cs.LG | 2026-05-15