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

Abstract

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.

7+40 pages, 3+10 figures, replaced with final version providing substantial detail

References in corpus (6)

• Quantum algorithm for solving linear systems of equations
• Quantum random access memory
• Quantum advantage in learning from experiments
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• Solving Quantitative Reasoning Problems with Language Models
• A super-polynomial quantum-classical separation for density modelling

Cited by in corpus (14)

• A comprehensive review of Quantum Machine Learning: from NISQ to Fault Tolerance
• Generalization of Quantum Machine Learning Models Using Quantum Fisher Information Metric
• Quantum DeepONet: Neural operators accelerated by quantum computing
• QRAM: A Survey and Critique
• Explicit block encodings of boundary value problems for many-body elliptic operators
• Fundamental causal bounds of quantum random access memories
• An Early Investigation of the HHL Quantum Linear Solver for Scientific Applications
• Accelerating the drive towards energy-efficient generative AI with quantum computing algorithms
• The Role of Quantum Computing in Advancing Scientific High-Performance Computing: A perspective from the ADAC Institute
• Comprehensive Library of Variational LSE Solvers
• Engineering Quantum Reservoirs through Krylov Complexity, Expressivity and Observability
• Experimentally validated quantum-secure federated learning over a multi-user quantum network
• Single-Qudit Quantum Neural Networks for Multiclass Classification
• Randomized adiabatic quantum linear solver algorithm with optimal complexity scaling and detailed running costs