  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.
