  Optimization problems in disciplines such as machine learning are commonly
solved with iterative methods. Gradient descent algorithms find local minima by
moving along the direction of steepest descent while Newton's method takes into
account curvature information and thereby often improves convergence. Here, we
develop quantum versions of these iterative optimization algorithms and apply
them to polynomial optimization with a unit norm constraint. In each step,
multiple copies of the current candidate are used to improve the candidate
using quantum phase estimation, an adapted quantum principal component analysis
scheme, as well as quantum matrix multiplications and inversions. The required
operations perform polylogarithmically in the dimension of the solution vector
and exponentially in the number of iterations. Therefore, the quantum algorithm
can be beneficial for high-dimensional problems where a small number of
iterations is sufficient.
