Technical Summary: AQKA: Active Quantum Kernel Acquisition Under a Shot Budget

1. Problem Statement

Quantum kernel methods, which map classical inputs to a quantum feature space to compute fidelities $K(x_i, x_j) = |\langle \phi(x_j)|\phi(x_i)\rangle|^2$, are among the most accessible workloads for Noisy Intermediate-Scale Quantum (NISQ) hardware. However, their practical deployment is bottlenecked by measurement costs. Estimating an $N \times N$ kernel matrix requires $\Theta(N^2 S)$ circuit executions (shots), where $S$ is the number of shots per entry to achieve a desired precision. On current hardware, where circuit latencies range from milliseconds to seconds, this scaling limits deployable problem sizes to the low hundreds.

Existing budget-saving strategies (e.g., Nyström-QKE, ShoFaR, kernel-target alignment) address this by sub-sampling which entries to measure (e.g., selecting landmark columns or training points). However, these methods typically allocate the shot budget uniformly within their chosen subsets. They fail to account for the heterogeneity of how much each specific kernel entry contributes to the downstream classifier's performance. The core unanswered question is: given a fixed shot budget $B$, how should shots be allocated at the pair level to minimize the loss of the downstream task?

2. Methodology: AQKA

The authors formulate shot-budgeted quantum kernel learning as an optimization problem minimizing the expected loss $\mathbb{E}[L(\hat{K})]$ subject to a total shot budget constraint $\sum s_{ij} \leq B$.

Theoretical Derivation

Using a first-order analysis (Delta method) combined with Karush-Kuhn-Tucker (KKT) conditions, the authors derive a closed-form optimal allocation rule. For a kernel entry $K_{ij}$ estimated with $s_{ij}$ shots, the variance is $K_{ij}(1-K_{ij})/s_{ij}$. The optimal allocation $s^*_{ij}$ that minimizes the variance of the loss estimator is proportional to the sensitivity of the loss to that entry:
$$s^*_{ij} \propto |g_{ij}| \sqrt{K_{ij}(1-K_{ij})}$$
where $g_{ij} = \partial L / \partial K_{ij}$ is the gradient of the loss with respect to the kernel entry.

• For Kernel Ridge Regression (KRR): The gradient is derived explicitly as $g_{ij} = -2\lambda^2(\beta_i \alpha_j + \beta_j \alpha_i)$, where $\alpha = (K+\lambda I)^{-1}y$ and $\beta = (K+\lambda I)^{-1}\alpha$.
• For Support Vector Machines (SVM): Using the envelope theorem (Danskin's theorem), the gradient is derived as $g_{ij} = -y_i y_j \eta^*_i \eta^*_j$, where $\eta^*$ are the optimal dual variables.

Algorithmic Implementation

The authors propose AQKA (Active Quantum Kernel Acquisition), a deployable algorithm that operates in rounds:

1. Warm-up: A small fraction of the budget ($\eta_w B$) is spent uniformly to seed an initial kernel estimate $\hat{K}$.
2. Sensitivity Estimation: The algorithm solves the KRR (or SVM) problem on $\hat{K}$ to compute the gradient-based sensitivity scores $g_{ij}$.
3. Target-Fill Allocation: Instead of sampling shots from a multinomial distribution (which can starve low-sensitivity pairs due to stochastic spikes), AQKA uses a deterministic "target-fill" approach. It calculates the target shot count $s^*_{ij}$ and adds the difference $\max(0, s^*_{ij} - s_{ij})$ to each pair.
4. Exploration: A small exploration fraction ($\eta_e B$) is added uniformly to prevent the algorithm from completely ignoring pairs that might become important due to higher-order effects or estimation noise.

3. Key Contributions

1. Complete Regime Decomposition

The paper provides a principled characterization of when different allocation strategies are optimal:

• AQKA dominates in the budget-limited regime ($B \lesssim 16 n_{pairs}$) on sparse-sensitivity KRR tasks.
• Nyström-QKE (low-rank reconstruction) wins at saturating budgets on planted-sparse data, where the low-rank structure can be fully recovered.
• ShoFaR-style methods are competitive only in extreme low-budget regimes.

2. Closed-Form Pair-Level Acquisition Theory

• KKT-Optimal Allocation: Derivation of the closed-form gradient $g_{ij}$ for KRR and SVM under shot noise.
• Corrected Sparsity-Aware Bounds: The authors derive a Cauchy-Schwarz bound for the achievable variance reduction ratio $\rho$. They correct the naive $\Theta(m^2/N^2)$ scaling (assuming $g$ is supported on $S \times S$) to a more accurate $\Theta(m/N)$ scaling ($\rho \leq 2m/N$ for KRR). This reflects the structural fact that even if the solution vector $\alpha$ is sparse, the sensitivity vector $\beta = (K+\lambda I)^{-1}\alpha$ is generically dense, meaning any pair touching the support set has non-zero sensitivity.
• Regret Bounds: An explicit-constant plug-in regret bound is provided, showing that the error converges to the oracle optimum as the warm-up budget increases.

3. Deployable Target-Fill Algorithm

The paper demonstrates that a deterministic target-fill scheme outperforms natural multinomial sampling, particularly in the budget-limited regime. Multinomial sampling tends to concentrate aggressively on a few high-score pairs, starving others and amplifying noise in the matrix inversion; target-fill maintains a minimum coverage floor.

4. First Multi-Seed Live Online Adaptation on Quantum Hardware

The authors report the first published demonstration of online adaptive shot allocation on current 156-qubit IBM Heron-class devices.

• IBM Aachen (N=20): +17.0 ± 4.8 percentage points over uniform allocation (3.5$\sigma$ significance).
• IBM Berlin (N=30): +14.0 ± 8.5 percentage points at higher budgets.

4. Experimental Results

Synthetic and Simulated Settings

• Planted-Sparse KRR: On synthetic data with sparse solution vectors, AQKA (target-fill with estimated sensitivity) achieves +8 to +25 percentage points over uniform allocation as $N$ scales from 225 to 1000.
• Noiseless Quantum Kernels: The gains transfer to noiseless 4-qubit ZZFeatureMap simulations, showing +13 to +18 points over uniform.
• Hardware-Resampling Ablation: Using a kernel measured on IBM Pittsburgh (156 qubits) and resampling with shot noise, AQKA achieves +26.3 ± 6.1 points at $B = n_{pairs}$ and +31.9 ± 7.2 points at $B = 4n_{pairs}$ over uniform.

Real-Data Benchmarks

• Breast Cancer (Dense $\alpha$): On a real-world dataset where the solution vector is dense (not sparse), AQKA does not uniformly dominate. It is competitive but shows regime-dependent performance, highlighting that the method's advantage relies on high pair-level sensitivity heterogeneity.
• SVM vs. KRR: The paper notes that while the theoretical framework extends to SVM, the plug-in version is more brittle due to the instability of the support set under noisy warm-ups. In small-N, noisy-warm-up regimes, AQKA for SVM can underperform uniform allocation, whereas the KRR version remains robust.

5. Significance and Claims

The paper claims to close the gap between theoretical shot-budget optimization and practical deployment on NISQ hardware. Its primary significance lies in:

1. Moving beyond uniform allocation: Demonstrating that non-uniform, sensitivity-aware shot allocation is critical for near-term quantum kernel learning, especially when budgets are tight.
2. Hardware Validation: Providing the first multi-seed, live-online validation of an adaptive shot allocation strategy on real quantum hardware, proving that the theoretical gains survive device noise and calibration drift.
3. Regime Awareness: Establishing that no single method is universally superior; AQKA is specifically designed for the budget-limited, sparse-sensitivity regime, which is the operationally relevant zone for current hardware.

The authors are modest in their claims, acknowledging that for dense-sensitivity problems or saturating budgets, other methods (like Nyström) or uniform allocation may be preferable. They also identify the SVM plug-in noise as a current limitation requiring future work (e.g., margin-stabilized acquisition).