Quantum advantage for learning shallow neural networks with natural data distributions
Not on the map. Why?
Abstract (arXiv)
Without large quantum computers to empirically evaluate performance, theoretical frameworks such as the quantum statistical query (QSQ) are a primary tool to study quantum algorithms for learning classical functions and search for quantum advantage in machine learning tasks. However, we only understand quantum advantage in this model at two extremes: either exponential advantages for uniform input distributions or no advantage for arbitrary distributions. Our work helps close the gap between these two regimes by designing an efficient quantum algorithm for learning periodic neurons in the QSQ model over a variety of non-uniform distributions and the first explicit treatment of real-valued functions. We prove that this problem is hard not only for classical gradient-based algorithms, which are the workhorses of machine learning, but also for a more general class of SQ algorithms, establishing an exponential quantum advantage.
Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 32 of its 136 references that are in the map. First posted on arXiv 26 Mar 2025.
Builds on
32 of 136 references.
References · 32
- 2020Language Models are Few-Shot Learnerscited by 32,419
- 2020Implicit Neural Representations with Periodic Activation Functionscited by 2,238
- 2020pi-GAN: Periodic Implicit Generative Adversarial Networks for 3D-Aware Image Synthesiscited by 708
- 2021Quantum advantage in learning from experimentscited by 188
- 2017Spurious Local Minima are Common in Two-Layer ReLU Neural Networkscited by 104
- 2017Failures of Gradient-Based Deep Learningcited by 80
- 2016Quantum Recommendation Systemscited by 70
- 2017Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputscited by 61
- 2020Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descentcited by 58
- 2015Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimizationcited by 41
- 2020Building high accuracy emulators for scientific simulations with deep neural architecture searchcited by 36
- 2016Optimal Quantum Sample Complexity of Learning Algorithmscited by 33
20 more
- 2014Quantum Deep Learningcited by 31
- 2022Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixturescited by 26
- 2020Quantum statistical query learningcited by 21
- 2021Periodic Activation Functions Induce Stationaritycited by 21
- 2021On the Cryptographic Hardness of Learning Single Periodic Neuronscited by 20
- 2017On the approximation by single hidden layer feedforward neural networks with fixed weightscited by 19
- 2017On the Complexity of Learning Neural Networkscited by 18
- 2024Hardness of Learning Neural Networks under the Manifold Hypothesiscited by 18
- 2015Quantum assisted Gaussian process regressioncited by 17
- 2020Hardness of Learning Neural Networks with Natural Weightscited by 15
- 2019Quantum Learning Boolean Linear Functions w.r.t. Product Distributionscited by 9
- 2023On the average-case complexity of learning output distributions of quantum circuitscited by 9
- 2018Two new results about quantum exact learningcited by 8
- 2022Physics-informed Neural Networks with Periodic Activation Functions for Solute Transport in Heterogeneous Porous Mediacited by 8
- 2020Improved Quantum Boostingcited by 7
- 2021Learnability of the output distributions of local quantum circuitscited by 7
- 2024On Lattices, Learning with Errors, Random Linear Codes, and Cryptographycited by 7
- 2023On the Role of Entanglement and Statistics in Learningcited by 5
- 2024Learning low-degree quantum objectscited by 2
- 2024Testing classical properties from quantum datacited by 2
Built on by
Citing papers per year: 2025: 2; 2026: 1.
3 papers.