Skip to content
Preprint

Adaptive Low-Rank Quantum Kernel Acquisition under Finite-Shot Measurements: Perturbation Guarantees for QSVMs

Nov 2026 · 0 citations · 29 references
Engineering Computer Science

TL;DR

This work develops a non-asymptotic perturbation framework, ICAQKL, intended to enable measurement-efficient and theoretically controlled use of a selected quantum kernel, rather than to establish quantum advantage over classical kernels.

Abstract

Quantum kernel methods require estimating entries of a dense Gram matrix through repeated circuit measurements, making kernel construction expensive and statistically noisy. For a dataset of size $n$, dense construction requires $O(n^2)$ kernel queries, while existing approximation methods typically assume inexpensive access to kernel entries or use non-adaptive sampling. We study adaptive low-rank quantum kernel acquisition when the kernel is accessible only through a finite-shot quantum overlap oracle. Our framework, ICAQKL, uses residual-driven incomplete Cholesky construction to acquire informative kernel columns sequentially and form a positive-semidefinite rank-$r$ surrogate, reducing the training-kernel acquisition cost to $O(nrN_s)$ circuit executions for $r\ll n$, where $N_s$ is the number of shots per queried entry. The central difficulty is that finite-shot errors perturb both the queried kernel values and the adaptive pivot sequence that determines the low-rank factor. We develop a non-asymptotic perturbation framework for this stochastic adaptive process, establishing concentration over the realized queries, stability of noisy pivot selection and factor construction, and propagation of the coupled sampling and approximation errors to the QSVM objective, optimizer, prediction function, and classification margin. The resulting rank--shot conditions characterize when ICAQKL approaches the full QSVM induced by the same quantum feature map. Experiments on benchmark and biomedical datasets show favorable accuracy--query-cost tradeoffs, competitive performance with the full QSVM, and competitive or improved performance relative to the evaluated Nystr\"om baselines under comparable settings. ICAQKL is intended to enable measurement-efficient and theoretically controlled use of a selected quantum kernel, rather than to establish quantum advantage over classical kernels.

View source

Similar papers

Preprint Oct 2026

Reduced Cost Quantum Kernel Training

Quantum kernel methods are promising for near-term quantum machine learning, but their training costs are driven by the quadratic scaling of Gram-matrix construction and the measurement cost of estimating individual kernel values. In this work, we investigate one-class anomaly detection as a resource-efficient operatin...

Daniel R. Germain, Benjamin Goldweber, Kayla J. Rodriguez et al. · 0 citations
Preprint Oct 2026

Prototype-Guided Optimization of Quantum Data Embeddings with Linear Cost

In supervised quantum machine learning with classical data, classification performance critically depends on the geometry induced by quantum data embedding. Existing data-adaptive approaches rely on pairwise fidelity evaluations between samples, which scale as $O(B^2)$ for $B$ samples and create a computational bottlen...

Seokhoon Jeong, Daniel K. Park · 0 citations
Preprint Oct 2026

Who can sample forever? Shot noise effects in quantum linear regression

Quantum fidelity kernels and quantum extreme learning machines share the same basic architecture: a fixed quantum device generates features that are combined through a classically trained linear model. We refer to this broad non-variational setting as quantum linear regression. A defining aspect of these models is that...

G. Lo Monaco, S. Lorenzo, A. Ferraro et al. · 1 citation
Preprint Oct 2026

Nearly Optimal Quantum Sample Complexity of Learning Fourier-Sparse Boolean Functions

We study the number of uniform quantum examples needed to exactly learn a Boolean function with at most $k$ nonzero Fourier coefficients. We give a learner with near-optimal $\widetilde{O}(k)$ sample complexity independent of the input length $n$. The learner uses only separate measurements of individual examples. This...

Ze-Kun Ye · 0 citations
#machine learning Preprint Oct 2026

Empirical Evaluation of Quantum Kernel Methods for Classification: A Comparative Study with Classical Kernels

Quantum kernel methods are the most concrete near-term proposal for quantum machine learning on classical data, yet published benchmarks disagree on whether they outperform tuned classical kernels, and the disagreement cannot be resolved from the literature because the comparisons are not protocol-controlled. We argue...

Ronak Bhalgami · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.