When Quantum and Classical Models Disagree: Learning Beyond Minimum Norm Least Square
arXiv:2411.04940 · doi:10.1038/s41534-026-01217-y
Abstract
Quantum Machine Learning algorithms based on Variational Quantum Circuits (VQCs) are important candidates for useful application of quantum computing. It is known that a VQC is a linear model in a feature space determined by its architecture. Such models can be compared to classical ones using various sets of tools, and surrogate models designed to classically approximate their results were proposed. At the same time, quantum advantages for learning tasks have been proven in the case of discrete data distributions and cryptography primitives. In this work, we propose a framework to avoid Random Feature approximation techniques. Using previous results, we establish conditions on the weight vectors of the quantum models that are necessary to avoid these dequantization methods. We show that this theory is compatible with previously proven quantum advantages on discrete inputs, and provides examples of advantages for continuous inputs. This separation is connected to large weight vector norm, and we suggest that this can only happen with a high dimensional feature map. Our results demonstrate that it is possible to design quantum models that cannot be classically approximated with good generalization. In addition, we provide a method to verify that the necessary condition is respected for a quantum model. Finally, we discuss how concentration issues must be considered to design such instances. We expect that our work will be a starting point to design near-term quantum models that avoid dequantization methods by ensuring non-classical convergence properties, and to identify existing quantum models that can be classically approximated.
References in corpus (26)
- Quantum Machine Learning
- Quantum algorithm for solving linear systems of equations
- Variational Quantum Algorithms
- Supervised learning with quantum enhanced feature spaces
- Barren plateaus in quantum neural network training landscapes
- Circuit-centric quantum classifiers
- The effect of data encoding on the expressive power of variational quantum machine learning models
- Challenges and Opportunities in Quantum Machine Learning
- Integration with respect to the Haar measure on unitary, orthogonal and symplectic group
- Connecting ansatz expressibility to gradient magnitudes and barren plateaus
- Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
- A rigorous and robust quantum speed-up in supervised machine learning
- Quantum machine learning beyond kernel methods
- Supervised quantum machine learning models are kernel methods
- Quantum Recommendation Systems
- Does provable absence of barren plateaus imply classical simulability?
- Shadows of quantum machine learning
- Generalization despite overfitting in quantum machine learning models
- Classical surrogates for quantum learning models
- Exponential data encoding for quantum supervised learning
- Potential and limitations of random Fourier features for dequantizing quantum machine learning
- Constrained and Vanishing Expressivity of Quantum Fourier Models
- Subspace Preserving Quantum Convolutional Neural Network Architectures
- Exponential separations between classical and quantum learners
- Ground state-based quantum feature maps
- On Dequantization of Supervised Quantum Machine Learning via Random Fourier Features