Quantum optimal algorithm for general polynomials

Gradient descent algorithms, which is a first-order iterative algorithm, is widely used for optimization problems. To obtain the local minimum of a objective function, one caculates the gradients at the current point in a $d$-dimension space and then move the function along the negative gradient. This procedure requires $O(poly(d))$ calculation operations, which hinders the performance of the algorithm in a high dimensional optimization situation. Here, by learning a framework of a quantum iterative optimization algorithm and introducing an adapted encoding scheme, we develop the quantum gradient operation for an in-homogenous polynomial objective function with a unit norm constraint. Under certain circumstances, the calculation operations required for the algorithm decreases and is linear with the $O(poly(log(d)))$. Besides, we experimentally demonstrate it on a 4-qubit Nuclear Magnetic Resonance(NMR) quantum system and show the feasibility in polynomial optimization. Since the potential value in high dimensional optimization problems, this algorithm is supposed to influence the interdisciplinary research including Quantum Information and Artificial Intelligence, such as Support Vector Machine, Logistic regression, (quantum) Neural network