Southwest Quantum Information and Technology

Optimizing quantum optimization algorithms via faster quantum gradient computation

Presenting Author: Nathan Wiebe, Microsoft Research
Contributing Author(s): Andres Gilyen, Srinivasan Arunachalam

We consider a generic framework of optimization algorithms based on gradient descent. We develop a quantum algorithm that calculates the gradient of a multi-variate real-valued function by evaluating it at only a logarithmic number of points in superposition. Our algorithm is an improved version of Jordan's gradient calculation algorithm, providing an approximation of the gradient of the function with quadratically better dependence on the evaluation accuracy of the function, for a class of smooth functions. Furthermore, we show that most functions arising from quantum optimization algorithms satisfy the necessary smoothness conditions; our new algorithm thereby provides a quadratic improvement in the complexity of their gradient calculation step. We also show that in a continuous phase query model, our gradient calculation algorithm has optimal query complexity up to poly-logarithmic factors, for a particular class of smooth functions. One of the main technical challenges in applying our gradient calculation procedure for optimization algorithms is the necessity of interconversion between a probability oracle (which is common in quantum optimization procedures) and phase oracle (which is common in quantum query algorithms) of the objective function. We provide efficient subroutines to perform this delicate interconversion between the two type of oracles incurring only a logarithmic overhead, which might be of independent interest.

Read this article online: https://arxiv.org/abs/1711.00465

(Session 4 : Thursday from 4:15pm-4:45pm)