cs.LGJun 18, 2026

Effective Dimension Governs Generalization in Quantum Kernel Vision Models

Authors: Jian XuDelu ZengJohn PaisleyQibin Zhao

Abstract

Recent quantum vision models-quantum vision transformers and quantum convolutional networks-report two striking but unexplained empirical phenomena: (i) ansatze with more, or more uniformly distributed, entanglement generalize better, and (ii) injecting quantum noise can improve test accuracy rather than degrade it. These observations are currently treated as curiosities, discovered by grid search and explained, if at all, by hand. We show that both are manifestations of a single, measurable quantity: the \emph{effective dimension} deffd_{\rm eff} of the (noise-shaped) quantum feature kernel. Working primarily with quantum-kernel vision models-a quantum feature map read out by a kernel classifier-we give a spectral account in which entanglement structure and quantum noise are two knobs that move deffd_{\rm eff}; in an overfitting regime, contracting deffd_{\rm eff} acts as ridge-like regularization. We analyze the mechanism: an \emph{exact} decomposition of the depolarized kernel Kp=(1p)2K+p(2p)D11K_p=(1-p)^2K+\tfrac{p(2-p)}{D}\mathbf{1}\mathbf{1}^\top with deff(Kp)1d_{\rm eff}(K_p)\to1, a contraction result (and its boundary) for amplitude damping, a kernel-machine capacity bound, and a capacity/alignment risk decomposition; the monotone contraction operative in our entangled experiments is verified empirically, not proven in general. Along the one-parameter depolarizing family the collapse is instead exact by construction; we use it only to confirm the kernel decomposition to machine precision and at up to 1212 qubits, not as evidence for deffd_{\rm eff}. Amplitude damping contracts deffd_{\rm eff} and lifts test accuracy by up to +13%+13\% along an inverted-U sweet spot; the effect's sign flips between the over- and under-fitting regimes; noise injection matches an explicit spectral-filtering frontier. Our results organize two reported anecdotes into a single measurable principle for designing quantum-vision models.

Explore similar work

Aug 31, 2026quant-ph

Fractal dimension predicts quantum kernel collapse in angle-encoded data

Angle-encoded quantum kernels on tabular data collapse when the feature map is wider than the intrinsic dimension of the data. We propose the correlation fractal dimension D2 as an a priori qubit budget: encode D2 coordinates chosen by FD-ASE instead of the PCA-95% width or all E attributes. On nine data sets and a statevector simulator (n= 32), a one-layer ZZ fidelity kernel at q=D2 stays geometrically alive while the same kernel at the PCA-95% width has already collapsed. The budget is map-dependent: product-state and IQP maps overshoot it; a second ZZ layer undershoots it. Packed dense-angle and re-uploading encodings still live at the fractal q, but not when PCA-95% features are stacked onto those qubits. Shrinking the angle bandwidth moves the ZZ knee later; stretching it kills the kernel earlier. On IBM Quantum (ibm_fez, 256 shots, n=8) the one-layer ZZ kernel at the fractal width matches the exact kernel (MAE 0.021); past that width both hardware and simulator have collapsed. The ceiling is a property of the map-data pair at a stated bandwidth, not of the classical table alone.
Ana Paula Appel
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 i=1Nαik(x,xi)\sum_{i=1}^N α_i k(x,x_i) of NN 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α22/ε2)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(α1/ε)O(\lVertα\rVert_1/\varepsilon), removing the dependence on NN from the query count and yielding a quadratic improvement in both α1\lVertα\rVert_1 and ε\varepsilon. We prove a matching lower bound of Ω(α1/ε)Ω(\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
May 14, 2026cs.LG

AQKA: Active Quantum Kernel Acquisition Under a Shot Budget

Estimating an N×NN \times N quantum kernel from circuit fidelities requires Θ(N2S)Θ(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 (B16npairsB \lesssim 16 n_{\mathrm{pairs}}) on sparse-sensitivity KRR, with the gap \emph{growing} from +8+8 to +25+25 pts over uniform as NN scales 2251000225{\to}1000 and reaching +26+26--3232 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}: sijgijKij(1Kij)s_{ij}^{\star} \propto |g_{ij}|\sqrt{K_{ij}(1-K_{ij})} with explicit gradient gijg_{ij} for KRR (Lemma1, βiαj+βjαiKij(1Kij)|β_iα_j+β_jα_i|\sqrt{K_{ij}(1-K_{ij})}) and SVM via the envelope theorem (ηiηjKij(1Kij)|η_i^*η_j^*|\sqrt{K_{ij}(1-K_{ij})}); a \emph{corrected} sparsity-aware Cauchy--Schwarz rate ρ2m/Nρ\le 2m/N matching empirics (vs.\ the naive m2/N2m^2/N^2); an explicit-constant plug-in regret bound (Theorem2); and a tighter SVM ceiling ρSVMmsv2/N2ρ^{\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±4.8+17.0 \pm 4.8 pts at N=20N{=}20 on \texttt{ibm_aachen} (3.5σ3.5σ, 5 seeds), with the advantage holding at N=30N{=}30 at higher budget on \texttt{ibm_berlin} (+14.0±8.5+14.0 \pm 8.5 pts, 5 seeds).
Jian Xu, Chao Li, Delu Zeng +2