PaperlayerView exact revision on arXiv

Source-linked AI summary

The Inductive Bias of Quantum Kernels

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

arXiv:2106.03747v2quant-phstat.ML

TL;DR

Quantum kernels may provide a learning advantage by encoding a low-dimensional inductive bias containing functions that are classically hard to compute, but expressive quantum feature spaces make generalization difficult. The paper analyzes kernel spectra and shows that suitable bias can help when the target class is known, while kernel estimation may require exponentially many measurements. It concludes that substantial advantages are not indicated for supervised learning on classical datasets.

  • Problem

    Quantum kernels can efficiently evaluate inner products in exponentially large spaces, but high-dimensional feature spaces complicate generalization and do not by themselves establish quantum advantage.

  • Method

    The paper analyzes the spectral properties of quantum-kernel RKHSs and studies how projecting kernels encodes inductive bias.

  • Results

    The analysis finds an exponential advantage when the target is known to come from a single-qubit observable and the RKHS is constrained accordingly.

  • Takeaways & Limitations

    Quantum advantage appears to require problem knowledge that can be encoded in a quantum model but not efficiently in a classical one.

  • Takeaways & Limitations

    Biased-kernel estimation can require exponentially many measurements, while quantum neural networks can suffer from exponentially vanishing gradients.

Abstract

from arXiv · show

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.

1 Introduction

The paper frames quantum advantage in machine learning as a question of inductive bias rather than quantum speedups for generic computation. It analyzes quantum kernels spectrally, finding that expressive embeddings can harm generalization while suitable projections may encode classically difficult biases, although estimating them can require exponentially many measurements.

  • Motivation: Quantum machine learning may offer an advantage when its model encodes an inductive bias that is hard to implement efficiently classically and matches the dataset.The paper relates this possibility to the no free lunch principle: a bias that helps one problem can hurt another.
  • Contributions: The paper analyzes quantum-kernel inductive bias through the spectral properties of the associated function spaces.Its main analysis concerns how the kernel spectrum affects generalization and learnability.
  • Contributions: Overly expressive data embeddings can prevent quantum kernel methods from generalizing effectively.The paper identifies this failure as a theorem-level result and contrasts it with appropriately projected kernels.
  • Contributions: Appropriately projecting a quantum kernel can create an inductive bias that is difficult to construct classically.This projection is presented as a route to a quantum advantage when the target function fits the resulting restricted class.
  • Limitations: Estimating a suitably biased quantum kernel may require exponentially many measurements, paralleling barren-plateau difficulties in quantum neural networks.The paper reports experiments supporting its main theoretical claims.
  • Conclusion: The paper gives no recipe for quantum advantage on classical datasets and conjectures that an advantage requires knowledge of a quantum-describable data-generating process.The same useful bias must be hard to encode efficiently in a classical model.

2 Supervised learning

This section formulates supervised regression and kernel ridge regression in RKHSs, then uses kernel spectra to explain how regularization and eigenstructure create inductive bias. It identifies strong alignment between the target and dominant eigenfunctions as a simple route to learnability, including a one-eigenvalue quantum-advantage construction.

  • Supervised learning: Supervised regression models data as Y = f*(X) + ε and seeks a function minimizing expected prediction risk from n i.i.d. observations.The inputs lie in X ⊂ R^d, outputs in R, and ε is zero-mean noise.
  • Kernel ridge regression: Kernel ridge regression optimizes empirical risk plus λ times the squared RKHS norm, producing a convex kernel-based learning problem.The Representer Theorem reduces the solution to a combination of kernel evaluations on the training data.
  • Spectral properties: The kernel integral operator has eigenvalues γ_i and orthonormal eigenfunctions φ_i that determine the kernel’s spectral structure.The kernel can be decomposed using these eigenvalues and eigenfunctions, which define its function-space bias.
  • Kernel ridge regression: Larger regularization emphasizes principal components with the largest eigenvalues, whereas smaller regularization fits more components but risks overfitting noise.Choosing λ balances the bias-variance tradeoff.
  • Inductive bias: A target function is easiest to learn when it aligns with a kernel’s principal components, especially when the kernel has one nonzero eigenvalue.The paper identifies k(x, x′) = f(x)f(x′) as the simplest such construction.
  • Inductive bias: A scalar function that is quantum-computable but classically exponential yields an exponential learning advantage under k(x, x′) = f(x)f(x′).The data are generated as Y = f(X) + ϵ, and the kernel directly captures the target function.
  • Alignment measures: Kernel-target alignment measures how well a kernel fits the target, while task-model alignment measures how much signal lies in the first i principal components.Learning becomes harder when target signal is spread across many eigenfunctions.

3 Quantum computation in machine learning

Quantum machine-learning models use exponentially large quantum state spaces to define function classes, with quantum kernels providing a convex nonparametric alternative to parametrized quantum neural networks. Their practical promise is limited by measurement costs and, for quantum neural networks, non-convex optimization with vanishing gradients.

  • Quantum-kernel evaluation: The exponential quantum state space can make general expressions classically hard, but measurement requirements can prevent this computational power from being easily harnessed.The paper treats measurement as a central practical obstacle rather than assuming state-space size alone guarantees an advantage.
  • Quantum function classes: Quantum machine-learning function classes are built from quantum states generated by data-dependent unitary transformations and measurements of observables.The quantum state space grows exponentially with the number of qubits d.
  • Quantum neural networks: Quantum neural networks define a parametric function class through variational circuits whose observables depend on classical parameters.Their optimization is generally non-convex and can suffer from exponentially vanishing gradients.
  • Quantum kernels: Quantum kernels define a nonparametric RKHS through k(x, x′) = Tr[ρ(x)ρ(x′)], making the learning objective convex.The quantum model supplies the kernel while classical optimization solves the resulting kernel-learning problem.
  • Quantum kernels: The Representer Theorem reduces optimization over an exponentially large function class to parameters whose dimension equals the training-set size.Because the ridge objective is convex, the optimization can be performed efficiently on a classical computer.
  • Quantum-kernel evaluation: Evaluating a quantum kernel requires estimating an overlap or measurement probability from finitely many circuit measurements.For pure-state encodings, the relevant probability is obtained after applying the inverse of one data-encoding transformation followed by the other.

4 The inductive bias of simple quantum kernels

The section analyzes how simple quantum kernels trade expressivity for generalization through their spectral structure and projected, biased embeddings. It shows that restricting the kernel can make learning feasible when the retained function class matches the target, while generic biased kernels may be impractical to estimate.

  • Expressivity and generalization: The RKHS of a d-qubit quantum state has dimension at most 4^d, while an m-qubit biased kernel has dimension at most 4^m.Learning is possible when the training sample size satisfies n ≳ 4^m ≥ dim(F).
  • Expressivity and generalization: Quantum kernels with exponentially large feature spaces cannot generally learn from polynomially many samples when their embeddings are too expressive.Theorem 1 links this failure to exponentially small leading eigenvalues and shows that generalization requires restricted embeddings.
  • Biased kernels: Projected kernels reduce the generalization gap but can increase approximation error unless the retained RKHS represents the target function.The reduction is useful as an inductive bias only when supported by knowledge of the data-generating process.
  • Spectral structure: For Haar-random projections, the averaged operator has one dominant constant-function eigenvalue and 4^m−1 much smaller eigenvalues.The dominant eigenvalue is 2^-m + O(2^-2d), while the remaining eigenvalues are 2^-m−d + O(2^-2d).
  • Spectral structure: The biased kernel can encode eigenfunctions conjectured to be exponentially hard to compute classically, whereas the constant-function bias can also be implemented classically.This creates the relevant quantum advantage only when the target lies in the quantum-accessible, classically hard part of the spectrum.
  • Practical limitation: Generic biased kernels require exponentially many measurements for exponential kernel accuracy, making learning beyond the constant function impractical for moderately large d.The limitation is related to barren-plateau behavior in quantum neural networks.

5 Experiments

The experiments test whether spectral bias improves learning when the target is generated by a single-qubit observable. The appropriately biased kernel aligns with the target and avoids the overfitting or underfitting seen with alternative kernels.

  • Experimental setup: The experiments use a single-qubit observable target, compare full, correctly biased, incorrectly biased, and radial-basis kernels, and vary the number of qubits.Labels include Gaussian noise with variance 10^-4, while the target variance is fixed across dimensions.
  • Regression results: As the number of qubits increases, the full and radial-basis kernels overfit, whereas the incorrectly biased kernel severely underfits.The incorrectly biased kernel does not significantly improve performance over the full kernel.
  • Alignment analysis: The biased kernel is the only kernel well aligned with the task in the centered kernel-target alignment experiments.The alignment is estimated over 50 random seeds, alongside task-model alignment.
  • Alignment analysis: The target function is completely expressed by the first four components of the biased kernel, while the other kernels require essentially their entire spectra.The sample size is 200, so the empirical kernel matrix is 200-dimensional; the incorrectly biased kernel has only four dimensions and cannot learn higher components.

6 Discussion

The discussion argues that quantum advantage depends on encoding a classically hard inductive bias tied to the data-generating process. It also emphasizes major practical limits: kernel evaluation may require exponentially many measurements, and strong biases for classical datasets remain unclear.

  • Discussion: Spectral properties, rather than RKHS dimensionality alone, determine whether quantum-kernel learning is feasible.Exponentially large RKHSs can have too little inductive bias, causing naive encodings to hinder learning unless datasets are exponentially large.
  • Discussion: The authors observe an exponential advantage when the target is known to come from a single-qubit observable and the RKHS is constrained accordingly.This advantage relies on information about the data-generating process that cannot be efficiently encoded classically.
  • Discussion: Evaluating the kernel can require exponentially many measurements, linking the limitation to barren-plateau phenomena in quantum neural networks.This measurement cost complicates finding suitable quantum kernels.
  • Discussion: For fully coherent quantum computers, it remains unclear how to encode a strong inductive bias for classical datasets, and the paper finds no indication of substantial supervised-learning gains on them.The paper suggests quantum-generated data may offer a more plausible setting for such biases.

Supplementary Material

The supplementary material defines the partial trace for a bipartite quantum system and verifies its key trace identity. The proof first treats tensor-product operators and then extends the result by linearity.

  • Partial trace: For a bipartite state space H1 ⊗ H2, the reduced state on H1 is obtained as ρ1 = Tr2[ρ12].The partial trace is characterized through its action against operators on H1 and H2.
  • Trace identity: The trace identity Tr[Tr2[S]T] = Tr[S(T ⊗ id)] is established for operators S on H1 ⊗ H2 and T on H1.The tensor-product form of the identity is shown explicitly before handling general operators.
  • Trace identity: For S = A ⊗ B, the identity follows because the trace of a tensor product factors into the product of the traces.The calculation yields Tr[AT]Tr[B] and then rewrites it as Tr[(A ⊗ B)(T ⊗ id)].
  • Trace identity: The result extends from tensor-product operators to arbitrary S by linearity of both sides.This completes the proof of the partial-trace relation used later.

B General results about RKHS

This material develops centering, tensor-product RKHSs, and quantum-kernel function spaces. It shows how centering removes the dominant constant component and how product-kernel spectra factorize, while quantum embeddings induce tensor-product and operator-based RKHS structures.

  • Centering in RKHS: Centering subtracts the data mean and removes the constant-function component from the kernel spectrum.For the biased kernel, the constant eigenvalue is set to zero while the other spectral terms remain invariant.
  • Centering in RKHS: The centered biased kernel retains the target’s centered component because that function is expressed through its eigenfunctions.When the three relevant eigenvalues are equal, kernel-target alignment can be analyzed directly from this representation.
  • Tensor products: For product kernels, the RKHS contains products f1(x1)f2(x2), and the integral-operator eigenvalues are pairwise products γ1γ2.The eigenvalue problems decouple under a product measure.
  • Quantum-kernel RKHS: A one-qubit embedding generates an RKHS from the embedding amplitudes, while the physical kernel produces functions of the form f·ḡ.Independent coordinate embeddings give the resulting RKHS a tensor-product structure.

C.2 Proof of Lemma 1

The proof relates the quantum kernel’s integral-operator spectrum to density-matrix and tensor-product structure, then characterizes the resulting eigenfunctions and RKHS.

  • Spectral correspondence: The eigenvalues of the non-physical kernel’s integral operator equal those of the mean density matrix.This identifies the kernel spectrum with the spectrum of a density operator associated with the data distribution.
  • Tensor-product structure: For product data measures and coordinate-wise qubit embeddings, the integral operator factorizes across dimensions, producing products of one-dimensional eigenvalues.The largest eigenvalue can therefore become exponentially small when each coordinate embedding has eigenvalues bounded below one.
  • Quantum-kernel eigendecomposition: The quantum-kernel eigenfunctions have the form f_i(x) = Tr[ρ(x)A_i], where A_i are orthonormal Hermitian matrices.The matrix-map eigendecomposition supplies both the eigenvalues and the corresponding functions.
  • Example RKHS: In the single-qubit example, the RKHS has dimension 4 when the relative phase varies, and its functions can be parametrized as a cos(x + b) + c.The phase condition makes the relevant feature components linearly independent.
  • Example RKHS: For d qubits, eigenfunctions are indexed by coordinate-wise trigonometric factors, with eigenvalue 2^-d−Σ_i(α_i+β_i) and degeneracy determined by the corresponding level.The indices satisfy α_i + β_i ≤ 1.

D Proof of Theorem 1

Theorem 1 is proved by combining a bound on the largest kernel eigenvalue with concentration and kernel-ridge-regression estimates under product measures.

  • Proof strategy: The proof reduces Theorem 1 to a result controlling learning when the largest integral-operator eigenvalue is small.Theorem 3 provides the intermediate learning bound used by the argument.
  • Eigenvalue bound: Under product measures, Lemma 1 gives γmax(d) ≤ δ^d/2 for a fixed δ < 1.This exponential decay is later compared with polynomial factors in the sample-size assumptions.
  • Asymptotic comparison: Because exponential decay dominates polynomial growth, sufficiently large d satisfies the bounds required by the theorem.The proof explicitly compares δ^d/2 with polynomial expressions involving ε, d, and l.
  • Probability conclusion: The probability estimates combine the intermediate theorem with the eigenvalue bounds to obtain an overall success probability of at least 1 − ε.The proof sets ε′ = ε/2 and combines two failure-probability terms.

E Proof of Theorem 2

Theorem 2 analyzes reduced density matrices and the averaged operator under random unitaries, showing concentration near a maximally mixed state and a simple operator spectrum.

  • Random-unitary model: The analysis uses Haar-measure moments, while the arguments only require unitary t-designs, including efficiently implementable 2-designs.Random Haar unitaries may require exponentially many gates, whereas the relevant designs can use polynomially many gates.
  • Projected kernel: The projected quantum kernel is introduced through a partial-trace decomposition separating the first m qubits from the remaining d − m qubits.Greek indices denote the retained subsystem and barred indices the traced-out subsystem.
  • Reduced-state concentration: For large d, the reduced density matrix ρ̃_V(x) is close to 2^-m id with high probability.The result follows from bounding the variance of its entries.
  • Operator spectrum: The averaged operator T is a multiple of the identity plus a rank-one perturbation, up to higher-order terms.This structure determines one distinguished eigenvector and a degenerate traceless subspace.
  • Operator spectrum: The leading eigenvalue is γ1 = 2^-m, with eigenvector given by the identity matrix, while traceless eigenvectors have eigenvalue 2^-m−d up to O(2^-2d) corrections.The identity direction corresponds to the constant function under the analyzed embedding.

F More on experiments

The experiments use idealized full-state simulations, compare implementation strategies and regularization choices, and examine how kernel alignment changes with qubit count.

  • Experimental setting: The experiments simulate the full quantum state and use exact quantum-kernel values, neglecting finite-measurement effects.This idealized setup omits the measurement difficulties discussed elsewhere in the paper.
  • Kernel evaluation: The biased kernels are evaluated from stored reduced density matrices, requiring n circuit simulations instead of n^2 when computing kernel entries individually.The stored 2 × 2 Hermitian matrices enable direct matrix products and traces.
  • Regularization: For higher-dimensional kernels, regularization strongly affects performance, whereas it matters little for biased kernels with four-dimensional RKHSs.The experiment sets λ = 0 for biased kernels and λ = 10^-3 for the higher-dimensional kernels.
  • Kernel alignment: Figure 5 reports kernel target alignment for d = 1, 3, 5, 7, and the estimated alignment correlates with learning performance in Figure 2.The additional histograms examine alignment as the number of qubits increases.
Loading 2106.03747v2…