PaperlayerView exact revision on arXiv

Source-linked AI summary

Power of data in quantum machine learning

Hsin-Yuan Huang, Michael Broughton, Masoud Mohseni, Ryan Babbush, Sergio Boixo, Hartmut Neven, Jarrod R. McClean

arXiv:2011.01938v2quant-phcs.LG

TL;DR

Machine-learning tasks with provided data may differ sharply from computational tasks without data, raising questions about when quantum models can offer prediction advantages. The paper develops prediction-error bounds and a geometry-based screening methodology, then shows that data can make classical models competitive while projected quantum models can create separations. It reports engineered near-term demonstrations and a rigorous fault-tolerant speed-up, while noting an exponential training-data limitation for a simple quantum-kernel example.

  • Problem

    The paper addresses whether quantum machine learning offers prediction advantages when training data are provided, since classical models may learn quantum-generated problems that are hard to compute directly.

  • Method

    The authors derive prediction-error bounds, compare classical and quantum kernel methods through geometric differences, and construct projected quantum models and engineered data sets.

  • Results

    Classical models can rival quantum models with data, while projected quantum models produce prediction advantages over common classical models on engineered data sets up to 30 qubits.

  • Takeaways & Limitations

    Kernel geometry provides a function-independent pre-screen for deciding whether a quantum prediction advantage is possible before analyzing the specific function or labels.

  • Takeaways & Limitations

    A simple quantum-kernel example requires N ≥ (1 − ϵ)2^n training samples to achieve prediction error ≤ ϵ.

Abstract

from arXiv · show

The use of quantum computing for machine learning is among the most exciting prospective applications of quantum technologies. However, machine learning tasks where data is provided can be considerably different than commonly studied computational tasks. In this work, we show that some problems that are classically hard to compute can be easily predicted by classical machines learning from data. Using rigorous prediction error bounds as a foundation, we develop a methodology for assessing potential quantum advantage in learning tasks. The bounds are tight asymptotically and empirically predictive for a wide range of learning models. These constructions explain numerical results showing that with the help of data, classical machine learning models can be competitive with quantum models even if they are tailored to quantum problems. We then propose a projected quantum model that provides a simple and rigorous quantum speed-up for a learning problem in the fault-tolerant regime. For near-term implementations, we demonstrate a significant prediction advantage over some classical models on engineered data sets designed to demonstrate a maximal quantum advantage in one of the largest numerical tests for gate-based quantum machine learning to date, up to 30 qubits.

INTRODUCTION

The paper argues that provided training data can make classical machine learning competitive with quantum models, even for quantum-generated problems that are hard to compute classically. It develops rigorous bounds and a geometry-based workflow to assess potential quantum prediction advantage, then proposes projected quantum models for larger separations.

  • The paper studies two quantum-enhancement routes: improving classical-model training or inference, and using quantum models to generate hard-to-represent correlations.The first route may provide only quadratic or small polynomial speedups without additional structure.
  • Provided training data can elevate classical models to rival quantum models, even when quantum circuits generating the data are classically hard to compute.
  • Rigorous prediction-error bounds underpin a methodology for comparing classical and quantum kernel-based machine-learning models on quantum data.The framework also relates quantum kernels to infinite-depth quantum neural networks and includes numerical comparisons beyond kernel-associated methods.
  • The geometric difference between classical and quantum kernels provides a function-independent pre-screen for possible prediction advantage using a fixed amount of training data.A small geometric difference guarantees similar or better classical prediction, while a large difference permits construction of a data set with quantum advantage.
  • The proposed projected quantum model enlarges geometric differences and yields prediction advantages over common classical models on engineered data sets in experiments up to 30 qubits.The advantage remains robust across tested classical methods, including random forests, according to the reported numerical experiments.

A. Setup and motivating example

The paper sets up supervised learning of quantum-generated functions and uses a motivating example to show why classical prediction from data can differ from classical computation without data. It then frames both classical and quantum models through kernel methods and identifies data, encoding, and model complexity as central considerations.

  • Setup: The setup is supervised learning with N independently sampled examples {(x_i, y_i)}, where inputs come from a distribution D.Labels may be generated by a quantum model whose function the classical or quantum learner must predict.
  • Setup: Quantum inputs are encoded by a continuous unitary as |x_i⟩ = U_enc(x_i)|0⟩^⊗n, followed by a quantum neural network and observable measurement.
  • Motivating example: Without training data, efficiently computing the quantum-generated function for every U_QNN and observable O would imply BPP = BQP.The paper uses this proposition to distinguish computational hardness without data from learnability using training examples.
  • Motivating example: With N proportional to p^2/ϵ^2 training examples, a classical model can predict the motivating quantum function to additive error ϵ.This example illustrates how sufficient data can change computational-complexity considerations.
  • Motivating example: The motivating example uses amplitude encoding and a quadratic model, so the paper turns to stronger models, richer encodings, and regimes where N is much smaller than model dimension.The authors identify these as the more interesting cases addressed quantitatively.
  • Kernel methods: Kernel methods represent similarity through k(x_i, x_j), enable nonlinear feature maps, and include quantum, Gaussian, and neural-tangent-kernel constructions.The quantum kernel k_Q(x_i, x_j) = |⟨x_i|x_j⟩|^2 can learn arbitrarily deep quantum neural networks measuring observables, while the Gaussian kernel can learn any continuous function on a compact space.

B. Testing quantum advantage

The paper develops prediction-error bounds and a geometric-difference test for assessing when classical models can match or outperform quantum models on data-driven tasks. Small geometric difference favors classical competitiveness, while large geometric difference permits constructed datasets with quantum prediction advantage.

  • Prediction-error bounds: The bounds’ dependence on N captures how additional training data can improve prediction performance and reduce the possible separation between models.The paper gives a matching lower bound showing that scaling with Tr(O^2) is unavoidable for quantum-kernel learning in a large Hilbert space.
  • Prediction-error bounds: Prediction error is governed by the trained model complexity s_K(N), with smaller s_K(N) implying better generalization to new data.The quantity s_K(N) is computed from the trained kernel model and reflects whether kernel-defined closeness matches closeness in the target quantum function.
  • Geometric test: The framework evaluates quantum advantage through an asymmetric geometric difference between classical and quantum kernels, independent of function values or labels.The geometric difference can be computed classically from the kernel matrices using singular value decomposition.
  • Geometric test: Small g_CQ implies that classical models have similar or lower model complexity and will likely perform competitively with or better than the quantum model.This is the first decision step in the paper’s proposed flowchart for screening potential quantum prediction advantage.
  • Geometric test: Large g_CQ guarantees the existence of a dataset with s_C = g_CQ^2 s_Q on which the quantum model can exhibit superior prediction performance.The paper also gives an efficient construction for such a maximally divergent dataset.
  • Quantum-kernel bounds: For quantum kernels, the prediction bound depends on the effective training-space dimension d and the observable norm Tr(O^2), with s_Q ≤ min(d, Tr(O^2)).When both g_CQ and min(d, Tr(O^2)) are small, classical ML can learn any UQNN for the given encoding, even when the UQNN is arbitrarily deep.
  • Geometric test: A prediction advantage requires large separation between s_C and s_Q, meaning quantum-defined input similarities align with the target function but differ from classical similarities.This is the final test in the proposed methodology for identifying a task-specific quantum advantage.

C. Projected quantum kernels

The paper introduces projected quantum kernels to avoid the poor generalization associated with high-dimensional quantum kernels. Projection reduces the representation to a low-dimensional classical space while retaining a quantum-computationally difficult kernel evaluation.

  • Motivation: When the effective dimension d is large, the original fidelity-based quantum kernel approaches the identity matrix and its geometric difference from classical ML becomes small.In this regime, the kernel treats data points as far apart, limiting the prospect of quantum prediction advantage.
  • Projected kernels: Projected quantum kernels map quantum states into an approximate classical representation using reduced observables or classical shadows.The projection can reduce a training-space dimension d proportional to N to a lower-dimensional space that generalizes better.
  • Projected kernels: Although the representation is projected, evaluating the resulting kernel can remain difficult without a quantum computer because it passes through the exponentially large quantum Hilbert space.Numerically, the classical projection increases rather than decreases the geometric difference from classical ML models.
  • Examples and applications: A one-particle reduced-density-matrix kernel uses each encoded state’s 1-RDM as a feature map and can express arbitrary functions of powers of the 1-RDMs.The paper also describes projected kernels containing all RDM orders through local randomized measurements and classical shadows.
  • Examples and applications: Projected quantum kernels yield a simple rigorous quantum speed-up for a learning problem based on discrete logarithms.This result is presented as a fault-tolerant-regime application of the projected-kernel construction.

D. Numerical studies

Numerical studies test the framework on fashion-MNIST-derived classical and quantum tasks and on engineered datasets designed to maximize quantum-classical separation. Classical models remain competitive on naturalistic tasks, while projected quantum kernels outperform them on engineered high-geometric-difference tasks up to 30 qubits.

  • Experimental setup: The experiments use PCA-processed fashion-MNIST images as shared inputs for classical and quantum models, with quantum labels generated from observables evolved under random-coupling Heisenberg-like circuits.Classical models are selected from tuned standard algorithms, including SVMs, boosting, random forests, and neural networks.
  • Naturalistic datasets: Classical ML performs best on the original classical dataset and remains competitive or can outperform quantum ML on quantum datasets, despite lacking the quantum training embedding.The strongest classical performance occurs especially on Dataset (Q, E1) and Dataset (Q, E2).
  • Naturalistic datasets: As the standard quantum-kernel dimension grows approximately with N, its geometric difference decreases, whereas projected quantum spaces retain low dimension and higher geometric difference.The paper associates the standard-kernel dimension growth with declining performance and notes that adding qubits can worsen naive-kernel behavior through tiny inner products.
  • Engineered datasets: Engineered datasets set s_PQ = 1 and s_C = g(K_C||K_PQ)^2 to saturate the geometric inequality and maximize the predicted separation.The construction uses label functions engineered around the geometric difference between classical and projected quantum kernels.
  • Engineered datasets: More than 20% advantage is reached for projected quantum kernels at large sizes, and the advantage remains stable across common classical methods.As the encoding changes from E1 to E3 and geometric difference increases, classical and original quantum-kernel performance decline while projected-kernel performance tracks g.
  • Engineered datasets: Increasing the number of training examples improves all methods and gradually diminishes the engineered advantage.The engineered separation is reported at the largest system size studied and may persist under moderate quantum-device noise because of its margin.

DISCUSSION

The paper finds that classical models with data can rival quantum models, while projected quantum kernels produce large separations on engineered data. It also frames quantum advantage as requiring careful classical benchmarking and further validation on practical data.

  • Classical machine-learning algorithms with data can become computationally more powerful, so quantum prediction advantage is not guaranteed even for quantum-generated data.
  • Projected quantum kernels outperform all tested classical models in prediction error on engineered data sets.
  • The observed separation and trend up to 30 qubits suggest learning tasks that may be easy to verify but hard to model classically, while tolerating device noise.
  • Claims of quantum advantage require benchmarking classical models alongside classical approximations of quantum models.
  • Further work must identify useful embeddings and evaluate potential advantages on data sets closer to practical interest.

Appendix A: Rigorous proofs for statements regarding the motivating example

The appendix proves that the motivating function is generally hard to compute classically, yet a classical learner can predict it efficiently from data using a polynomial-time kernel method. This would collapse BQP and BPP if extended to arbitrary instances.

  • The motivating function is generally hard to compute classically, while learning it from data can be easy on a classical computer.
  • An estimate with absolute error below 0.15 separates positive from negative function values with high probability, allowing language membership to be decided.
  • If such a randomized classical algorithm existed, it would imply BQP ⊆ BPP and therefore BPP = BQP.
  • The classical kernel k(x_i, x_j) = (sum_l x_il x_jl)^2 is evaluable in time linear in the input dimension p.
  • This classical kernel is equivalent to the quantum kernel Tr(rho(x_i)rho(x_j)) = |<x_i|x_j>|^2 for the specified amplitude encoding.

Appendix B: Complexity-theoretic argument for the power of data

The appendix formalizes learning from sampled data through BPP/samp and relates it to established complexity classes. Its constructions show how data can encode information unavailable to ordinary classical computation, including a quantum-computable separation.

  • BPP/samp consists of probabilistic machines that generate polynomial-time samples and use polynomially many labeled samples to process inputs.
  • BPP is contained in BPP/samp because ignoring the sampled data recovers the ordinary definition of BPP.
  • BPP/samp is contained in P/poly by amplifying independent training sets, taking majority votes, and applying Chernoff and union bounds.
  • An undecidable-language construction lets one training point reveal hidden language information, enabling a classical learner to decide membership despite the language not being in BPP.
  • Quantum-generated data can replace undecidable data in the construction, yielding a separation involving a language outside BPP but inside BQP.

Appendix C: Relation between quantum kernel methods and quantum neural networks

This appendix establishes that arbitrarily deep quantum neural networks with trainable observables are formally equivalent to quantum kernel methods. It also develops prediction-error bounds based on training and generalization terms, while noting that the equivalence does not guarantee data-efficient learning.

  • Formal equivalence: Arbitrarily deep quantum neural networks with trainable observables are equivalent to quantum kernel methods using kQ(xi, xj) = Tr(ρ(xi)ρ(xj)).The equivalence follows from representing encoded inputs as quantum states and optimizing the corresponding observable or kernel model.
  • Prediction-error bounds: The prediction-error analysis decomposes error into training and generalization components governed by the kernel matrix, regularization, and the encoded quantum states.The bound is data-dependent, and regularization λ > 0 can limit model complexity and improve numerical stability.
  • Formal equivalence: The associated quantum kernel model is a linear function in a possibly infinite-dimensional Hilbert space, encompassing infinite-width neural networks and kernel regression.The kernel matrix determines the geometry between training examples and the trained model has an analytic representation.
  • Prediction-error bounds: Quantum-kernel prediction error is bounded by the smaller of the training-set quantum-subspace dimension and the Frobenius norm of the evolved observable.This characterizes the bound through the effective dimension of the states and the observable’s norm.
  • Geometric comparison: A small geometric scalar g implies that classical neural networks can predict as well as, or potentially better than, the quantum kernel method.The comparison concerns the geometry induced by classical and quantum feature spaces.

Appendix G: Constructing dataset to separate quantum and classical model

The appendix constructs training targets that maximize the separation between quantum and classical kernels by saturating their geometric difference. It also states matching sample-complexity bounds for learning quantum models in sufficiently large Hilbert spaces.

  • Dataset construction: The dataset construction targets the largest learning-theoretic separation by maximizing classical model complexity while fixing quantum complexity.The method uses generalized eigenvalue optimization over the quantum and classical kernel matrices.
  • Dataset construction: The resulting targets satisfy sC = g^2sQ = g^2, fully utilizing the geometric difference between the quantum and classical spaces.The construction sets sQ = 1 and chooses targets that maximize sC.
  • Dataset construction: The continuous targets can be converted into classification labels by thresholding at their median.Values above the median become +1, while values at or below it become −1.
  • Interpretation: The constructed dataset is intended to saturate the geometric-difference bound, so failure to observe quantum advantage would suggest little advantage for that setting.This is presented as a learning-theoretic diagnostic rather than a universal guarantee of empirical advantage.
  • Sample complexity: Quantum-kernel learning requires N scaling as O(Tr(O^2)/ϵ^2) in the upper bound, matching a worst-case lower bound of Ω(Tr(O^2)/ϵ^2).The lower bound applies when the input states can occupy a sufficiently large Hilbert space.

Appendix I: Limitations of quantum kernel methods

This appendix identifies practical limitations of native quantum-kernel methods. Although they can match a fundamental lower bound, simple functions may require exponentially many training examples or measurements when encoded in an exponentially large state space.

  • Practical limitations: Native quantum kernels can incur exponential overhead compared with trivial classical methods despite formally matching a fundamental sample-complexity lower bound.The limitation is illustrated with a simple learning task and is described as hindering practical applicability.
  • Classical comparison: For a simple linear function generated by a quantum model, classical linear regression or a single-layer neural network can learn from n training examples with high probability.The inputs are encoded as computational-basis states and the quantum model uses U = I and a Pauli-Z observable.
  • Classical comparison: The same task requires N ≥ (1 − ϵ)2^n training examples for the quantum kernel to achieve prediction error ≤ ϵ.The kernel is zero on unseen basis states, producing zero predictions while the target function remains ±1.
  • Measurement cost: In general, embedding classical inputs into an exponentially large quantum space makes distinct-state kernel values exponentially small and can require exponentially many measurements to resolve them.This measurement burden arises from the inherent quantum measurement error in estimating the kernel.

Appendix J: Projected quantum kernel methods

Projected quantum kernels address failures of native quantum kernels by mapping quantum states to approximate classical representations. The appendix generalizes these projections using reduced density matrices, including a construction containing all RDM orders.

  • Projected-kernel motivation: Projected quantum kernels use reduced physical observables or classical shadows to map quantum states into lower-dimensional classical spaces.The projection is intended to improve generalization while retaining evaluation through a potentially hard-to-simulate quantum state space.
  • Projected-kernel motivation: Native quantum kernels can fail to learn simple functions because the full exponential quantum state space makes kernel overlaps nearly zero.Projected kernels circumvent this learning difficulty by defining the kernel in a classical vector space.
  • RDM constructions: A linear kernel based on 1-RDMs can learn observables written as sums of one-body terms, while a Gaussian 1-RDM kernel can learn nonlinear functions of 1-RDMs.Kernels based on k-RDMs similarly target observables expressed as sums of k-body terms.
  • RDM constructions: The basic RDM-based projected kernels have limited function classes, motivating a more general all-orders construction.The appendix explicitly identifies restricted learnable function classes for the simpler choices.
  • RDM constructions: A kernel containing all orders of reduced density matrices can learn any quantum model with sufficient data because quantum-model outputs are linear functions of the full quantum state.The RDM feature map is evaluated using randomized local Pauli measurements and classical-shadow formalism.

Appendix K: Simple and rigorous quantum advantage over classical machine learning models

The appendix constructs a projected quantum-kernel method for a discrete-logarithm learning problem whose straightforward quantum-kernel representation requires exponentially many samples. Projecting the feature map reduces the task to learning a quadratic function, yielding input-size-independent sample complexity.

  • The discrete-logarithm learning problem asks for y(x) on uniformly sampled inputs, while computing log_g(x) is assumed classically hard.
  • The straightforward feature map |log_g(x)> makes distinct inputs maximally separated, so the original quantum kernel needs exponentially many training examples for accurate generalization.
  • Projecting |log_g(x)> into z = log_g(x)/p ∈ [0,1) converts the classification task into learning a simple quadratic decision function.
  • The projected quantum kernel efficiently represents quadratic functions az^2 + bz + c, enabling a support vector machine to fit the training data perfectly.
  • With probability at least 0.99, a perfectly fitting projected quantum-kernel model using N = O(log(1/ϵ)/ϵ^2) samples achieves the stated prediction-error bound.
  • The resulting sample complexity is independent of the input size n, establishing the appendix’s projected-quantum-kernel solution to the discrete-logarithm learning problem.

Appendix M: Additional numerical experiments

Additional experiments find no substantial large-system advantage for original quantum kernels, while projected quantum kernels show an advantage at small training sizes that shrinks as data increases. Classical prediction-error bounds follow trends similar to actual errors.

  • Large-system engineered datasets show no substantial advantage for original quantum kernels because the geometric difference from classical approaches is small.
  • At N = 100 training examples, projected quantum kernels have a non-trivial prediction advantage over the best classical machine-learning model on the E2 dataset.
  • As training-set size increases, every model improves and the prediction advantage of the projected quantum kernel shrinks.
  • Classical kernel prediction-error bounds are upper bounds on actual errors, yet their trends closely track the best classical model’s prediction performance across three quantum datasets.
Loading 2011.01938v2…