  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.
