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

Large-scale machine learning models, while revolutionary, present significant challenges in terms of computational cost, power consumption, and training time. The environmental impact is substantial; for instance, training GPT-3 reportedly cost millions of dollars and generated hundreds of tons of CO2 equivalent emissions. This necessitates the development of more sustainable and efficient training methods. Quantum computing is a promising area for enhancing machine learning, with numerous proposals for using quantum algorithms to improve classical approaches. However, many current quantum machine learning algorithms lack theoretical guarantees of outperforming their classical counterparts, especially in fault-tolerant settings. While some theoretical results demonstrate super-polynomial quantum speedups for highly structured problems, these are often far from real-world applications. Many existing methods use quantum states as training data, a departure from typical classical machine learning practices. This work aims to bridge this gap by designing end-to-end quantum machine learning algorithms with theoretical guarantees and applicability to large-scale problems.

The paper reviews existing quantum machine learning algorithms, highlighting their limitations. Many near-term algorithms lack theoretical justification for outperforming classical methods. Fault-tolerant quantum machine learning algorithms have shown theoretical speedups, but these often apply to highly structured problems not reflective of current state-of-the-art machine learning. The authors note a gap between theoretical advancements and practical applications in large-scale machine learning. Existing work often utilizes quantum states as training data, which is not the primary focus of most current classical machine learning applications. The paper emphasizes the need for quantum algorithms that provide theoretical guarantees and address practical challenges in large-scale model training, such as sustainability and scalability.

The authors propose a hybrid quantum-classical algorithm for training large machine learning models. This approach leverages the efficiency of quantum algorithms for solving differential equations to tackle the stochastic gradient descent (SGD) problem, a cornerstone of machine learning. The core idea is to use quantum Carleman linearization to transform the non-linear SGD equations into a linear form suitable for the Harrow-Hassidim-Lloyd (HHL) algorithm, a quantum algorithm for solving linear systems of equations. This method requires the model and weight vectors to be sparse and the model to be sufficiently dissipative. Sparsity ensures efficient data transfer between classical and quantum processors (though the authors note that this could be relaxed with quantum random access memory, QRAM). Dissipation, which is observed in the early stages of large-scale model training, helps control the error introduced by linearization. The algorithm involves several steps: (1) Linearizing the model using quantum Carleman linearization; (2) Uploading the sparse weight vector to the quantum computer; (3) Solving the linearized equations using a modified HHL algorithm; (4) Downloading and obtaining the classical model parameters using tomographic methods. The authors provide theoretical analysis establishing the time complexity of their algorithm, showing that it scales better than known classical algorithms in terms of model size (n). However, they acknowledge that for a given problem, there's no guarantee that their hybrid approach will always outperform all classical algorithms. The supplementary material includes a detailed description of the discrete Carleman linearization, including error analysis and higher-order corrections. The authors thoroughly discuss the differences between their discrete approach and previous continuous methods. Importantly, they clarify that their approach assumes the availability of the gradient descent equation's explicit form, to enable construction of the Carleman linearization. They leave the exploration of more complex scenarios to future research.

The paper presents two main theorems (informally stated): Theorem 1: For sparse, fully dissipative models with small learning rates, a quantum algorithm exists with time complexity O(T x poly(log n)). Theorem 2: For sparse, almost dissipative models with small learning rates, a quantum algorithm exists with time complexity O(T² x poly(log n)). These theorems highlight the potential quantum speedup achievable for specific classes of machine learning models. Numerical experiments on ResNet models with 7 million and 103 million parameters support the theoretical findings. The analysis of Hessian spectra during training reveals that the dissipative nature of the early training process leads to an initial reduction in a proxy for error. However, this error grows exponentially later in the training. To mitigate this, the authors propose a sparse parameter download and re-upload scheme, updating the model on the quantum computer periodically. This strategy maintains a manageable error bound, although it might lead to temporary accuracy dips. Experiments also suggest that using classical training for a short period after downloading parameters (before re-uploading) could improve accuracy. The Hessian analysis of the 103 million parameter model after pruning shows a dominance of dissipative modes, indicating the potential for similar quantum enhancement as observed in the smaller model.

The results suggest that quantum computing could significantly improve the scalability and sustainability of training large-scale classical machine learning models. The authors argue that their algorithm is not easily de-quantized by classical methods. The focus is on augmenting classical training with a key quantum step that constitutes a bottleneck in the classical process. The requirement of sparsity is consistent with the lottery ticket hypothesis in classical machine learning, where a small subset of the network's parameters can achieve good performance. While sparsity might decrease during training, the authors propose strategies to mitigate this. The paper's findings open new avenues of research in quantum machine learning, including exploring time-dependent versions of the algorithm, developing better dissipation criteria, and investigating connections with diffusion models and LLMs. The algorithm's limitation of requiring an explicit form of the gradient equation remains a limitation for complex models.

This research presents a novel hybrid quantum-classical algorithm for training large machine learning models that offers a potential quantum speedup under specific conditions of sparsity and dissipation. The theoretical analysis and numerical experiments provide evidence of this quantum enhancement, but further research is needed to explore the full potential and applicability to a wider range of models. Future directions include developing more robust algorithms, exploring different linearization techniques, and investigating alternative approaches to handle non-sparse models.

The proposed algorithm's effectiveness relies on model sparsity and dissipation. While sparsity is consistent with some existing techniques in machine learning, it might be challenging to maintain a high degree of sparsity throughout the entire training process. The requirement of an explicit form for the gradient descent equation limits the algorithm's applicability to complex models where analytical decomposition might be computationally expensive. Furthermore, the accuracy improvement from the proposed quantum algorithm is observed at the early stages of training, and its performance compared to purely classical algorithms in later stages of training is unclear. The dependence on tomographic methods for downloading quantum states also introduces a limitation in the form of error scaling with the number of iterations.