# AQKA: Active Quantum Kernel Acquisition Under a Shot Budget

arXiv: https://arxiv.org/abs/2605.14672 · HTML: https://mlsanity.com/paper/2605.14672/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 30 references that are in the map.
- First posted on arXiv 14 May 2026.

## Builds on (most cited first, 17 of 17)

- [Understanding Black-box Predictions via Influence Functions](https://mlsanity.com/paper/1703.04730/) (2017)
- [Supervised learning with quantum enhanced feature spaces](https://mlsanity.com/paper/1804.11326/) (2018)
- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Power of data in quantum machine learning](https://mlsanity.com/paper/2011.01938/) (2020)
- [A rigorous and robust quantum speed-up in supervised machine learning](https://mlsanity.com/paper/2010.02174/) (2020)
- [Supervised quantum machine learning models are kernel methods](https://mlsanity.com/paper/2101.11020/) (2021)
- [Exponential concentration in quantum kernel methods](https://mlsanity.com/paper/2208.11060/) (2022)
- [Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees](https://mlsanity.com/paper/1804.09893/) (2018)
- [On Fast Leverage Score Sampling and Optimal Learning](https://mlsanity.com/paper/1810.13258/) (2018)
- [Quantum Kernel Methods under Scrutiny: A Benchmarking Study](https://mlsanity.com/paper/2409.04406/) (2024)
- [Fourier Sparse Leverage Scores and Approximate Kernel Learning](https://mlsanity.com/paper/2006.07340/) (2020)
- [Distributed Adaptive Sampling for Kernel Matrix Approximation](https://mlsanity.com/paper/1803.10172/) (2018)
- [A kernel-based quantum random forest for improved classification](https://mlsanity.com/paper/2210.02355/) (2022)
- [Improved Active Learning via Dependent Leverage Score Sampling](https://mlsanity.com/paper/2310.04966/) (2023)
- [Efficient Parameter Optimisation for Quantum Kernel Alignment: A Sub-sampling Approach in Variational Training](https://mlsanity.com/paper/2401.02879/) (2024)
- [In Search of Quantum Advantage: Estimating the Number of Shots in Quantum Kernel Methods](https://mlsanity.com/paper/2407.15776/) (2024)
- [Shot-frugal and Robust quantum kernel classifiers](https://mlsanity.com/paper/2210.06971/) (2022)

## Built on by (most cited first, 3 of 3)

- [Adaptive Measurement Allocation for Learning Kernelized SVMs Under Noisy Observations](https://mlsanity.com/paper/2605.22275/) (2026)
- [Active Quantum Kernel Acquisition for Gaussian Process Regression](https://mlsanity.com/paper/2606.28833/) (2026)
- [Statevector-to-Hardware Reconstruction of a Four-Qubit ZZ Quantum Kernel: A Single-Backend Case Study of Three Execution Jobs](https://mlsanity.com/paper/2607.20377/) (2026)

## Abstract (arXiv)

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).