Benign Overfitting with Quantum Kernels

Technical Summary: Benign Overfitting with Quantum Kernels

Problem Statement
Quantum kernel methods offer a potential pathway to quantum advantage by encoding classical data into high-dimensional Hilbert spaces via parameterized quantum circuits (PQCs). However, a significant challenge hinders their practical utility: the phenomenon of exponential concentration. As the number of qubits increases, highly expressive quantum kernels (such as the standard quantum fidelity kernel) tend to concentrate near zero, causing the kernel matrix to approach the identity matrix. This results in "spiky" behavior where the model fails to capture meaningful data correlations, leading to poor generalization despite interpolating training data. While regularization techniques (e.g., bandwidth tuning, dimensionality reduction) have been proposed to mitigate overfitting, they often treat concentration solely as a drawback rather than a feature that could be harnessed.

Methodology
The authors propose a novel construction called Local-Global Quantum Kernels, inspired by the concept of "benign overfitting" in classical machine learning and the "spiky-smooth" kernel decomposition. The core idea is to construct a kernel that combines two distinct components:

1. A Local Component: Derived from measurements on a small subsystem (reduced density matrices). This component retains a smooth structure, preserving non-trivial correlations between distinct inputs and supporting generalization.
2. A Global Component: Derived from measurements on the full quantum system. This component exhibits strong concentration effects, creating narrow "spikes" that enable the interpolation of training data.

The proposed kernel is defined as a weighted sum:
$$k_{LG}(x, z) = \lambda_L k_L(x, z) + \lambda_G k_G(x, z)$$
where $k_L$ is the local kernel and $k_G$ is the global kernel.

To facilitate theoretical analysis, the authors introduce a Separable Global Encoding scheme. In this setup, the total number of qubits $t$ is a multiple of a subsystem size $s$ ($t = q \cdot s$). The encoding unitary factorizes across $q$ blocks. Under this scheme, the global kernel becomes the $q$-th power of a base kernel ($k_G = k_B^q$), while the local kernel remains proportional to the base kernel ($k_L \propto k_B$). The resulting kernel takes the form:
$$k_{LG}(x, z) = \tilde{\lambda}_L k_B(x, z) + \lambda_G k_B(x, z)^q$$
As the parameter $q$ increases, the global component becomes increasingly spiky (localized), while the local component remains smooth.

Key Contributions

1. Local-Global Quantum Kernel Definition: The paper introduces a framework that explicitly decomposes quantum kernels into smooth (local) and spiky (global) components, creating a quantum analog of the spiky-smooth kernels proposed by Haas et al. [2023] for classical settings.
2. Theoretical Proof of Benign Overfitting: The authors prove that for a class of periodic, translation-invariant quantum fidelity kernels (specifically the cosine quantum kernel), ridgeless regression using the Local-Global kernel can exactly interpolate noisy training data while remaining statistically consistent. This demonstrates that the "spiky" nature of high-dimensional quantum kernels can be leveraged for interpolation without sacrificing generalization, provided a smooth local component is present.
3. Circuit Implementations: The paper provides concrete quantum circuit implementations for the Local-Global kernel, including:
   • A fully quantum implementation using a weighted sum of local and global observables on $t$ qubits.
   • A hybrid quantum-classical implementation that computes the base kernel on $s$ qubits and applies the power law classically, significantly reducing quantum resource requirements.
4. Empirical Validation: Experiments on synthetic and real-world datasets (e.g., the Airfoil dataset) demonstrate that the Local-Global kernel achieves interpolation of training data while maintaining low test error, outperforming standard ridgeless regression with the base kernel and, in some cases, matching or exceeding the performance of regularized ridge regression.

Results

• Phase Diagram of Overfitting: Numerical experiments in 1D illustrate a transition from poor bias-variance tradeoff (small $q$) to catastrophic overfitting (intermediate $q$) and finally to benign overfitting (large $q$), where the predictor interpolates data but remains smooth away from training points.
• Consistency: On synthetic data, the test Mean Squared Error (MSE) of the Local-Global ridgeless estimator converges to the noise level as the training size increases, confirming the theoretical consistency result. In contrast, ridgeless regression with the base kernel alone is shown to be inconsistent.
• Generalization: The Local-Global kernel successfully generalizes on real-world data while interpolating the training set, validating the hypothesis that the combination of local smoothness and global spikiness enables benign overfitting.

Significance
The paper claims to provide the first theoretical and empirical characterization of benign overfitting specifically for quantum kernels. By reframing the exponential concentration of quantum kernels not merely as a failure mode but as a mechanism for interpolation, the authors propose a design principle for quantum kernels that inherently promotes generalization. This work extends the scope of benign overfitting analysis beyond shrinking-bandwidth constructions in classical learning to quantum settings, utilizing power concentration of the global kernel component to achieve localization. The findings suggest that carefully designed quantum features can interpolate data without compromising predictive performance, offering a promising strategy for constructing effective quantum kernels in the NISQ era.