PaperlayerView exact revision on arXiv

Source-linked AI summary

Exponential concentration in quantum kernel methods

Supanut Thanasilp, Samson Wang, M. Cerezo, Zoë Holmes

arXiv:2208.11060v2quant-phcs.LGstat.ML

TL;DR

Quantum kernel methods’ optimization guarantees rely on efficiently estimating kernel values, but this efficiency cannot always be taken for granted. This paper analyzes several sources of kernel concentration and finds that polynomially many measurements can leave predictions insensitive to unseen inputs.

  • Problem

    Quantum kernel training guarantees depend on efficiently estimating kernel values, but whether this is feasible is not assured.

    Source: §I · p. 2, §III · p. 15

  • Method

    The paper analyzes concentration arising from embedding expressivity, global measurements, entanglement, and noise.

    Source: §I · p. 2, §3 · p. 11

  • Results

    With only polynomially many shots, predictions become insensitive to input data and perform trivially on unseen data when kernels exponentially concentrate.

    Source: §I · p. 2, §III · p. 15

  • Takeaways & Limitations

    Kernel and embedding choices should account for concentration risks; the authors advise generally avoiding problem-agnostic embeddings and being mindful of entanglement and fidelity-kernel global measurements.

    Source: §III · p. 15

Abstract

from arXiv · show

Kernel methods in Quantum Machine Learning (QML) have recently gained significant attention as a potential candidate for achieving a quantum advantage in data analysis. Among other attractive properties, when training a kernel-based model one is guaranteed to find the optimal model's parameters due to the convexity of the training landscape. However, this is based on the assumption that the quantum kernel can be efficiently obtained from quantum hardware. In this work we study the performance of quantum kernel models from the perspective of the resources needed to accurately estimate kernel values. We show that, under certain conditions, values of quantum kernels over different input data can be exponentially concentrated (in the number of qubits) towards some fixed value. Thus on training with a polynomial number of measurements, one ends up with a trivial model where the predictions on unseen inputs are independent of the input data. We identify four sources that can lead to concentration including: expressivity of data embedding, global measurements, entanglement and noise. For each source, an associated concentration bound of quantum kernels is analytically derived. Lastly, we show that when dealing with classical data, training a parametrized data embedding with a kernel alignment method is also susceptible to exponential concentration. Our results are verified through numerical simulations for several QML tasks. Altogether, we provide guidelines indicating that certain features should be avoided to ensure the efficient evaluation of quantum kernels and so the performance of quantum kernel methods.

I. INTRODUCTION

Quantum kernel methods offer convex training, but that guarantee is meaningful only when kernel values can be estimated efficiently and retain information about the inputs. The introduction warns that, under certain conditions, kernel values concentrate exponentially as qubit count grows.

I. INTRODUCTION

  • With polynomially many measurements, exponentially concentrated kernels require exponentially many shots to resolve and yield predictions on unseen inputs independent of the data.In that regime, the trained model is effectively useless for the target problem.Source: §I · pp. 1–2
  • Exponential concentration can arise from embedding expressivity, global measurements in fidelity kernels, entanglement with local observables, or noise, with analytic bounds and numerical demonstrations across learning tasks.Global measurements can cause concentration even when embedding expressivity and data-state entanglement are low.Source: §I · p. 2
  • The authors recommend problem-inspired embeddings over highly expressive, entangling problem-agnostic ones, while warning that optimizing parametrized embeddings can itself exhibit barren plateaus.The introduction also notes that projected kernels use local-subsystem measurements and maintained generalization in a setting where fidelity kernels failed.Source: §I · p. 2
  • This work systematically analyzes causes and effects of concentration under shot noise, extending prior observations for fidelity kernels, generalization analyses [45], and shot-count studies [16].The authors present the findings as guidance on kernels and embeddings to avoid, and caution against deep encoding schemes in the near term.Source: §I · p. 2

II. RESULTS · A. Framework

Quantum-kernel methods compare data-encoded quantum states and can be perfectly trained when their Gram matrix is available exactly, but concentration can make predictions independent of input data.

A. Framework

  • The results apply to supervised and unsupervised quantum-kernel tasks, while the analysis focuses concretely on supervised learning with classical data.In that setting, training examples pair input vectors with labels related by an unknown target function.Source: A. Framework · p. 2
  • With polynomially many measurement shots, exponentially concentrated kernels yield data-independent off-diagonal estimates and ultimately trivial predictions on unseen inputs.For the Loschmidt Echo test, off-diagonal estimates concentrate to zero; for the SWAP test, they are indistinguishable from a data-independent random variable.Source: Figure 1 · p. 3
  • Each input is encoded as an n-qubit state using an arbitrary unitary embedding, so the framework includes all unitary embedding schemes.The encoded state is obtained by applying the data-embedding unitary to an initial state.Source: A. Framework · p. 3
  • The framework considers fidelity and projected quantum kernels, which measure similarity between encoded states and, for the projected kernel, reduced single-qubit states.The projected-kernel definition also uses the Schatten 2-norm and a positive hyperparameter γ.Source: A. Framework · p. 3
  • Kernel methods map data into a higher-dimensional feature space and, by the Representer Theorem, express the optimal model as a linear combination of kernels on the training data.The QML model depends on input data through inner products between encoded states.Source: A. Framework · pp. 3–4
  • When the Gram matrix is calculated exactly and the loss is appropriately chosen, convex optimization finds the optimal parameters, making kernel-based methods perfectly trainable.The framework constructs the Gram matrix from kernels evaluated over training input pairs.Source: A. Framework · p. 4

B. Why exponential concentration is problematic

Exponential concentration makes quantum-kernel values difficult to distinguish with polynomially many measurements, producing estimates that can be insensitive to input data and lead to poor generalization.

B. Why exponential concentration is problematic

  • With polynomially many shots, exponentially concentrated kernel values yield estimates that are effectively independent of input data, making trained models insensitive to unseen inputs.The estimated Gram matrix, rather than the exact one, is used for training, and its statistical uncertainty inhibits performance.Source: B. Why exponential concentration is… · pp. 4, 6
  • For quantum kernels in [0,1], an exponentially small mean over input pairs implies exponentially small variance, providing a way to diagnose exponential concentration.For kernels, the input variables are pairs of data points; when the mean vanishes exponentially, deviations from zero by any fixed amount are exponentially unlikely.Source: B. Why exponential concentration is… · pp. 4–5
  • With exponentially small fidelity-kernel values, polynomial-shot Loschmidt Echo estimates produce an identity Gram matrix with exponentially high probability, yielding zero predictions on unseen inputs.The all-zero measurement outcome is then unlikely to appear in the sample, so estimated off-diagonal kernel values are zero.Source: B. Why exponential concentration is… · pp. 5–6
  • With polynomial-shot SWAP tests, the estimated Gram matrix is statistically indistinguishable from a data-independent random matrix, and unseen predictions are likewise data-independent.The exponentially small kernel signal is too small to distinguish from the uniform measurement distribution with polynomially many shots.Source: B. Why exponential concentration is… · pp. 5–6
  • In a 40-qubit simulation, more training data improved test performance with exact kernels but not estimated kernels; estimated-kernel training still achieved zero training error.The optimization can hard-code training labels even when kernel estimates provide no useful information for generalization, and adding training points does not remove this barrier.Source: B. Why exponential concentration is… · pp. 6–7, Figure 3 · p. 7

C. Sources of exponential concentration

The section investigates when quantum kernel values concentrate, since exponential concentration can produce trivial, data-independent models. It identifies four sources that hinder information extraction and derives a concentration bound for each.

C. Sources of exponential concentration

1. Expressivity-induced concentration

Highly expressive data embeddings make fidelity and projected quantum kernels concentrate, potentially requiring exponentially many measurements to estimate them. The section quantifies embedding expressivity and demonstrates concentration theoretically and numerically.

1. Expressivity-induced concentration

  • The data-dependent expressivity measure quantifies distance from a 2-design and incorporates both embedding expressivity and input-dataset randomness; it is zero only at maximal expressivity.A 2-design agrees with the uniform unitary distribution up to the second moment.Source: §1 · p. 8
  • As U(x) becomes more expressive, fidelity and projected kernels concentrate; near-2-design embeddings yield exponential concentration and exponentially many shots, with fidelity mean 1/2^n.The theorem assumes x and x′ are drawn from the same distribution; its bound uses ε_Ux, which is exponentially small for ε_Ux ∈ O(1/b^n), b > 1.Source: §1 · p. 8
  • Theorem 1 does not restrict U(x)’s form, extends to quantum data, and gives a similar concentration conclusion when paired inputs come from different training ensembles.The quantum-data case associates the data states with an underlying ensemble of state-preparing unitaries.Source: §1 · p. 9
  • Highly expressive encodings should be avoided; unstructured embeddings should generally give way to designs that account for data structure.The paper suggests geometrically inspired embeddings as one way to account for structure.Source: §1 · pp. 9–10
  • Roughly L ≥16, projected-kernel variance enters the exponential-decay regime, versus L ≥75 for fidelity; fidelity generally has smaller variance and stronger concentration.The numerics use an L-layer Hardware Efficient Embedding on MNIST data.Source: §1 · p. 9, Figure 6 · p. 10

2. Entanglement-induced concentration

Entanglement can concentrate projected quantum kernel values because tracing out qubits from highly entangled encoded states leaves local states close to maximally mixed. The resulting deterministic bound makes volume-law encodings especially problematic, while area-law scaling alone does not determine whether exponential concentration occurs.

2. Entanglement-induced concentration

  • Theorem 2 bounds projected-kernel deviation from 1 using the relative entropy between reduced encoded states and a single-qubit maximally mixed state.Unlike the earlier concentration results, this bound is deterministic and applies to a given pair of encoded states, not an average over data pairs.Source: §2 · p. 10
  • For volume-law encodings with S ∈ O(1/2^(n−1)) for all subsystems, projected-kernel values deterministically concentrate exponentially toward 1.The theorem’s upper bound allows area-law encodings with S ∈ O(1) to avoid exponential concentration, but does not guarantee that they do.Source: §2 · p. 10
  • For encoded-state ensembles forming at least a 4-design, most states obey volume-law scaling, but the expressivity bound already predicts exponential kernel concentration.Thus the entanglement-induced result is redundant for those ensembles; it also applies to individual data pairs rather than averaging over all pairs.Source: §2 · p. 10
  • Even a non-highly expressive embedding can make projected kernels fail at supervised learning with polynomially many shots if its encoded states obey a volume law.In the stated binary-classification example, performance cannot exceed random guessing without exponentially many shots, although the fidelity kernel avoids this concentration problem.Source: §2 · p. 10
  • Highly entangling embeddings should be avoided for projected kernels, while quantum datasets produced by Haar-random evolutions can make classification inefficient with them.Pure-state fidelity kernels do not incur this entanglement-induced effect because they do not trace out qubits; classical data embeddings can instead avoid highly entangled states.Source: §2 · p. 11

3. Global-measurement-induced concentration

Global measurements can cause exponential concentration of fidelity kernels even for simple product embeddings, although this is not universal: data structure matters. To avoid it, embeddings should preserve pairwise state fidelities at least in Ω(1/poly(n)).

3. Global-measurement-induced concentration

  • Global measurements act non-trivially on all qubits and are required for fidelity kernels, but not projected kernels; extracting global state information can cause concentration.Projected kernels avoid this difficulty through their local construction.Source: §3 · p. 11
  • With independent uniform input components and product initial states, Proposition 3 shows concentration for a fidelity kernel using single-qubit rotation embeddings, despite low expressivity and no entanglement.The proposition’s intuition is that the fidelity between two product states is usually exponentially small.Source: §3 · p. 11
  • Fidelity-kernel variance decays exponentially with qubit count even for single-layer product rotations, and additional HEE layers accelerate the decay.The simulations use independently and uniformly sampled input components; increasing embedding expressivity can further increase concentration.Source: §3 · p. 11, Figure 7 · p. 12
  • Global measurements do not always cause exponential concentration: MNIST with low-depth ansätze lacks the proposition’s assumptions, and its fidelity kernel does not show exponential concentration.If encoded states are close enough that kernel values concentrate no worse than polynomially in n, their overlap can be efficiently resolved.Source: §3 · p. 12
  • For global-measurement kernels, choose embeddings so every pair of encoded states has fidelity at least Ω(1/poly(n)), using problem structure or reducing problem-agnostic embedding expressivity.The authors identify structure-aware embedding design [43] and reduced expressivity for problem-agnostic embeddings as approaches.Source: §3 · p. 12

4. Noise-induced concentration

Layerwise Pauli noise makes both fidelity and projected quantum kernels concentrate exponentially with embedding depth, because noisy encoded states approach the maximally mixed state. When depth scales polynomially with qubit count, the bounds decay exponentially in qubit count for every q < 1.

Noise-induced concentration

  • The analysis models unital local Pauli noise before and after each embedding layer, for layered embeddings that include HEE, QAOA, HVE, and IQP ansätze.The model permits each layer to encode an input component or repeatedly encode a fixed input vector.Source: §4 · p. 12
  • For both kernel types, noise-induced concentration is exponential in layer count: the fidelity kernel approaches μ = 1/2^n and the projected kernel μ = 1.The bounds are deterministic because the noise acts independently of input data; the noisy encoded state also concentrates toward the maximally mixed state.Source: §4 · pp. 12–13
  • For polynomial depth L in qubit count n, the concentration bound decays exponentially in n for all q < 1, with noise characteristics changing the decay rate.This includes moderately deep circuits with L scaling at least linearly in n, a regime of interest for locally connected embeddings.Source: §4 · p. 13
  • In MNIST simulations, both kernels concentrate exponentially with HEE depth, and concentration is stronger at higher noise levels; the plotted fixed points are 1/2^n and 1.The simulations apply noise before and after single-qubit gates but assume noiseless entangling gates; the authors expect real entangling-gate noise to accelerate concentration.Source: §4 · p. 13, Figure 8 · p. 13
  • The authors argue that common error-mitigation techniques cannot resolve this exponential concentration, posing a barrier to implementing quantum kernel methods on near-term hardware.The discussion names Zero-Noise Extrapolation, Clifford Data Regression, Virtual Distillation, and Probabilistic Error Cancellation.Source: §4 · p. 13

D. Training parameterized quantum kernels

This section studies trainability of learned data embeddings for quantum kernels, showing that kernel concentration can flatten kernel-target-alignment landscapes and make embedding optimization untrainable with polynomially many measurement shots.

D. Training parameterized quantum kernels

  • Training the embedding is an alternative to constructing problem-inspired embeddings, which can be highly non-trivial, and has been proposed to improve quantum-kernel generalization.It is an additional step before applying the standard quantum-kernel algorithm.Source: D. Training parameterized quantum… · p. 13
  • Embedding parameters define a family of quantum kernels, and training selects an optimal embedding before the standard quantum-kernel model-training process.Kernel target alignment measures similarity to an ideal kernel approximated from training data and can be used as a loss, but this embedding-training loss is generally non-convex.Source: D. Training parameterized quantum… · pp. 13–14
  • When kernel variances over training pairs vanish exponentially with qubit count, kernel target alignment concentrates, making its parameter landscape exponentially flat and untrainable with polynomially many shots.The variance of target alignment over embedding parameters is upper bounded by the variances of the parameterized kernels.Source: D. Training parameterized quantum… · p. 14
  • Deep unstructured circuits and global measurements can induce the exponentially vanishing kernel variances that produce barren plateaus in parameterized quantum kernels.These features should therefore be avoided when designing parameterized data embeddings for quantum kernels.Source: D. Training parameterized quantum… · p. 14
  • With global measurements, the variance of kernel target alignment over parameter initializations exponentially concentrates as qubit count increases in the reported numerical study.The study used a hypercube dataset with 10 training samples and parameterized single-qubit y rotations followed by a hardware-efficient entangling layer.Source: D. Training parameterized quantum… · p. 14, Figure 9 · p. 14

III. DISCUSSION … 2. Many samples

Quantum kernels can concentrate exponentially, making accurate estimation exponentially costly and causing polynomial-shot models to ignore their inputs. The discussion identifies embedding expressivity, global measurements, entanglement, and noise as hazards; the appendicial lemmas relate finite-sample distinguishability to probability-distribution distances.

III. DISCUSSION

  • Exponential concentration can make quantum-kernel values require exponentially many shots; with polynomial shots, predictions become input-insensitive, and more training data cannot fix this.The paper says performance can instead be improved by increasing measurement shots or using a more appropriate embedding; its bounds apply to a wide range of embedding architectures.Source: §III · p. 15
  • The four hazards are expressive embeddings, global measurements, entanglement, and noise; avoid highly expressive embeddings, entangling states for local kernels, and noisy polynomial-depth circuits, and use fidelity kernels only for nearby embedded states.Fidelity kernels can concentrate under global measurements even with a simple, low-expressivity, unentangled embedding.Source: §III · p. 15
  • Training parametrized quantum kernels by kernel target alignment can suffer exponentially flat training landscapes.The discussion notes this result for parametrized quantum kernels; the related-work section also describes kernel target alignment and progressive unitary-block construction as embedding-training approaches.Source: §III · p. 15, §3 · p. 20

1. Exponential concentration in fidelity quantum kernels

  • Refs. linked fidelity-kernel concentration-like behavior to poor generalization, while later numerical evidence supported the concern; these studies did not analyze exact causes and assumed direct state access without shot noise.Ref. gave a generalization bound and numerical evidence up to 30 qubits; Ref. analyzed an unstructured product embedding.Source: §1 · p. 19

2. Exponential concentration in projected quantum kernels

  • For projected kernels, this work studies arbitrary data-dependent embeddings and the input-distribution/embedding interplay, identifying expressivity, noise, and entanglement as concentration sources and analyzing shot-noise effects on predictions.This contrasts with Ref. 's concentration from a data-independent embedding component.Source: §2 · p. 19

3. Attempts to mitigate the exponential concentration

  • Mitigation proposals include data rescaling [45], whose quantum advantage was questioned numerically, and quantum Fisher kernels [89], which avoid concentration at log depth but not linear depth.Other approaches train embeddings with kernel target alignment or progressively add unitary blocks [90], though training can incur barren plateaus.Source: §3 · p. 20

4. Effect of shot noise in the absence of exponential concentration

  • With discrete-log data, Ref. proves a fidelity-kernel SVM advantage that persists under shot noise; Ref. [16] finds robustness when class separation is polynomial and concentration is absent.For Ref., kernel values and predictions can be evaluated with polynomially many measurement shots.Source: §4 · p. 20

Appendix B: Preliminaries for statistical indistinguishability; 1. One sample; 2. Many samples

  • Appendix B frames single- and N-sample distinguishability through probability-distribution 1-norms; product-distribution distance is at most N||P−Q||1, and a binary perturbation has distance 2|ε|.The setup treats N samples as one sample from product distributions, with the two hypotheses equally likely.Source: Appendix B · p. 20, §1 · p. 21, §2 · p. 22

Appendix C: Practical implications of exponential concentration on kernel methods · 1. Fidelity quantum kernel

With polynomially many measurements, exponential concentration can make estimated kernel information independent of input data, producing trained predictions that cannot generalize. The appendix examines this consequence for fidelity and projected quantum kernels.

Appendix C: Practical implications of exponential concentration on kernel methods

  • With polynomially many measurements, estimated Gram matrices are high-probability data-independent, yielding trained models whose predictions cannot generalize.The argument is illustrated with kernel ridge regression and is said to carry over to other learning tasks.Source: Appendix C · p. 22

1. Fidelity quantum kernel

  • Under exponential concentration, Loschmidt Echo estimates concentrate at zero, making the estimated Gram matrix likely identity and model predictions concentrate to zero.These consequences are stated to hold with high probability.Source: Appendix C · p. 23
  • With the SWAP test, exponentially concentrated kernel estimates become statistically indistinguishable, and trained-model outputs become insensitive to unseen inputs.The argument reduces the result to hypothesis testing.Source: Appendix C · p. 23
  • Numerical simulations of the fidelity kernel support the theoretical results for its measurement strategies.The appendix also reports numerical results supporting its projected-kernel findings.Source: Appendix C · p. 23

Appendix C: Practical implications of exponential concentration on kernel methods

  • For projected quantum kernels, both measurement strategies yield indistinguishable kernel estimates and model predictions under exponential concentration.The passage says this effect occurs in the same manner as for the fidelity kernel SWAP test.Source: Appendix C · p. 23
  • Extending kernel concentration to state concentration gives a stronger result that polynomially many quantum-accessible state copies cannot resolve.The appendix also discusses a sufficient condition for resolving exponential concentration.Source: Appendix C · p. 23
  • Resolving exponential concentration requires measurement shots scaling exponentially with qubit number, which is impractical for large problems.The stated sufficient condition is an exponential number of shots to obtain enough resolution in kernel estimates.Source: Appendix C · p. 23

a. Loschmidt Echo test

For the Loschmidt Echo test, the fidelity kernel is estimated by counting all-zero measurement outcomes, so exponentially small concentrated kernel values are missed with polynomially many shots. The resulting estimated Gram matrix is typically the identity, making kernel-ridge predictions input-independent and poor at generalizing.

a. Loschmidt Echo test

  • The Loschmidt Echo test estimates the fidelity kernel by counting all-zero bitstrings, since that outcome alone has measurement value +1.The observable is the global projector onto the all-zero state; all other measurement outcomes are 0.Source: a. Loschmidt Echo test · p. 24
  • With polynomially many shots, an exponentially small concentrated fidelity kernel is estimated as zero with probability exponentially close to 1, and the estimated Gram matrix is the identity with the same high probability.For a training set of polynomial size, the identity-Gram-matrix conclusion holds with probability exponentially close to 1.Source: a. Loschmidt Echo test · p. 25
  • With exponentially high probability, kernel ridge regression’s optimal parameters equal the input-independent fixed point a0(y, λ) = y/(1 − λ), while predictions on unseen inputs concentrate at zero.The optimal-parameter equality and zero unseen-input kernel estimates each hold with probability exponentially close to 1.Source: a. Loschmidt Echo test · p. 26
  • Although the model can achieve low training error, its predictions are insensitive to input data and generalize poorly; hoping for good generalization requires at least exponentially many shots.The poor generalization described here cannot be resolved simply by training on more data points.Source: a. Loschmidt Echo test · p. 27

b. SWAP test … 4. Sufficient condition to resolve kernel values

These parts examine how exponential concentration affects the resolvability of quantum-kernel values with polynomial measurement resources, across SWAP tests, projected-kernel estimates, tomography, local estimates, and coherent copies. They describe when estimates or predictions become input-independent and the measurement resources needed to distinguish or resolve kernel values.

b. SWAP test

  • With exponentially high probability over input pairs, polynomial-sample SWAP-test outcomes for an exponentially concentrated fidelity kernel are statistically indistinguishable from uniform binary outcomes.The kernel’s exponentially small value creates an exponentially small perturbation from the uniform distribution.Source: b. SWAP test · pp. 28–29
  • Consequently, polynomial-size training with these estimates yields data-independent Gram matrices and predictions, so the model is useless for generalization even if its training error is low.The result applies to kernel methods broadly; the stated corollary covers kernel ridge regression with squared loss and a polynomial-size dataset.Source: b. SWAP test · pp. 30–31

c. Numerical simulation

  • At 30 and 40 qubits, all Loschmidt Echo estimates were zero even with 2 × 10^6 shots per kernel value; maintaining a constant SWAP-test success ratio requires exponentially many shots.The SWAP-test success ratio counts estimates that pass a binomial test against the uniform distribution at p-value below 0.01.Source: Figure 13 · p. 32, c. Numerical simulation · p. 32

2. Projected quantum kernel

  • Projected-kernel estimates can use single-qubit tomography, requiring a constant number of measurements per qubit with respect to qubit count, or local SWAP tests, followed by classical post-processing.Local SWAP tests estimate reduced-state 2-norm terms, including overlaps and purities.Source: §2 · p. 33

a. Consequence of exponential concentration

  • When the expected reduced-state 2-norm distance vanishes exponentially for each qubit, the projected quantum kernel exponentially concentrates.The paper states that the sources of exponential concentration it analyzes for projected kernels also lead to exponential vanishing of these reduced-state distances.Source: a. Consequence of exponential… · p. 34
  • With polynomial shots, estimated reduced-state 2-norms and projected-kernel values are statistically indistinguishable from input-data-independent random variables.This follows by estimating all single-qubit terms and combining them to form the 2-norms and projected kernel.Source: a. Consequence of exponential… · p. 35
  • For polynomial-size training sets, projected-kernel estimates, Gram matrices, and unseen-input predictions become statistically indistinguishable from data-independent quantities, yielding poor generalization.The training process can encode training labels and attain small training error without obtaining information about input data during training or prediction.Source: a. Consequence of exponential… · p. 36

b. Numerical simulation

  • An exponential number of shots is required to substantially increase the fraction of estimates distinguishable from fixed distributions in the projected-kernel simulation.With only polynomially many shots, estimates of the measured quantities remain indistinguishable from data-independent random variables for larger systems.Source: b. Numerical simulation · pp. 36–37, Figure 14 · p. 37
  • With N = 1000 shots, SWAP- and tomography-estimated kernels do not improve generalization as training data increases, unlike exact kernel values.Training errors remain perfect in all cases, while relative error follows a trend similar to training on a random Gram matrix.Source: b. Numerical simulation · p. 37, Figure 15 · p. 38

c. Proof of analytical results

  • With polynomial measurement shots, tomography coefficients exponentially concentrate near exponentially small values and local SWAP means toward 1/2, yielding fixed distributions {1/2, 1/2} and {3/4, 1/4}, respectively.The associated distributions are statistically indistinguishable from these data-independent fixed distributions with probability exponentially close to 1.Source: c. Proof of analytical results · pp. 39–42
  • With polynomial shots and a polynomial-size training set, the projected-kernel Gram matrix, estimated optimal parameters, and unseen-input predictions are statistically indistinguishable from input-independent quantities with probability exponentially close to 1.The Gram matrix has diagonal elements 1 and input-independent off-diagonal entries; the proof uses a union bound over measured kernel values and test-input kernels.Source: c. Proof of analytical results · pp. 44–45

3. Indistinguishability of concentrated quantum states

  • If quantum states are exponentially close in one-norm, they remain indistinguishable when a polynomial number of copies is processed coherently.Their one-norm distance is O(1/b^n) for b > 1; in the presence of noise, multiple-copy error mitigation cannot avoid the resulting data-independence.Source: §3 · p. 46

4. Sufficient condition to resolve kernel values

  • When X(α) is exponentially concentrated, resolving its values requires relative error ˜ϵ ≲1 and exponentially many measurement shots for constant success probability, assuming ∥O∥∞∈O(1).The relative error compares statistical uncertainty with the variation of X(α) across α.Source: §4 · p. 46
  • For the fidelity quantum kernel, distinguishing off-diagonal Gram-matrix elements from a fixed matrix requires exponentially many shots; classical shadows may reduce quadratic scaling in dataset size but not the exponential scaling in qubits, which also applies to projected kernels.The fixed matrix has diagonal elements 1 and off-diagonal elements equal to the concentration value.Source: §4 · pp. 47–48
  • Absence of exponential concentration is necessary for quantum kernels to have potential; encoding problem structure into an embedding can achieve it in the cited encryption-inspired task and covariant-kernel family [43].The section identifies a non-vanishing class separation from the feature map as essential for a quantum support vector machine.Source: §4 · p. 48

Appendix D: Proof of Theorem 1: Expressivity-induced concentration · 1. Extensions of Theorem 1 to different input distributions · Appendix E: Proof of Theorem 2: Entanglement-induced concentration

The appendices establish expressivity- and entanglement-based concentration bounds for quantum kernels, extend the expressivity result to distinct input distributions, and prove the entanglement result through reduced-state comparisons.

Appendix D: Proof of Theorem 1: Expressivity-induced concentration

  • For inputs from the same distribution, Theorem 1 bounds concentration of fidelity and projected quantum kernels using data-dependent expressivity and G_n(ε_Ux).Source: Appendix D · p. 48
  • For projected kernels, the proof bounds 1−κ_PQ using its nonnegative unit upper bound, applies 1−e^-t≤t, and then completes the concentration proof with Chebyshev’s inequality.Source: Appendix D · pp. 48, 49, 51
  • For fidelity kernels, the proof upper-bounds variance around the Haar value β_Haar and applies Chebyshev’s inequality to establish concentration.Source: Appendix D · pp. 48–49

1. Extensions of Theorem 1 to different input distributions

  • For x and x′ drawn from different distributions, concentration retains Theorem 1’s form with modified bounds depending on separate expressivity measures for the fidelity and projected kernels.Source: §1 · p. 51

Appendix E: Proof of Theorem 2: Entanglement-induced concentration

  • Theorem 2 relates projected-kernel concentration to reduced-state concentration, with its bound expressed using quantum relative entropy and single-qubit reduced states.Source: Appendix E · p. 52
  • The proof considers an n_s-qubit reduced subsystem and bounds pairwise reduced-state distance using Pinsker’s inequality and norm and triangle inequalities.Source: Appendix E · p. 52
  • For the projected kernel’s single-qubit subsystem, the proof derives its bound using 1−e^-t≤t and the preceding reduced-state inequality.Source: Appendix E · p. 52

Appendix F: Proof of Proposition 3: Global-measurement-induced concentration · 1. Extension to arbitrary local unitaries

For product-state fidelity kernels with independent local data encodings, global measurements can induce exponential concentration; the result extends to arbitrary local unitaries, with a 1/3^n bound when all single-qubit unitaries are random.

Appendix F: Proof of Proposition 3: Global-measurement-induced concentration

  • Proposition 3 considers fidelity kernels with one y-axis rotation per qubit, encoding independent input components sampled uniformly from [−π, π] and a product initial state.The data embedding is a tensor product of the local rotations.Source: Appendix F · p. 53
  • The proof bounds the kernel variance over the input data and applies Chebyshev’s inequality to establish the concentration bound.For Proposition 3, the argument uses the specified local y-axis data embedding.Source: Appendix F · p. 53
  • For y-axis rotations with independently uniform inputs in [−π, π] and a product initial state, the global-measurement concentration point is 2^-n.The passage states that each factor in the concentration point’s product equals 1/2 for these rotations.Source: Appendix F · p. 53

1. Extension to arbitrary local unitaries

  • The extension allows arbitrary local unitaries encoding independent input components, with a product initial state and a data-dependent local expressivity measure.The supplied proposition text identifies this measure, but the bound’s full expression is not included in the passages.Source: §1 · p. 54
  • The generalized proof bounds variance and invokes Chebyshev’s inequality; its bound uses the local-unitary expressivity term ε_Uk.The proof also cites trace factorization, independence, and norm inequalities in deriving the bound.Source: §1 · p. 55
  • With random single-qubit unitaries, the generalized concentration bound is 1/3^n, so the kernel concentrates probabilistically as the qubit count grows.This is the stated limit when ε_Uk = 0 for every qubit.Source: §1 · p. 55

Appendix G: Proof of Theorem 3: Noise-induced concentration

Appendix G proves Theorem 3: under layer-wise Pauli noise with characteristic parameter q < 1, noisy fidelity and projected quantum kernels concentrate around different fixed values. It also establishes concentration of noisy data-encoded states toward the maximally mixed state.

Supporting lemmas

  • Unitary transformations preserve the Schatten p-norm of the Pauli expansion, while local Pauli noise acts on its coefficients.The appendix uses these lemmas to establish the state and kernel concentration bounds.Source: Appendix G · p. 56

Theorem 3

  • For an L-layered embedding with layer-wise Pauli noise q < 1, Theorem 3 bounds fidelity-kernel concentration around µ = 1/2^n and projected-kernel concentration around µ = 1.The bounds use the sandwiched 2-Rényi relative entropy, with b = 1/(2 ln(2)) ≈ 0.72.Source: Appendix G · p. 58
  • The noisy data-encoded state concentrates toward the maximally mixed state.The proof writes the state in the Pauli basis and repeatedly applies the unitary-invariance and noise-channel lemmas across the embedding layers.Source: Appendix G · p. 58

Appendix H: Error Mitigation … 4. Noise

The section examines concentration and flatness in noisy quantum-kernel settings, including error mitigation, concentration bounds for fidelity and projected kernels under layer-wise Pauli noise, and conditions under which kernel alignment and variational training inherit concentration or flatness. It also describes the noisy data-encoded state concentrating toward the maximally mixed state.

Appendix H: Error Mitigation

  • Prior work [32] [77] finds that common error-mitigation strategies cannot resolve noise-induced barren plateaus; here, they likewise cannot remove exponential noise-induced kernel concentration.For small circuit depths, error mitigation may still help; at fixed system size, it can also impair resolvability compared with no mitigation [32].Source: Appendix H · pp. 60–61
  • With local depolarizing noise before and after each layer, expectation estimates concentrate on a state-independent fixed point as depth grows; for Lσ ∈ Ω(n), mitigated Cm concentrates toward F0.The bound assumes ∥A∥∞ ∈ O(poly(n)) and uses the maximum coefficient and copy count in the mitigation strategy.Source: Appendix H · p. 61

Appendix I: Proof of Proposition 4: Concentration of kernel target alignment

  • Proposition 4 bounds concentration of kernel target alignment by the concentration of the parameterized quantum kernel.The appendix proves this result for a parameterized kernel and a binary-classification training dataset.Source: Appendix I · pp. 61, 63

Appendix J: Sources that lead to exponentially flat landscape of parameterized quantum kernels

  • The training landscape of parameterized quantum kernels can become exponentially flat through expressivity, entanglement, global measurements, or noise in the variational embedding.This flatness arises from the variational part of the embedding, unlike earlier kernel concentration caused by input data.Source: Appendix J · p. 65

1. Expressivity

  • Supplemental Theorem 2 gives concentration bounds for parameterized fidelity and projected quantum kernels in terms of the embedding’s expressivity.The theorem defines the expressivity measure over the variational unitaries for a given input.Source: §1 · pp. 65–66

2. Entanglement

  • Entanglement generated by the parameterized data embedding can negatively affect the parameterized projected quantum kernel.Supplemental Theorem 3 generalizes the entanglement result to this parameterized kernel.Source: §2 · p. 66

3. Global measurements

  • Global measurements can induce flatness for fidelity kernels, but have no impact on projected kernels because those kernels are constructed locally.For a fidelity kernel, barren plateaus in the relevant global-observable expectation values imply a barren plateau in the kernel; a hardware-efficient ansatz yields exponential concentration around its mean.Source: §3 · pp. 66–67

4. Noise

  • Noise both exponentially flattens the training landscape of noisy parameterized kernels with respect to θ and exponentially concentrates their values with respect to x and x′.The passage introduces a theorem generalizing the noisy-kernel concentration result.Source: §4 · p. 67
  • The local Pauli noise acts before and after each layer.The noise model is specified by characteristic parameter q.Source: §4 · p. 67
  • For an L-layered embedding with Pauli noise parameter q ≤ 1, Supplemental Theorem 4 bounds concentration of fidelity and projected kernels, with means 1/2^n and 1, respectively.Source: §4 · p. 68
  • The noisy data-encoded quantum state concentrates toward the maximally mixed state.Source: §4 · p. 68

Related papers

Loading 2208.11060v2…