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

The paper addresses the high computational cost and carbon footprint of training large-scale machine-learning models (e.g., LLMs like GPT-3). It explores whether fault-tolerant quantum computing can provide algorithmic improvements with theoretical guarantees for widely used classical methods, particularly (stochastic) gradient descent (SGD). The authors note limitations of current quantum machine learning: near-term approaches lack guarantees, and existing fault-tolerant speedups often target highly structured or quantum-data problems not aligned with mainstream classical ML. The goal is to design end-to-end quantum algorithms that can enhance training of large classical models in practical regimes by leveraging sparsity and dissipative training dynamics, thereby potentially reducing time and resource requirements while maintaining scalability.

The authors review quantum machine learning literature, highlighting that many near-term algorithms lack theoretical evidence of outperforming classical counterparts, while fault-tolerant proposals show super-polynomial speedups mainly for highly structured tasks or quantum-data scenarios. Prior work includes HHL for sparse linear systems and efficient quantum algorithms for dissipative nonlinear differential equations. They argue that these do not yet address mainstream classical ML training with classical data at large scales. They also reference classical sparsity and pruning literature (e.g., lottery ticket hypothesis) as a basis for leveraging sparse training to enable efficient quantum-classical interfacing.

The approach adapts quantum algorithms for dissipative differential equations to discrete (stochastic) gradient descent training. Core elements: 1) Model setup: Consider an n-parameter model trained via T iterations of SGD with small learning rate, possibly with stochastic noise. 2) Discrete Carleman linearization: Formulate the nonlinear recursion of SGD into a higher-dimensional linear system using a quantum Carleman linearization that captures tensor products of parameters up to a truncation order. The authors develop a novel discrete theory, including tensor network diagrammatics and higher-order corrections, distinct from continuous-time formulations. 3) Conditions: Require sparsity in both the model and parameter vectors to enable efficient state preparation and readout, and dissipativity in the training dynamics to control truncation errors. 4) Quantum pipeline: (i) Start from initial parameters θ(0), training horizon T, and architecture with explicit gradient form. (ii) Construct the Carleman matrix M (QCM) from model nonlinearities. (iii) Prepare the sparse θ(0) as a quantum state using efficient sparse state preparation (or QRAM if available, though not required). (iv) Solve the resulting linear system corresponding to the discretized, truncated Carleman dynamics over T steps via an HHL-type solver, effectively performing the SGD trajectory in O(polylog(n) × T) or O(polylog(n) × T^2) time under stated conditions. (v) Recover classical parameters θ(T) using efficient tomographic techniques tailored for sparse states. 5) Discrete vs continuous nuances: In discrete time, A includes higher-order terms in the learning rate (η^2 F^2, η^3 F^3, ...), unlike the purely linear dependence in continuous-time formulations; these contributions vanish as η→0. The truncation error is well-controlled for sufficiently dissipative systems (dominance of positive Hessian eigenvalues). 6) Practical training scheme: During sparse training, periodically download parameters and re-upload to reset error growth; optionally perform a small number of classical steps (e.g., 10) before re-upload when QRAM is assumed to mitigate Hessian broadening effects.

- Theoretical results: Theorem 1 (informal) establishes that for sparse models with size n, T iterations, and fully dissipative dynamics with small learning rates, there exists a quantum algorithm running in O(T × poly(log n)) time with precision ε>0, including efficient upload/download due to sparsity. Theorem 2 (informal) shows that for almost dissipative dynamics, the runtime is O(T^2 × poly(log n)) with precision ε>0. - Algorithmic contribution: A discrete Carleman linearization framework for SGD is developed, enabling an HHL-based solution to the resulting sparse linear systems under dissipativity and sparsity, with controlled truncation errors. - Numerical evidence: Experiments on ResNet models: (i) A 7 million-parameter model trained on 100-class image classification shows initial dissipative training dynamics (Hessian spectra dominated by positive modes), an error proxy that initially decreases and later grows exponentially, motivating periodic download/re-upload every 100 steps to reset error accumulation. Training accuracy exhibits dips after re-upload but recovers; Hessian broadening observed. (ii) A 103 million-parameter ResNet pruned to 10% density shows initial Hessian dominated by dissipative modes, suggesting manageable error growth similar to the smaller model. - Practical scheme: With QRAM, performing ~10 classical dense training steps after download before re-upload helps counteract Hessian broadening without significant overall cost (linear in n for those few steps). - Precision considerations: Sparse state tomography can recover parameters with precision scaling as 1/sqrt(2^T) for the quantum ODE solver output, which may be optimal quantumly but not necessarily comparable to classical precision-cost trade-offs.

The findings suggest that fault-tolerant quantum algorithms can augment classical training in regimes where models and parameter vectors remain sufficiently sparse and where early training dynamics are dissipative. By mapping SGD to a sparse linear system via discrete Carleman linearization and solving with HHL, the approach can achieve polylogarithmic scaling in model size n and linear or quadratic scaling in iterations T, potentially outperforming known classical gradient-based methods in these regimes. Numerical Hessian analyses indicate that early training exhibits sufficient dissipativity to control linearization/truncation errors, supporting periodic download/re-upload strategies to manage error growth. The approach targets enhancing specific classical algorithms rather than guaranteeing superiority over all classical methods; nonetheless, because efficiently solving general nonlinear dissipative ODEs is BQP-hard, straightforward classical de-quantization appears implausible. The work aligns with sparsity-oriented ML practices (e.g., lottery ticket hypothesis) and points to a hybrid quantum-classical workflow that could improve scalability and sustainability of large-scale training.

The paper proposes and analyzes a fault-tolerant quantum framework to accelerate (stochastic) gradient descent for large-scale classical neural networks by leveraging sparsity and dissipativity, using discrete Carleman linearization and HHL-based solvers. Theoretical bounds indicate O(T × polylog(n)) or O(T^2 × polylog(n)) runtimes under fully or almost dissipative dynamics, respectively. Numerical studies up to 103 million parameters support the presence of dissipative regimes and outline practical training schemes with periodic parameter download/re-upload and optional brief classical interludes. Future directions include time-dependent formulations along training trajectories, refined dissipation criteria, connections to diffusion models and LLMs, improved truncated HHL algorithms, and mechanisms for quantum speedups beyond dissipation-based approaches.

- Applicability requires sufficient sparsity in both model structure and parameter vectors to enable efficient state preparation and tomography; sparsity ratios may decay during training. - Training dynamics must be fully or almost dissipative with small learning rates to control truncation and linearization errors; error can grow exponentially outside these regimes, necessitating periodic re-upload. - The method assumes availability of explicit gradient forms to construct the Carleman linearization; this may be challenging for complex architectures. - Precision and readout: Tomographic recovery scales unfavorably with iteration horizon (e.g., precision ~1/sqrt(2^T)); classical-quantum I/O can be a bottleneck. - Hardware requirements: Assumes fault-tolerant quantum computers; QRAM can help but is not required and remains technologically challenging. - Comparative advantage is shown for specific gradient-based workflows; there is no guarantee of outperforming all classical methods, especially non-gradient-based algorithms. - Numerical validation focuses on Hessian spectra and selected training behaviors; full end-to-end large-scale training with quantum resources is not demonstrated experimentally.