Power of data in quantum machine learning

The paper investigates when and how quantum machine learning (QML) can offer a predictive advantage over classical machine learning (CML) when training data are available. While quantum devices can generate distributions or correlations believed hard to compute or sample classically, the authors hypothesize that access to data can elevate classical learners to accurately predict even classically intractable quantum-generated functions. They aim to formalize this intuition with rigorous prediction error bounds and to develop practical tests to prescreen potential quantum prediction advantage. The study situates itself in the broader context of rapid advances in both quantum technologies and classical ML, emphasizing that claims of quantum advantage must account for the power of data-driven classical learning and that advantages from optimization speedups alone are typically limited to small polynomial gains.

Two main avenues for quantum enhancement in ML are reviewed: (1) using quantum resources to accelerate classical training or inference (e.g., improved optimization or sampling), which without additional structure generally yields at most quadratic or small polynomial speedups; and (2) leveraging intrinsically quantum models that generate correlations or distributions that are classically hard to sample, as suggested by quantum supremacy/sampling results and explored in quantum neural networks and hybrid quantum-classical feature maps. Prior arguments for QML advantage often rely on circuit sampling hardness or quantum simulation. On the classical side, the paper connects to kernel methods and recent theory showing equivalences between training wide neural networks and kernel regression via the neural tangent kernel. The authors position their approach within kernel-based learning (classical and quantum kernels), noting that quantum kernel methods relate to inner products in Hilbert space of quantum states, while classical models with appropriate kernels (including NTKs) can be highly expressive. The literature suggests both potential and pitfalls: naive quantum embeddings can produce near-orthogonal states (tiny inner products), limiting useful signal and enabling classical competitiveness when data are abundant.

The authors develop a kernel-based framework to quantify prediction performance and assess potential QML advantage. Key elements include: (1) Prediction error bounds: For models trained via kernels, generalization is controlled by a model complexity term s_k(N)=||w||^2 after training h(x)=w^T φ(x), with regularization to prevent overfitting. They derive bounds that are asymptotically tight and provide matching lower bounds; for quantum kernels, required data can scale with Tr(O^2) and the effective dimension d of the data-embedded subspace. (2) Geometric difference g: They define a geometry-based test comparing kernel matrices from two models (e.g., quantum vs classical) via g=||√K − √K′||_F under normalization Tr(K)=Tr(K′)=N. Small g implies that classical models will match or outperform the quantum model regardless of labels; large g implies existence (and efficient construction) of datasets where the quantum model predicts significantly better. The computation of g uses SVD of N×N kernel matrices on a classical computer. (3) Flowchart for advantage: A prescreening procedure uses g to assess potential for quantum advantage independent of labels, followed by label/function-specific checks via model complexities s_t and s_k. (4) Quantum kernel method: Using quantum-state overlaps (e.g., fidelities) defines K(x,x′)=ψ(x)†ψ(x′) or related forms; they bound prediction error in terms of the effective rank d of the data’s quantum Gram matrix and Tr(O^2). They note many practical observables (e.g., Pauli) can yield large Tr(O^2), making d the central quantity. (5) Projected quantum kernels: To avoid the small-g regime common for standard quantum kernels (due to high-dimensional Hilbert space with near-orthogonality), they propose projecting quantum states to approximate classical representations that increase geometric difference. A simple instance measures the one-particle reduced density matrix (1-RDM) on n qubits and defines an RBF-like kernel K^ρ(x_i,x_j)=exp(−0.5||ρ_1(x_i)−ρ_1(x_j)||^2). This projection preserves relevant structure while reducing effective dimension and increasing g against classical kernels. (6) Engineered datasets: To empirically realize maximal separation predicted by theory, they construct label functions via an eigenvalue problem to saturate geometric inequalities between classical kernels and the projected quantum kernel, across embeddings E1–E3 and system sizes up to 30 qubits. Training sets with N (e.g., N=600) are used to compare quantum kernel (Q), projected quantum kernel (PQ), and multiple classical baselines (Gaussian/linear SVM, random forest, AdaBoost, neural networks, gradient boosting). Kernel ranks/dimensions are computed via SVD of quantum-obtained kernels.

- Data can empower classical ML to accurately predict outputs of quantum processes that are classically hard to compute, undermining naive expectations of QML advantage when training data are available. - Geometric difference g between kernel geometries is a powerful, label-agnostic predictor of potential advantage: small g predicts classical parity or superiority; large g enables quantum prediction advantage on appropriately constructed datasets. - Prediction error bounds are asymptotically tight; for quantum kernels, sample complexity can scale with Tr(O^2) and the effective dimension d (rank of the quantum kernel matrix on the training data). Matching lower bounds show such scaling is unavoidable under large Hilbert-space assumptions. - Standard quantum kernels often yield small g as system size increases (effective dimension d approaches N), causing classical models to be competitive or superior. Increasing qubits naively may worsen performance due to vanishing inner products. - Projected quantum kernels that use low-order measurements (e.g., 1-RDM) increase g and reduce effective dimension, improving prediction performance versus both standard quantum kernels and classical baselines in certain regimes. - Engineered datasets designed to saturate the geometric separation show substantial prediction advantages for projected quantum kernels: accuracy gaps exceeding 20% over the best classical models at larger system sizes, with demonstrations up to 30 qubits. In contrast, standard quantum kernels showed little to no advantage at larger sizes due to small g. - Numerical experiments (e.g., with N=600 training points) confirm theoretical predictions: when g is small, classical models match or outperform quantum methods; when g is large (e.g., with embedding E3 and projected kernels), quantum methods achieve stronger prediction accuracy. - The advantage observed for projected kernels is robust across a suite of classical baselines, including models without clear kernel interpretations (e.g., random forests).

The findings resolve a key question: even if a quantum process is hard to simulate classically, does that ensure a learning advantage for quantum models? The answer is no—when data are available, classical learners can generalize effectively if the geometry induced by classical kernels aligns with that of the quantum data. The geometric difference framework provides a practical, function-agnostic test for potential quantum advantage and clarifies why naive quantum embeddings often fail to yield advantages: the induced state space is too high-dimensional with near-orthogonal embeddings, leading to small g and poor signal. Projected quantum kernels address this by extracting informative low-order observables that increase g while keeping effective dimension low, yielding improved generalization. These results connect theory with practice: tight error bounds delineate when QML can or cannot help, and engineered datasets demonstrate that sizable prediction advantages are possible and scalable with qubit number under appropriate embeddings. The work emphasizes that claims of quantum learning advantage must benchmark against strong classical learners and classical approximations to quantum models and that advantage is contingent on both embedding choice and data regime.

This work introduces a principled methodology for assessing quantum prediction advantage in supervised learning with data. Contributions include: (1) rigorous, asymptotically tight prediction error bounds for classical and quantum kernel-based learners; (2) a geometric difference metric and practical flowchart to prescreen and test for potential quantum advantage independent of labels; (3) the proposal of projected quantum kernels that increase geometric difference and improve prediction performance; and (4) large-scale numerical evidence, including engineered datasets up to 30 qubits, showing significant accuracy gaps (>20%) in favor of projected quantum kernels over strong classical baselines. Future research directions involve identifying embeddings that are simultaneously hard to approximate classically and yield strong signals on low-order observables at large scales, extending analyses to more realistic datasets and tasks, and developing robust implementations tolerant to device noise while maintaining geometric separation advantages.

- Many practical observables can have exponentially large Tr(O^2), limiting sample-efficiency of standard quantum kernels; effectiveness hinges on keeping the effective dimension d small relative to data size. - Standard quantum kernel methods often suffer from small geometric difference as qubits increase, leading to classical competitiveness or superiority; naive scaling in qubit count can degrade performance. - Empirical demonstrations of advantage are shown on engineered datasets designed to maximize geometric separation; translating these gains to real-world datasets remains to be established. - True claims of advantage require benchmarking against strong classical learners and classical approximations to quantum models; such comprehensive benchmarking may be computationally intensive. - The approach relies on accessible projections (e.g., 1-RDM); measuring richer features may be costly on near-term devices, and noise can affect kernel estimation, though the authors note some robustness to moderate noise.