# Towards provably efficient quantum algorithms for large-scale machine-learning models

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

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- Builds on 38 of its 104 references that are in the map.
- First posted on arXiv 6 Mar 2023.

## Builds on (most cited first, 30 of 38)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [PaLM: Scaling Language Modeling with Pathways](https://mlsanity.com/paper/2204.02311/) (2022)
- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://mlsanity.com/paper/1803.03635/) (2018)
- [Solving Quantitative Reasoning Problems with Language Models](https://mlsanity.com/paper/2206.14858/) (2022)
- [SNIP: Single-shot Network Pruning based on Connection Sensitivity](https://mlsanity.com/paper/1810.02340/) (2018)
- [Variational Quantum Algorithms](https://mlsanity.com/paper/2012.09265/) (2020)
- [Supervised learning with quantum enhanced feature spaces](https://mlsanity.com/paper/1804.11326/) (2018)
- [Carbon Emissions and Large Neural Network Training](https://mlsanity.com/paper/2104.10350/) (2021)
- [Sparsity in Deep Learning: Pruning and growth for efficient inference and training in neural networks](https://mlsanity.com/paper/2102.00554/) (2021)
- [Opening the Black Box of Deep Neural Networks via Information](https://mlsanity.com/paper/1703.00810/) (2017)
- [Pruning neural networks without any data by iteratively conserving synaptic flow](https://mlsanity.com/paper/2006.05467/) (2020)
- [Picking Winning Tickets Before Training by Preserving Gradient Flow](https://mlsanity.com/paper/2002.07376/) (2020)
- [Power of data in quantum machine learning](https://mlsanity.com/paper/2011.01938/) (2020)
- [Quantum Machine Learning](https://mlsanity.com/paper/1611.09347/) (2016)
- [A rigorous and robust quantum speed-up in supervised machine learning](https://mlsanity.com/paper/2010.02174/) (2020)
- [Predicting Many Properties of a Quantum System from Very Few Measurements](https://mlsanity.com/paper/2002.08953/) (2020)
- [The large learning rate phase of deep learning: the catapult mechanism](https://mlsanity.com/paper/2003.02218/) (2020)
- [Quantum advantage in learning from experiments](https://mlsanity.com/paper/2112.00778/) (2021)
- [Pruning Neural Networks at Initialization: Why are We Missing the Mark?](https://mlsanity.com/paper/2009.08576/) (2020)
- [The Principles of Deep Learning Theory](https://mlsanity.com/paper/2106.10165/) (2021)
- [Drawing Early-Bird Tickets: Towards More Efficient Training of Deep Networks](https://mlsanity.com/paper/1909.11957/) (2019)
- [Information-theoretic bounds on quantum advantage in machine learning](https://mlsanity.com/paper/2101.02464/) (2021)
- [The Difficulty of Training Sparse Neural Networks](https://mlsanity.com/paper/1906.10732/) (2019)
- [On the Quantum versus Classical Learnability of Discrete Distributions](https://mlsanity.com/paper/2007.14451/) (2020)
- [Where is the Information in a Deep Neural Network?](https://mlsanity.com/paper/1905.12213/) (2019)

## Built on by (most cited first, 30 of 32)

- [Beyond Classical Attention: Quantum Attention for Scalable Computation](https://mlsanity.com/paper/2307.08045/) (2023)
- [Generalization of Quantum Machine Learning Models Using Quantum Fisher Information Metric](https://mlsanity.com/paper/2303.13462/) (2023)
- [Quantum Transformer: Accelerating model inference via quantum linear algebra](https://mlsanity.com/paper/2402.16714/) (2024)
- [Towards efficient quantum algorithms for diffusion probabilistic models](https://mlsanity.com/paper/2502.14252/) (2025)
- [Quantum computing and artificial intelligence: status and perspectives](https://mlsanity.com/paper/2505.23860/) (2025)
- [Experimentally validated quantum-secure federated learning over a multi-user quantum network](https://mlsanity.com/paper/2501.12709/) (2025)
- [sQUlearn -- A Python Library for Quantum Machine Learning](https://mlsanity.com/paper/2311.08990/) (2023)
- [An unconditional distribution learning advantage with shallow quantum circuits](https://mlsanity.com/paper/2411.15548/) (2024)
- [Fundamental causal bounds of quantum random access memories](https://mlsanity.com/paper/2307.13460/) (2023)
- [Comprehensive Library of Variational LSE Solvers](https://mlsanity.com/paper/2404.09916/) (2024)
- [Quantum Machine Learning: An Interplay Between Quantum Computing and Machine Learning](https://mlsanity.com/paper/2411.09403/) (2024)
- [Regression and Classification with Single-Qubit Quantum Neural Networks](https://mlsanity.com/paper/2412.09486/) (2024)
- [Q-Newton: Hybrid Quantum-Classical Scheduling for Accelerating Neural Network Training with Newton's Gradient Descent](https://mlsanity.com/paper/2405.00252/) (2024)
- [Leveraging Pre-Trained Neural Networks to Enhance Machine Learning with Variational Quantum Circuits](https://mlsanity.com/paper/2411.08552/) (2024)
- [Towards identifying possible fault-tolerant advantage of quantum linear system algorithms in terms of space, time and energy](https://mlsanity.com/paper/2502.11239/) (2025)
- [Quantum Machine Learning for UAV Swarm Intrusion Detection](https://mlsanity.com/paper/2509.01812/) (2025)
- [Accelerating Inference for Multilayer Neural Networks with Quantum Computers](https://mlsanity.com/paper/2510.07195/) (2025)
- [Quantum Deep Learning Still Needs a Quantum Leap](https://mlsanity.com/paper/2511.01253/) (2025)
- [Quantum Circuit-Based Learning Models: Bridging Quantum Computing and Machine Learning](https://mlsanity.com/paper/2602.00048/) (2026)
- [Optimal algorithmic complexity of inference in quantum kernel methods](https://mlsanity.com/paper/2604.15214/) (2026)
- [Expanding the Horizon: Enabling Hybrid Quantum Transfer Learning for Long-Tailed Chest X-Ray Classification](https://mlsanity.com/paper/2405.00156/) (2024)
- [AutoQML: A Framework for Automated Quantum Machine Learning](https://mlsanity.com/paper/2502.21025/) (2025)
- [Single-Qudit Quantum Neural Networks for Multiclass Classification](https://mlsanity.com/paper/2503.09269/) (2025)
- [Extreme Learning Machines for Attention-based Multiple Instance Learning in Whole-Slide Image Classification](https://mlsanity.com/paper/2503.10510/) (2025)
- [The Future of Internet of Things and Multimodal Language Models in 6G Networks: Opportunities and Challenges](https://mlsanity.com/paper/2504.13971/) (2025)
- [Quantum Optimization via Gradient-Based Hamiltonian Descent](https://mlsanity.com/paper/2505.14670/) (2025)
- [Quantum-Informed Contrastive Learning with Dynamic Mixup Augmentation for Class-Imbalanced Expert Systems](https://mlsanity.com/paper/2506.13987/) (2025)
- [MediQ-GAN: Quantum-Inspired GAN for High Resolution Medical Image Generation](https://mlsanity.com/paper/2506.21015/) (2025)
- [Generative modeling using evolved quantum Boltzmann machines](https://mlsanity.com/paper/2512.02721/) (2025)
- [Random-Matrix-Induced Simplicity Bias in Over-parameterized Variational Quantum Circuits](https://mlsanity.com/paper/2601.01877/) (2026)

## Abstract (arXiv)

Large machine learning models are revolutionary technologies of artificial intelligence whose bottlenecks include huge computational expenses, power, and time used both in the pre-training and fine-tuning process. In this work, we show that fault-tolerant quantum computing could possibly provide provably efficient resolutions for generic (stochastic) gradient descent algorithms, scaling as O(T^2 polylog(n)), where n is the size of the models and T is the number of iterations in the training, as long as the models are both sufficiently dissipative and sparse, with small learning rates. Based on earlier efficient quantum algorithms for dissipative differential equations, we find and prove that similar algorithms work for (stochastic) gradient descent, the primary algorithm for machine learning. In practice, we benchmark instances of large machine learning models from 7 million to 103 million parameters. We find that, in the context of sparse training, a quantum enhancement is possible at the early stage of learning after model pruning, motivating a sparse parameter download and re-upload scheme. Our work shows solidly that fault-tolerant quantum algorithms could potentially contribute to most state-of-the-art, large-scale machine-learning problems.