본 논문은 뉴턴의 경사 하강법(Newton's GD)을 가속화하기 위한 하이브리드 양자-고전 스케줄러인 Q-Newton을 제안한다. 뉴턴의 경사 하강법은 빠른 수렴 특성을 가지지만, 역 헤시안 행렬의 계산에 $O(N^3)$ 시간이 소요되는 행렬 역전 문제가 있다. 본 논문에서는 양자 선형 솔버 알고리즘(QLSA)을 이용하여 이 문제를 해결하고자 한다. QLSAs는 $\text{polylog}(N)$ 시간 내에 작동하여 지수적인 가속화를 제공할 수 있지만, 조건수($\kappa$)와 양자 오라클의 스파스티($d$)에 따라 성능이 제한될 수 있다. Q-Newton은 조건수를 추정하고 줄이며, 양자 솔버를 위한 스파스티를 구성하는 간소화된 스케줄링 모듈을 통해 양자 및 고전 선형 솔버 간의 협업을 조율한다. 실험 결과, Q-Newton이 SGD와 같은 일반적인 최적화 알고리즘에 비해 훈련 시간을 크게 단축할 수 있음을 보여준다. 향후 양자 컴퓨터의 게이트 시간이 감소하면 Q-Newton의 성능이 더욱 향상될 것으로 예상한다.
