2024/04/30 by Pingzhi Li, Li, Pingzhi, Junyu Liu +5
Computer Science · #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #FOS: Physical sciences #Machine Learning (cs.LG) #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.2405.00252
openalex publication_date 2024/04/30 · openalex created_date 2024/05/04 · openalex updated_date 2026/07/28
Optimization techniques in deep learning are predominantly led by first-order gradient methodologies, such as SGD. However, neural network training can greatly benefit from the rapid convergence characteristics of second-order optimization. Newton's GD stands out in this category, by rescaling the gradient using the inverse Hessian. Nevertheless, one of its major bottlenecks is matrix inversion, which is notably time-consuming in O(N3) time with weak scalability. Matrix inversion can be translated into solving a series of linear equations. Given that quantum linear solver algorithms (QLSAs), leveraging the principles of quantum superposition and entanglement, can operate within a polylog(N) time frame, they present a promising approach with exponential acceleration. Specifically, one of the most recent QLSAs demonstrates a complexity scaling of O(d⋅κlog(N⋅κ/ε)), depending on: size~N, condition number~κ, error tolerance~ε, quantum oracle sparsity~d of the matrix. However, this also implies that their potential exponential advantage may be hindered by certain properties (i.e. κ and d). We propose Q-Newton, a hybrid quantum-classical scheduler for accelerating neural network training with Newton's GD. Q-Newton utilizes a streamlined scheduling module that coordinates between quantum and classical linear solvers, by estimating & reducing κ and constructing d for the quantum solver. Our evaluation showcases the potential for Q-Newton to significantly reduce the total training time compared to commonly used optimizers like SGD. We hypothesize a future scenario where the gate time of quantum machines is reduced, possibly realized by attoseconds physics. Our evaluation establishes an ambitious and promising target for the evolution of quantum computing.