AQKA: Active Quantum Kernel Acquisition Under a Shot Budget
Jian Xu, Chao Li, Delu Zeng, John Paisley, Qibin Zhao · 2026
Read AQKA: Active Quantum Kernel Acquisition Under a Shot Budget by Jian Xu, Chao Li, Delu Zeng, John Paisley, Qibin Zhao (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-14672.txt.
Introduction
Xu, Li, Zeng, Paisley and Zhao tackle quantum kernel estimation under a shot budget. Measuring an N by N kernel costs on the order of N squared times shots. Existing savers sub-sample which entries to measure but spread shots evenly within the subset. They ignore how much each entry shapes the downstream classifier. Their AQKA method allocates shots by a closed-form pair-level rule tied to classifier sensitivity. It is claimed to dominate the budget-limited regime on sparse-sensitivity kernel ridge regression in tests.
Catalog record
| CREATOR | Jian Xu, Chao Li, Delu Zeng, John Paisley, Qibin Zhao |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 108589 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.14672
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
AQKA: Active Quantum Kernel Acquisition Under a Shot Budget Jian Xu, Chao Li, Delu Zeng, John Paisley, Qibin Zhao Abstract Estimating an N × N N\times N quantum kernel from circuit fidelities requires Θ ( N 2 S ) \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 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 ≲ 16 n pairs B\lesssim 16n_{\mathrm{pairs}} ) on sparse-sensitivity KRR, with the gap growing from + 8 +8 to + 25 +25 pts over uniform as N N scales 225 → 1000 225{\to}1000 and reaching + 26 +26 – 32 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 i j ⋆ ∝ | g i j | K i j ( 1 − K i j ) s_{ij}^{\star}\propto|g_{ij}|\sqrt{K_{ij}(1-K_{ij})} with explicit gradient g i j g_{ij} for KRR (Lemma 1, | β i α j + β j α i | K i j ( 1 − K i j ) |\beta_{i}\alpha_{j}+\beta_{j}\alpha_{i}|\sqrt{K_{ij}(1-K_{ij})} ) and SVM via the envelope theorem ( | η i ∗ η j ∗ | K i j ( 1 − K i j ) |\eta_{i}^{*}\eta_{j}^{*}|\sqrt{K_{ij}(1-K_{ij})} ); a corrected sparsity-aware Cauchy–Schwarz rate ρ ≤ 2 m / N \rho\leq 2m/N matching empirics (vs. the naive m 2 / N 2 m^{2}/N^{2} ); an explicit-constant plug-in regret bound (Theorem 2); and a tighter SVM ceiling ρ SVM ≤ m sv 2 / N 2 \rho^{\mathrm{SVM}}\leq m_{\mathrm{sv}}^{2}/N^{2} . We close with the first multi-seed live online adaptive shot allocation on quantum hardware: + 17.0 ± 4.8 +17.0\pm 4.8 pts at N = 20 N{=}20 on ibm_aachen ( 3.5 σ 3.5\sigma , 5 seeds), with the advantage holding at N = 30 N{=}30 at higher budget on ibm_berlin ( + 14.0 ± 8.5 +14.0\pm 8.5 pts, 5 seeds). 1 Introduction Quantum kernel methods ( 9 ; 24 ) embed classical inputs into a quantum feature space and use the resulting fidelity, K(x_{i},x_{j})=|\langle\phi(x_{j})|\phi(x_{i})\rangle|^{2}\in[0,1] , as a positive semi-definite kernel for support vector machines (SVM) or kernel ridge regression (KRR). They admit provable separations on classically-hard data ( 13 ) and are among the most experimentally accessible quantum machine-learning workloads on noisy intermediate-scale quantum (NISQ) hardware. Their dominant practical bottleneck is measurement cost : each entry K_{ij} requires S Bernoulli outcomes of an inversion test, so the full N\times N Gram matrix costs \Theta(N^{2}S) circuit executions ( 15 ) . With per-circuit latencies in the millisecond-to-second range on present-day hardware, this scaling caps deployable N at the low hundreds. Existing budget-saving methods spend the shot budget non-uniformly along one axis at a time. Nyström -style methods ( 6 ) measure M\ll N landmark columns; sub-sampled QKA ( 22 ) sub-samples training points during variational kernel training; shot-frugal robust SVM ( 25 ) adapts total shots to the SVM margin. Each prescribes which entries to measure, but allocates the per-entry shot budget uniformly within its chosen subset—and so cannot exploit the heterogeneity of how much each entry contributes to the downstream classifier. The unanswered question: given a fixed budget B , which pair-level entries deserve how many shots? Our contribution. We formulate shot-budgeted quantum kernel learning as \min_{\{s_{ij}\}}\;\mathbb{E}\bigl[\mathcal{L}(\hat{K})\bigr]\quad\text{s.t.}\quad\sum_{i\leq j}s_{ij}\leq B, (1) where \hat{K}_{ij} is an unbiased Bernoulli estimate of K_{ij} with variance K_{ij}(1-K_{ij})/s_{ij} . A first-order analysis combined with the KKT conditions yields a clean closed form: s_{ij}^{\star}\;\propto\;|g_{ij}|\sqrt{K_{ij}(1-K_{ij})}, (2) where g_{ij}=\partial\mathcal{L}/\partial K_{ij} is the loss gradient with respect to the kernel entry—equivalently, s_{ij}^{\star}\propto\sqrt{a_{ij}} with a_{ij}:=g_{ij}^{2}K_{ij}(1-K_{ij}) the delta-method variance contribution of pair (i,j) . We turn this into a deployable algorithm, Active Quantum Kernel Acquisition (AQKA), in which a small warm-up budget yields plug-in estimates of K_{ij} and g_{ij} , and the remaining budget is filled toward the target s_{ij}^{\star} rather than sampled from it—we show below that this distinction matters even with oracle sensitivities. The contributions are: 1. A complete regime decomposition for shot-budgeted quantum kernel learning. We provide the first principled characterization of when each allocation strategy wins: AQKA (this work) dominates the budget-limited regime B\lesssim 16n_{\mathrm{pairs}} on sparse-sensitivity KRR; Nyström-QKE wins at saturating budgets on planted-sparse via low-rank reconstruction; ShoFaR-style captures only the extreme low-budget regime. The decomposition is supported by closed-form theory (Cauchy–Schwarz bounds with regime-specific rates) and validated across simulator, hardware-resampling, and live-hardware settings; it tells practitioners which method to pick for which budget , which prior shot-allocation work for QKE has not addressed. 2. Pair-level KKT-optimal acquisition theory for KRR and SVM under shot noise. We derive the closed-form gradient g_{ij} for KRR (Lemma 1 , s^{\star}_{ij}\propto|g_{ij}|\sqrt{K_{ij}(1-K_{ij})} ), a corrected sparsity-aware Cauchy–Schwarz rate \rho\leq 2m/N matching empirics (vs. the naive m^{2}/N^{2} , Theorem 1 ), an explicit-constant plug-in regret bound (Theorem 2 ), and a rigorous SVM extension via the envelope theorem with a tighter \rho^{\mathrm{SVM}}\leq m_{\mathrm{sv}}^{2}/N^{2} ceiling (Appendix A ). 3. AQKA: a deployable target-fill plug-in algorithm. The deterministic target-fill scheme outperforms the natural multinomial sampler at matched sensitivity score and scales favorably with N : gain over uniform grows from +8 to +25 pts as N{:}225{\to}1000 on planted-sparse, reaches +26 – 32 pts on the ibm_pittsburgh -measured hardware kernel, and +11 pts over Nyström at B{=}n_{\mathrm{pairs}} . Robust to baseline tuning: \tau -sweep for ShoFaR (Appendix C ) and m_{\ell} -sweep with leverage-score Nyström variant (Appendix C ) preserve the regime decomposition. 4. First multi-seed live online adaptive shot allocation on quantum hardware. Real-time adaptive T{=}4 -round shot submission via qiskit-ibm-runtime Session: +17.0\pm 4.8 pts at N{=}20 across 5 seeds on ibm_aachen ( 3.5\sigma , 4/5 seeds positive); +14.0\pm 8.5 pts at N{=}30 at B{=}16n_{\mathrm{pairs}} on ibm_berlin . To our knowledge, the first published demonstration of online adaptive QKE on a current 156-qubit IBM Heron-class device. 2 Background Quantum kernels and shot noise. A quantum feature map |\phi(x)\rangle=U(x)|0\rangle^{\otimes n} produced by a parametric circuit U(\cdot) on n qubits induces the fidelity kernel K(x_{i},x_{j})=|\langle 0|U(x_{j})^{\dagger}U(x_{i})|0\rangle|^{2}, (3) estimated on hardware by executing U(x_{j})^{\dagger}U(x_{i}) and counting the frequency of the all-zero outcome. With s shots, \hat{K}_{ij}\;=\;\frac{1}{s}\sum_{t=1}^{s}b_{ij}^{(t)},\qquad b_{ij}^{(t)}\stackrel{{\scriptstyle\text{iid}}}{{\sim}}\mathrm{Bernoulli}(K_{ij}), (4) so \mathbb{E}[\hat{K}_{ij}]=K_{ij} and \mathrm{Var}[\hat{K}_{ij}]=K_{ij}(1-K_{ij})/s . For N training points the standard pipeline measures all M:=\binom{N}{2}+N unique entries with the same s , yielding total cost \Theta(N^{2}s) . Kernel ridge regression as the analytic vehicle. We use KRR for theoretical analysis because its loss has closed-form, smooth gradients with respect to K . Given training labels y\in\{-1,+1\}^{N} and ridge \lambda>0 , the KRR predictor is \hat{f}(x)=\sum_{i}\alpha_{i}K(x_{i},x) with \alpha=(K+\lambda I)^{-1}y , and the training squared loss is \mathcal{L}_{\mathrm{tr}}(K)\;=\;\|y-K\alpha\|^{2}\;=\;\lambda^{2}\|\alpha\|^{2}. (5) The first lemma below is the analytic backbone of all subsequent allocation results; its proof is in Appendix A . Lemma 1 (KRR gradient and Gauss–Newton sensitivity) . Let \mathcal{L}_{\mathrm{tr}}(K)=\lambda^{2}\|\alpha(K)\|^{2} with