The Inductive Bias of Quantum Kernels

Jonas M. Kübler, Simon Buchholz, Bernhard Schölkopf

Introduction

Quantum computers can access exponentially large feature spaces, but this "superpower" is a double-edged sword. Without the right inductive bias, these models fail to generalize from finite data. This paper proves that for a quantum kernel to offer a real advantage, it must be specifically "biased" toward the problem at hand. While this is often classically hard to simulate, failing to do so risks running into "Barren Plateaus" where the kernel becomes impossible to measure efficiently.

The Problem: Expressivity vs. Generalization

In the quest for "quantum advantage," researchers have increasingly turned to Quantum Machine Learning (QML). One popular approach uses quantum kernels, where data is embedded into a high-dimensional quantum state space (Hilbert space) to find patterns that classical computers cannot easily detect.

However, there is a fundamental tension in machine learning: the more "expressive" a model is (i.e., the more functions it can represent), the harder it is to learn the right function from a limited amount of data—a concept rooted in the "No Free Lunch" theorem. The authors address a critical gap in QML literature: Does the massive dimensionality of quantum Hilbert space actually help us learn, or does it just lead to overfitting? They seek to formalize what kind of "inductive bias" (the set of assumptions a model makes about the data) is necessary for a quantum computer to outperform a classical one.

Methods and Approach

The authors analyze the spectral properties of quantum kernels using the framework of Kernel Ridge Regression (KRR). Their approach includes a rigorous spectral analysis, examining the eigenvalues and eigenfunctions of the integral operator associated with quantum kernels. A "good" kernel has its largest eigenvalues aligned with the target function.

To combat the "too much space" problem inherent to quantum embeddings, they introduce "projected kernels" that only look at a subset of qubits, effectively reducing the size of the feature space and enforcing a specific bias.

Quantum circuits illustrating (a) data generation, (b) the full quantum feature state, and (c) the projected (biased) quantum feature state.

The paper relies on mathematical proofs to establish two main theorems:

  • Theorem 1 shows that if a quantum embedding is too expressive (high diversity/low purity), the model will fail to generalize unless the dataset size is also exponential.
  • Theorem 2 explores the behavior of kernels under random unitary transformations, showing that generic quantum kernels tend to look like constant functions with exponentially small fluctuations.

To test these theories, the authors use synthetic quantum-generated datasets. They generate labels using a quantum circuit (applying a random unitary and measuring a single qubit). This creates a "ground truth" that is naturally represented in a quantum feature space but is conjectured to be exponentially hard for classical computers to approximate.

Key Insights

  • The Expressivity Trap: Simply having an exponentially large feature space is not an advantage; it’s a liability. If the kernel is too "flat" (all eigenvalues are small and equal), the model cannot distinguish signal from noise.
  • Inductive Bias is the Secret Sauce: A quantum advantage only occurs if we can encode specific knowledge about the problem into the quantum circuit. If the target function lies in a low-dimensional subspace of the Hilbert space that is classically hard to compute, the quantum model wins.
  • The Measurement Wall: There is a "Barren Plateau" for kernels. As you add more qubits, the difference between the kernel values for different data points shrinks exponentially. To tell them apart, you would need an exponential number of measurements, potentially negating any computational speedup.

Key Results: The Power of Projection

The empirical results strongly support the theoretical claims. Theorem 1 rigorously proves that "generic" quantum kernels—those that spread data too thinly across the Hilbert space—cannot learn any function with a polynomial number of samples.

In experiments scaling up to $d=7$ qubits, the biased kernel (which was designed to look at the relevant subset of qubits) achieved near-zero Mean Squared Error (MSE). In stark contrast, both the full quantum kernel and the classical RBF kernel failed to generalize as the number of qubits increased, essentially "overfitting" to the noise.

Left: Eigenvalues of the biased kernel remain stable. Right: The biased kernel maintains low test error as qubits increase, whereas full quantum and classical RBF kernels fail to generalize.

This success is explained by spectral concentration. The biased kernel showed a clear "spectral bias," where a few principal components captured almost all the information (seen in the stable eigenvalues). Meanwhile, the other kernels had "flat" spectra, making learning practically impossible.

Limitations and Future Work

The authors offer a somewhat "sobering" conclusion: finding the right inductive bias for classical datasets is an open and difficult problem. We do not yet have a reliable "recipe" for building quantum kernels for non-quantum data (like images or text), where classical biases like translation invariance are already well-understood and efficiently implemented.

Furthermore, the paper highlights that even if a perfect biased kernel exists, the precision required to evaluate it might grow exponentially with the number of qubits. Future directions point toward exploring specific mathematical problems (like the discrete logarithm) or data derived directly from physical quantum processes as the most promising areas for demonstrating a practical quantum advantage in machine learning.

Summary updated

Abstract

It has been hypothesized that quantum computers may lend themselves well to applications in machine learning. In the present work, we analyze function classes defined via quantum kernels. Quantum computers offer the possibility to efficiently compute inner products of exponentially large density operators that are classically hard to compute. However, having an exponentially large feature space renders the problem of generalization hard. Furthermore, being able to evaluate inner products in high dimensional spaces efficiently by itself does not guarantee a quantum advantage, as already classically tractable kernels can correspond to high- or infinite-dimensional reproducing kernel Hilbert spaces (RKHS). We analyze the spectral properties of quantum kernels and find that we can expect an advantage if their RKHS is low dimensional and contains functions that are hard to compute classically. If the target function is known to lie in this class, this implies a quantum advantage, as the quantum computer can encode this inductive bias, whereas there is no classically efficient way to constrain the function class in the same way. However, we show that finding suitable quantum kernels is not easy because the kernel evaluation might require exponentially many measurements. In conclusion, our message is a somewhat sobering one: we conjecture that quantum machine learning models can offer speed-ups only if we manage to encode knowledge about the problem at hand into quantum circuits, while encoding the same bias into a classical model would be hard. These situations may plausibly occur when learning on data generated by a quantum process, however, they appear to be harder to come by for classical datasets.
BibTeX
@inproceedings{kubler2021inductive,
  author = {Jonas M. Kübler and Simon Buchholz and Bernhard Schölkopf},
  title = {{The Inductive Bias of Quantum Kernels}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=yeUytNH7jXn},
}
Figure