# Quantum advantage for learning shallow neural networks with natural data distributions

arXiv: https://arxiv.org/abs/2503.20879 · HTML: https://mlsanity.com/paper/2503.20879/

## 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 (most cited first, 30 of 32)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Implicit Neural Representations with Periodic Activation Functions](https://mlsanity.com/paper/2006.09661/) (2020)
- [pi-GAN: Periodic Implicit Generative Adversarial Networks for 3D-Aware Image Synthesis](https://mlsanity.com/paper/2012.00926/) (2020)
- [Quantum advantage in learning from experiments](https://mlsanity.com/paper/2112.00778/) (2021)
- [Spurious Local Minima are Common in Two-Layer ReLU Neural Networks](https://mlsanity.com/paper/1712.08968/) (2017)
- [Failures of Gradient-Based Deep Learning](https://mlsanity.com/paper/1703.07950/) (2017)
- [Quantum Recommendation Systems](https://mlsanity.com/paper/1603.08675/) (2016)
- [Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs](https://mlsanity.com/paper/1702.07966/) (2017)
- [Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descent](https://mlsanity.com/paper/2006.12011/) (2020)
- [Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization](https://mlsanity.com/paper/1512.09170/) (2015)
- [Building high accuracy emulators for scientific simulations with deep neural architecture search](https://mlsanity.com/paper/2001.08055/) (2020)
- [Optimal Quantum Sample Complexity of Learning Algorithms](https://mlsanity.com/paper/1607.00932/) (2016)
- [Quantum Deep Learning](https://mlsanity.com/paper/1412.3489/) (2014)
- [Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixtures](https://mlsanity.com/paper/2204.02550/) (2022)
- [Quantum statistical query learning](https://mlsanity.com/paper/2002.08240/) (2020)
- [Periodic Activation Functions Induce Stationarity](https://mlsanity.com/paper/2110.13572/) (2021)
- [On the Cryptographic Hardness of Learning Single Periodic Neurons](https://mlsanity.com/paper/2106.10744/) (2021)
- [On the approximation by single hidden layer feedforward neural networks with fixed weights](https://mlsanity.com/paper/1708.06219/) (2017)
- [On the Complexity of Learning Neural Networks](https://mlsanity.com/paper/1707.04615/) (2017)
- [Hardness of Learning Neural Networks under the Manifold Hypothesis](https://mlsanity.com/paper/2406.01461/) (2024)
- [Quantum assisted Gaussian process regression](https://mlsanity.com/paper/1512.03929/) (2015)
- [Hardness of Learning Neural Networks with Natural Weights](https://mlsanity.com/paper/2006.03177/) (2020)
- [Quantum Learning Boolean Linear Functions w.r.t. Product Distributions](https://mlsanity.com/paper/1902.08753/) (2019)
- [On the average-case complexity of learning output distributions of quantum circuits](https://mlsanity.com/paper/2305.05765/) (2023)
- [Two new results about quantum exact learning](https://mlsanity.com/paper/1810.00481/) (2018)
- [Physics-informed Neural Networks with Periodic Activation Functions for Solute Transport in Heterogeneous Porous Media](https://mlsanity.com/paper/2212.08965/) (2022)
- [Improved Quantum Boosting](https://mlsanity.com/paper/2009.08360/) (2020)
- [Learnability of the output distributions of local quantum circuits](https://mlsanity.com/paper/2110.05517/) (2021)
- [On Lattices, Learning with Errors, Random Linear Codes, and Cryptography](https://mlsanity.com/paper/2401.03703/) (2024)
- [On the Role of Entanglement and Statistics in Learning](https://mlsanity.com/paper/2306.03161/) (2023)

## Built on by (most cited first, 3 of 3)

- [Generative quantum advantage for classical and quantum problems](https://mlsanity.com/paper/2509.09033/) (2025)
- [Expressive and Scalable Quantum Fusion for Multimodal Learning](https://mlsanity.com/paper/2510.06938/) (2025)
- [Improving Sample Efficiency in Peptide-HLA Binding Prediction with Hybrid Quantum-Classical Neural Networks](https://mlsanity.com/paper/2609.19642/) (2026)

## 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.