标题： Q-Newton：使用牛顿梯度下降加速神经网络训练的混合量子经典调度 显示英文标题

标题： Q-Newton: Hybrid Quantum-Classical Scheduling for Accelerating Neural Network Training with Newton's Gradient Descent

摘要： 深度学习中的优化技术主要由一阶梯度方法引领，例如随机梯度下降（SGD）。 然而，神经网络训练可以极大地受益于二阶优化的快速收敛特性。 牛顿梯度下降在此类别中脱颖而出，它通过使用逆海森矩阵来重新缩放梯度。 然而，其主要瓶颈之一是矩阵求逆，这在$O(N^3)$时间内具有显著的计算时间，且扩展性较弱。 矩阵求逆可以转化为求解一系列线性方程。 鉴于量子线性求解算法（QLSAs），利用量子叠加和纠缠原理，可以在$\text{polylog}(N)$时间范围内运行，它们提供了一种具有指数加速潜力的方法。 具体而言，最近的QLSAs之一展示了复杂度为$O(d\cdot\kappa \log(N\cdot\kappa/\epsilon))$的规模，这取决于矩阵的{大小~$N$，条件数~$\kappa$，误差容限~$\epsilon$，量子预言稀疏性~$d$}。 然而，这也意味着它们的潜在指数优势可能受到某些特性（即$\kappa$和$d$）的阻碍。 我们提出了Q-Newton，一种用于加速牛顿梯度下降神经网络训练的混合量子-经典调度器。 Q-Newton利用一个简化的调度模块，在量子和经典线性求解器之间进行协调，通过估计和减少$\kappa$并为量子求解器构建$d$。 我们的评估展示了Q-Newton相比常用的优化器如SGD显著减少总训练时间的潜力。 我们假设了一个未来场景，其中量子机器的门时间将被减少，这可能通过阿秒物理实现。 我们的评估为量子计算的发展设定了一个雄心勃勃且有前景的目标。 显示英文摘要

摘要： 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(N^3)$ 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 $\text{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\cdot\kappa \log(N\cdot\kappa/\epsilon))$, depending on: {size~$N$, condition number~$\kappa$, error tolerance~$\epsilon$, quantum oracle sparsity~$d$} of the matrix. However, this also implies that their potential exponential advantage may be hindered by certain properties (i.e. $\kappa$ 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 $\kappa$ 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.