AQKA: Active Quantum Kernel Acquisition Under a Shot Budget

Jian Xu; Chao Li; Delu Zeng; John Paisley; Qibin Zhao

cs.LGMay 14, 2026

AQKA: Active Quantum Kernel Acquisition Under a Shot Budget

Authors: Jian Xu, Chao Li, Delu Zeng, John Paisley, Qibin Zhao

Organizations: 1RIKEN iTHEMS · 2RIKEN AIP · 3South China University of Technology · 4Columbia University

Abstract

Estimating an $N \times N$ quantum kernel from circuit fidelities requires $Θ(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 16 n_{\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 (Lemma1, $|β_iα_j+β_jα_i|\sqrt{K_{ij}(1-K_{ij})}$ ) and SVM via the envelope theorem ( $|η_i^*η_j^*|\sqrt{K_{ij}(1-K_{ij})}$ ); a \emph{corrected} sparsity-aware Cauchy--Schwarz rate $ρ\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 $ρ^{\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σ$ , 5 seeds), with the advantage holding at $N{=}30$ at higher budget on \texttt{ibm_berlin} ( $+14.0 \pm 8.5$ pts, 5 seeds).

Explore similar work

Jun 27, 2026cs.LG

Active Quantum Kernel Acquisition for Gaussian Process Regression

Quantum kernel estimation on near-term hardware is shot-budgeted: every entry of the kernel Gram matrix is a Bernoulli expectation that must be sampled with a finite number of circuit executions. Recent work on quantum kernel classification has shown that allocating shots non-uniformly across kernel entries, weighted by their downstream task sensitivity, can reduce the shot budget required to reach a target accuracy. We extend this idea to Gaussian process (GP) regression, a setting whose downstream quantities (full-spectrum posterior variance, log-determinant, marginal likelihood) couple to kernel error more tightly than the sign-only outputs of classification. We derive three closed-form pair-level sensitivities predictive coupling

|α_iα_j|

, leave-one-out residual, and marginal-likelihood gradient and plug them into a Neyman-style minimum-variance allocation rule. To prevent catastrophic over-concentration when the warm-up sensitivity estimate is itself noisy, we add a high uniform coverage floor justified by a Frobenius lower bound on the missing-entry perturbation. On four UCI benchmarks and two synthetic RBF + Bernoulli controlled studies, the resulting allocator delivers

10

21\%

test-RMSE improvement over uniform allocation across the moderate-budget regime. The gain transfers (i) to genuine ZZ and Pauli-Z quantum kernels on quantum-natural data (

-13

15\%

at low budget,

p<0.05

paired) and (ii) to four downstream tasks (Bayesian quadrature, heteroscedastic regression, hyperparameter learning, multi-output Cokriging). On UCI features embedded into a ZZ kernel the gain disappears, consistent with the exponential-concentration regime where shot allocation has nothing to exploit.

Jian Xu, Artur Miroszewski, John Paisley +2

Quantum Kernels Gaussian Process Graphics Processing Unit Kernels Gibbs Measures Bayesian Quadrature Posterior+2

Ask PDF

Apr 16, 2026quant-ph

Optimal algorithmic complexity of inference in quantum kernel methods

Quantum kernel methods are among the leading candidates for achieving quantum advantage in supervised learning. A key bottleneck is the cost of inference: evaluating a trained model on new data requires estimating a weighted sum

\sum_{i=1}^N α_i k(x,x_i)

N

kernel values to additive precision

\varepsilon

, where

α

is the vector of trained coefficients. The standard approach estimates each term independently via sampling, yielding a query complexity of

O(N\lVertα\rVert_2^2/\varepsilon^2)

. In this work, we identify two independent axes for improvement: (1) How individual kernel values are estimated (sampling versus quantum amplitude estimation), and (2) how the sum is approximated (term-by-term versus via a single observable), and systematically analyze all combinations thereof. The query-optimal combination, encoding the full inference sum as the expectation value of a single observable and applying quantum amplitude estimation, achieves a query complexity of

O(\lVertα\rVert_1/\varepsilon)

, removing the dependence on

N

from the query count and yielding a quadratic improvement in both

\lVertα\rVert_1

and

\varepsilon

. We prove a matching lower bound of

Ω(\lVertα\rVert_1/\varepsilon)

, establishing query-optimality of our approach up to logarithmic factors. Beyond query complexity, we also analyze how these improvements translate into gate costs and show that the query-optimal strategy is not always optimal in practice from the perspective of gate complexity. Our results provide both a query-optimal algorithm and a practically optimal choice of strategy depending on hardware capabilities, along with a complete landscape of intermediate methods to guide practitioners. All algorithms require only amplitude estimation as a subroutine and are thus natural candidates for early-fault-tolerant implementations.

Elies Gil-Fuster, Seongwook Shin, Sofiene Jerbi +2

Quantum Kernels Quantum Advantage Optimal Sample Complexity Inference Engine Optimality

Ask PDF

Apr 20, 2026quant-ph

Benchmarking Quantum Kernel Support Vector Machines Against Classical Baselines on Tabular Data: A Rigorous Empirical Study with Hardware Validation

Quantum kernel methods have been proposed as a promising approach for leveraging near-term quantum computers for supervised learning, yet rigorous benchmarks against strong classical baselines remain scarce. We present a comprehensive empirical study of quantum kernel support vector machines (QSVMs) across nine binary classification datasets, four quantum feature maps, three classical kernels, and multiple noise models, totalling 970 experiments with strict nested cross-validation. Our analysis spans four phases: (i) statistical significance testing, revealing that none of 29 pairwise quantum-classical comparisons reach significance at

α= 0.05

; (ii) learning curve analysis over six training fractions, showing steeper quantum slopes on six of eight datasets that nonetheless fail to close the gap to the best classical baseline; (iii) hardware validation on IBM ibm_fez (Heron r2), demonstrating kernel fidelity

r \geq 0.976

across six experiments; and (iv) seed sensitivity analysis confirming reproducibility (mean CV 1.4%). A Kruskal-Wallis factorial analysis reveals that dataset choice dominates performance variance (

\varepsilon^2 = 0.73

), while kernel type accounts for only 9%. Spectral analysis offers a mechanistic explanation: current quantum feature maps produce eigenspectra that are either too flat or too concentrated, missing the intermediate profile of the best classical kernel, the radial basis function (RBF). Quantum kernel training (QKT) via kernel-target alignment yields the single competitive result -- balanced accuracy 0.968 on breast cancer -- but with ~2,000x computational overhead. Our findings provide actionable guidelines for quantum kernel research. The complete benchmark suite is publicly available to facilitate reproduction and extension.

Siavash Kakavand, Christoph Strohmeyer, Michael Schlotter

Quantum Kernels Hybrid Quantum Neural Networks Tabular Data

Ask PDF