PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum machine learning beyond kernel methods

Sofiene Jerbi, Lukas J. Fiderer, Hendrik Poulsen Nautrup, Jonas M. Kübler, Hans J. Briegel, Vedran Dunjko

arXiv:2110.13162v3quant-phcs.AIcs.LGstat.ML

TL;DR

Quantum machine learning models based on parametrized circuits are difficult to compare, especially regarding their relation to kernel methods and their experimentally relevant resource needs. The paper unifies these models as linear models in quantum feature spaces and maps data re-uploading circuits into that framework. It shows that model choice can produce exponential separations in qubit and data requirements, with variational models retaining advantages beyond kernel methods.

  • Problem

    The relationships, comparative learning behavior, and qubit and data requirements of parametrized-circuit quantum machine learning models remain limitedly understood.

  • Method

    The paper constructs a unifying quantum-feature-space framework and maps data re-uploading circuits to explicit linear models using quantum-information techniques.

  • Results

    The paper proves exponential resource separations among model families, including exponentially greater qubit requirements for linear models than data re-uploading models and additional data requirements for kernels.

  • Takeaways & Limitations

    Generalization and experimentally relevant resources matter beyond training loss, and practical quantum learning advantages may lie in explicit and data re-uploading models beyond kernels.

Abstract

from arXiv · show

Machine learning algorithms based on parametrized quantum circuits are prime candidates for near-term applications on noisy quantum computers. In this direction, various types of quantum machine learning models have been introduced and studied extensively. Yet, our understanding of how these models compare, both mutually and to classical models, remains limited. In this work, we identify a constructive framework that captures all standard models based on parametrized quantum circuits: that of linear quantum models. In particular, we show using tools from quantum information theory how data re-uploading circuits, an apparent outlier of this framework, can be efficiently mapped into the simpler picture of linear models in quantum Hilbert spaces. Furthermore, we analyze the experimentally-relevant resource requirements of these models in terms of qubit number and amount of data needed to learn. Based on recent results from classical machine learning, we prove that linear quantum models must utilize exponentially more qubits than data re-uploading models in order to solve certain learning tasks, while kernel methods additionally require exponentially more data points. Our results provide a more comprehensive view of quantum machine learning models as well as insights on the compatibility of different models with NISQ constraints.

I. INTRODUCTION

Quantum machine learning models based on parametrized circuits offer potential practical value, but their relationships, learning guarantees, and resource requirements remain insufficiently understood. This work introduces a framework for comparing explicit, implicit, and data re-uploading models as linear models in quantum feature spaces.

  • Parametrized quantum circuits define hypothesis classes for supervised learning and are studied as potential alternatives to classical models.
  • Quantum machine learning research has emphasized kernel methods because many quantum models encode data into Hilbert spaces and use inner products.
  • Explicit models measure encoded quantum states with variational observables, whereas implicit models combine inner products between input and training feature states.
  • Data re-uploading alternates data encodings with variational unitaries, increasing expressivity but apparently breaking the fixed-feature-state correspondence used by kernels.
  • The paper unifies explicit, implicit, and data re-uploading models as linear models in suitably defined quantum feature spaces.
  • The work compares models using training behavior and experimentally relevant resources, including qubit number, data requirements, and circuit evaluations.

1. Explicit models

Explicit and implicit quantum models are both linear models in a quantum feature space, while data re-uploading extends the encoding process and can also be represented linearly after enlarging that space.

  • Explicit models: An explicit model restricts accessible observables through a variational unitary family acting before measurement.
  • Implicit models: An implicit model forms a weighted combination of kernel inner products between an input and training data points.
  • Linear quantum models: Both explicit and implicit quantum models are linear models in the same quantum feature space because kernel combinations correspond to observables formed from feature states.
  • Data re-uploading models: Data re-uploading interleaves multiple encoding layers with variational unitaries, so trainable gates cannot generally be collected into one fixed-feature-space observable.
  • Linear realizations: By enlarging the Hilbert space, the paper constructs equivalent explicit linear realizations of data re-uploading model families with an efficient mapping procedure.

1. Approximate mapping

The paper first gives an approximate explicit realization of data re-uploading circuits by encoding inputs into ancilla bit strings and using data-independent controlled operations. An exact construction later uses gate teleportation.

  • Approximate mapping: The approximate circuit uses n working qubits and dp encoding qubits to store p-bit descriptions of d real input components.
  • Approximate mapping: The illustrative construction produces an explicit model whose outputs approximate those of an arbitrary data re-uploading model within an adjustable error δ.
  • Approximate mapping: The explicit realization uses O(D log) additional qubits and gates, where D is the number of encoding gates and the observable contributes through its spectral norm.
  • Approximate mapping: Input components are encoded as finite-precision bit strings, which control fixed rotations that approximate data-encoding gates on the working qubits.
  • Exact mapping: An exact mapping with finite resources uses gate teleportation to implement encoding gates on ancillary qubits and teleport them back.

2. Exact mapping

The paper gives an exact mapping from arbitrary data re-uploading models to equivalent explicit linear models, while characterizing the mapping’s resource costs and evaluation caveats.

  • 2. Exact mapping: Gate teleportation constructs exact equivalent explicit models for arbitrary data re-uploading models.The mapping preserves expectation values while using data-independent operations and ancillary qubits.
  • 2. Exact mapping: O(D log(D/δ′)) additional qubits and gates suffice for a data re-uploading model with D encoding gates.The construction achieves the stated resource scaling for arbitrary renormalization parameter δ′ > 0.
  • 2. Exact mapping: Discarding gate-teleportation outcomes can produce an observable with exponentially larger spectral norm and exponentially harder evaluation at equal precision.A nested gate-teleportation scheme can make this norm overhead arbitrarily small.
  • 2. Exact mapping: Any universal mapping requires Ω(D) additional qubits in the worst case, making the gate-teleportation overhead optimal up to logarithmic factors.This lower bound applies to arbitrary data re-uploading models with D encoding gates.
  • 2. Exact mapping: The linear-quantum-model framework unifies explicit, implicit, and data re-uploading parametrized-circuit models.Data re-uploading hypothesis classes can be represented as explicit linear models with restricted observables.

A. Classical background and the representer theorem

Quantum feature encodings connect explicit and implicit models through linear models in Hilbert spaces and kernel methods, but lower regularized training loss need not imply better generalization.

  • A. Classical background and the representer theorem: The RKHS contains functions formed by inner products between quantum feature states and weights, including explicit and implicit quantum models.This characterizes families of linear quantum models using functional analysis.
  • A. Classical background and the representer theorem: The expected loss over the full data space is the relevant objective, while regularization is added to discourage overfitting.The regularization strength is controlled by λ ≥ 0.
  • A. Classical background and the representer theorem: The representer theorem states that the minimizer of regularized training loss in the RKHS is a kernel model.Consequently, implicit models achieve no higher regularized training loss than explicit models using the same encoding.
  • A. Classical background and the representer theorem: For the constructed bit-string encoding, the associated kernel is the Kronecker delta on encoded bit strings and is classically computable.The same kernel arises for the family of explicit models produced by the construction.
  • A. Classical background and the representer theorem: Estimating observables to the required precision is outside the analysis and may require exponentially many measurements in the number of qubits.The note applies to both explicit and implicit models.
  • A. Classical background and the representer theorem: As ε → 0, the corresponding implicit model overfits the training set and outputs zero outside it, failing to generalize to unseen points.Thus, greater expressivity can harm generalization despite regularization.

C. Rigorous learning separations between all quantum models

The paper constructs a parity-learning task that separates the three quantum model classes by experimentally relevant resource requirements as input dimension d grows.

  • C. Rigorous learning separations between all quantum models: The analysis measures quantum-model efficiency using the number of qubits and the training-set size.This follows an approach used in classical learning results separating neural networks from linear or kernel methods.
  • C. Rigorous learning separations between all quantum models: Parity functions on d-bit inputs provide the learning task because different subsets define orthogonal functions whose span grows combinatorially with d.The inputs lie in {−1, 1}^d, and each target is the product of a selected subset of components.
  • C. Rigorous learning separations between all quantum models: Theorem 2 specifies a regression family and input distributions under which the three quantum models require different resources to achieve a target mean-squared error.The theorem is stated for each input dimension d ∈ N.
  • C. Rigorous learning separations between all quantum models: Any linear quantum model requires a stated qubit lower bound, while any implicit quantum model additionally requires a stated number of data samples.The supplied theorem passage contains the comparison but truncates the numerical expressions.
  • C. Rigorous learning separations between all quantum models: A single-qubit data re-uploading model with d encoding gates can achieve perfect expected error with probability 1 − δ using M = O(log …) samples.The supplied passage truncates the final logarithmic expression.
  • C. Rigorous learning separations between all quantum models: The mapping from data re-uploading to equivalent explicit models has a worst-case lower bound of Ω(D) additional qubits, achieved up to logarithmic factors by the construction.This resource comparison links the model-mapping result to the broader separation analysis.

D. Quantum advantage beyond kernel methods

The paper revisits quantum advantage beyond kernel methods by comparing explicit, implicit, data re-uploading, and classical models on generalization and resource requirements. It finds that variational quantum models can outperform kernel and classical models on suitable tasks, while kernel methods may require exponentially more data for good generalization.

  • Quantum advantage beyond kernel methods: For the fashion-MNIST task, implicit models systematically achieve lower training loss, while explicit models clearly outperform both implicit and classical models in testing loss from n = 7 qubits.The experiment uses M = 1000 training images and a test set of size 100.
  • Quantum advantage beyond kernel methods: Quantum advantage should not be assessed only against quantum kernel methods because explicit and data re-uploading models can exhibit substantially better learning performance.Classical models can remain competitive with implicit models on quantum-tailored tasks, whereas variational quantum models can show a significant advantage.
  • Quantum advantage beyond kernel methods: Kernel methods can achieve lower training loss, but this advantage may coincide with poorer generalization outside the training set.The paper therefore evaluates testing loss rather than relying only on training performance.
  • Quantum advantage beyond kernel methods: The resource analysis shows exponential separations among data re-uploading, linear, and kernel models in qubits and data samples for certain learning tasks.The paper emphasizes that kernel methods may require exponentially more data samples to obtain good generalization performance.
  • Quantum advantage beyond kernel methods: Trainability remains a practical constraint: explicit models can exhibit barren plateaus, while implicit models can have exponentially vanishing kernel values.Under relevant conditions, either obstacle can require an exponential number of circuit evaluations for training and use.
  • Quantum advantage beyond kernel methods: The demonstrated exponential separations rely on parity functions, which the authors identify as not practically interesting for machine learning.They note that related lower bounds may extend to concept classes with large dimension.

Appendix A: Representer theorem

The appendix formalizes how data re-uploading circuits can be mapped to explicit models through approximate bit-string encodings and gate teleportation. These constructions preserve model expectation values while exposing approximation, normalization, and evaluation-cost trade-offs.

  • Appendix A: Representer theorem: The representer theorem states that regularized RKHS minimizers admit representations determined by the training examples and kernel evaluations.The theorem applies to strictly increasing regularization functions and arbitrary training losses under the stated RKHS setting.
  • Appendix A: Representer theorem: Explicit and implicit quantum models are linear models in quantum feature spaces, and data re-uploading models can also be realized as linear models in larger Hilbert spaces.This supplies the framework used to compare the model families.
  • Appendix A: Representer theorem: Encoding gates e^(-ih(x)H_n/2) can be reduced to single-qubit Rz(h(x)) rotations using O(n) data-independent operations.The reduction applies when H_n is an arbitrary n-qubit Pauli string.
  • Appendix A: Representer theorem: The approximate bit-string mapping uses ancillas as computational-basis controls, replacing data-dependent angles by precision ε = 2^-p rotations and tracing out the ancillas.In the worst case, D = d when each input component is assigned to a unique encoding gate.
  • Appendix A: Representer theorem: Gate teleportation implements Rz(x) exactly for one measurement outcome, while the other outcome requires a data-dependent Rz(2x) correction.The correction is needed with probability 1/2 for each teleportation.
  • Appendix A: Representer theorem: Without correction, the gate-teleportation mapping introduces a factor of 2^(D/2), making explicit-model evaluation exponentially harder in the number of encoding gates D.Repeated nested teleportations can make this norm overhead arbitrarily close to 1.

3. Kernels resulting from our mappings

The mappings generate explicit feature encodings whose induced kernels can be classically simulatable and increasingly close to delta kernels. The appendix also explains why these constructions do not violate no-programming and establishes broad approximation capabilities for explicit models.

  • 3. Kernels resulting from our mappings: The no-programming theorem rules out perfect universal processors implementing infinitely many unitaries through program states alone.The paper introduces this theorem to clarify the status of its mappings.
  • 3. Kernels resulting from our mappings: The gate-teleportation mappings produce feature encodings whose kernels approach k(x, x′) → δ_x,x′ as ND → ∞.Here D is the number of encoding gates and N the number of nested teleportations per gate.
  • 3. Kernels resulting from our mappings: For linear encoding angles and sufficiently large ND, no function can be learned by the resulting implicit model from a dataset of at most polynomial size in ND.This result assumes non-degenerate data distributions separable across all input components.
  • 3. Kernels resulting from our mappings: The mappings evade the theorem because bit-string implementations are approximate, gate-teleportation implementations are probabilistic, and exactness concerns expectation values rather than unitary maps.Approximation errors and normalization factors reflect these limits.
  • 3. Kernels resulting from our mappings: Explicit models are universal function approximators, including integrable functions with finitely many discontinuities on [0, 2π]^d.The construction uses feature encodings built from parametrized rotations and suitable observables.
  • 3. Kernels resulting from our mappings: The same construction extends to computable hypothesis classes specified by Boolean or quantum circuits with parametrized vectors.Amplitude or phase estimation creates bit-string representations of the input and parameters.

Appendix D: Beyond unitary feature encodings

The appendix describes general feature encodings and the numerical models used to compare explicit, implicit, and classical approaches. The simulations use PCA-processed data and variational quantum circuits, with performance selected using validation loss.

  • Beyond unitary feature encodings: General CPTP feature encodings can produce quantum kernels k(x, x′) = Tr[ρ(x)ρ(x′)] beyond unitary feature maps.The discussion contrasts these encodings with unitary maps and notes that tracing out part of the system can approximate kernels from unitary encodings.
  • Data generation: Fashion MNIST images are reduced by PCA to n components, with 2 ≤ n ≤ 12, then normalized component-wise before training and testing.The resulting vectors lie in R^n; the training set samples M = 1000 examples.
  • Quantum models: The explicit simulation model combines Havlíček feature encoding, hardware-efficient rotations and nearest-neighbour CZ gates, followed by a re-normalized Z1 expectation value.The appendix figure uses L = 2 layers, while the detailed simulations vary L so that 3nL is approximately 90.
  • Quantum models: Explicit models train variational parameters and an observable weight by gradient descent, whereas implicit models use the same encoding with kernel-ridge regression.The implicit simulations include unregularized training, with regularized results reported separately.
  • Classical baselines: Classical comparisons include random forests, gradient boosting, AdaBoost, neural networks, linear kernels, and Gaussian kernels, with hyperparameters selected by grid search where specified.At each system size, the model with the lowest validation loss is retained and its test loss is plotted.
  • Additional simulations: Additional simulations test regularization for implicit models and explicit models drawn from a mismatched variational family.The appendix reports these experiments as support for the main-text claims.

Appendix F: Additional numerical simulations

The appendix derives lower bounds for linear and implicit quantum models using sparse parity functions, Hilbert-space dimension arguments, and bounds on training-set spans. These results contrast with the single-qubit data re-uploading construction developed later.

  • Lower bounds for linear models: Linear quantum models require Ω(d) qubits to achieve non-trivial expected loss on the constructed parity-learning task.The result follows from the required dimension of the representable function subspace.
  • Parity-function task: The separation task uses k-sparse parity functions over {−1, +1}^d, whose mutually orthogonal structure supports dimensionality lower bounds.The analysis uses the uniform input distribution and mean-squared loss for its linear-model bounds.
  • Proof strategy: The parity lower bounds rely on a theorem that converts approximation error over many orthogonal functions into a lower bound on the dimension of the model subspace.The theorem is applied to the parity concept class under the chosen input distribution and loss.
  • Lower bounds for linear models: For an n-qubit linear model, the representable function subspace has dimension at most 2^(2n), because the feature space consists of 2^n × 2^n Hermitian operators.Combining this upper bound with the parity-family lower bound yields the qubit requirement.
  • Lower bounds for implicit models: Implicit models additionally require Ω(2^d) training samples because their weight vectors lie in the span of embedded training examples.This gives dim(W) ≤ min(2^(2n), M), producing both qubit and sample lower bounds.

b. Upper bound for data re-uploading models

The appendix constructs a single-qubit data re-uploading circuit that represents parity functions and analyzes how many samples suffice to learn the relevant subset of input coordinates.

  • Circuit mechanism: The circuit encodes parity in the qubit’s |+⟩ or |−⟩ state, while parametrized Ry rotations determine which data-encoding Rz gates act on it.Rz(exi) flips the parity state when xi = −1 and preserves it otherwise; Ry rotations hide or expose the state to each gate.
  • Exact representation: A single-qubit data re-uploading model with depth 2d + 1 represents any parity function exactly.The construction sets θi = π/2 for coordinates in A and θi = 0 otherwise.
  • Learning from data: Under the constructed mixture distribution, O(log(d)) samples suffice for data re-uploading models, while the same distribution preserves the Ω(2^d) lower bound for implicit models.The mixture reveals the relevant subset statistically while retaining the generalization hardness needed for the separation.
  • Open question: The appendix leaves open whether comparable learning guarantees can be obtained with a gradient-descent optimization procedure.The stated constructive guarantee uses a coordinate-wise empirical-loss procedure instead.

c. Main theorem

The main theorem combines the linear-model lower bounds with the data re-uploading upper bounds on a parity-learning task. It establishes distinct qubit and data requirements and an associated mapping overhead.

  • Main theorem: For the constructed task, linear quantum models require Ω(d) qubits, while implicit models additionally require Ω(2^d) data samples.These bounds concern achieving the stated non-trivial average mean-squared-error threshold.
  • Main theorem: A single-qubit data re-uploading model can be trained to perfect expected loss with probability 1 − δ using M = 32 log(d/δ) samples.The theorem attributes this result to the upper-bound construction and learning algorithm.
  • Mapping overhead: Any universal mapping from an arbitrary data re-uploading model with d encoding gates to an equivalent explicit model requires Ω(d) additional qubits in the worst case.The lower bound follows because sublinear overhead would contradict the linear-model parity lower bound.
  • Mapping overhead: The proposed gate-teleportation mapping uses O(d log(d/δ′)) additional qubits, which the appendix describes as essentially optimal in this overhead measure.δ′ is a controllable parameter in the mapping construction.
  • Scope boundary: The reported separations are established for regression with mean-squared loss; extending robust lower bounds to binary classification remains an open question.Exact-learning lower bounds for linear classifiers are described, but robust ε-loss bounds are identified as harder.
Loading 2110.13162v3…