IQI Weekly Seminar

Abstract: In this talk we present an improved version of Jordan's quantum algorithm for gradient calculation. For a class of smooth functions we prove a rigorous approximation error bound of the calculated gradient, that is quadratically better compared to Jordan's original result in terms of the precision parameter. We further show that the query complexity of the new gradient calculation algorithm is optimal up to poly-logarithmic factors.

We provide a generic model of quantum optimization algorithms that is based on gradient descent, and a method for interconverting between probability and phase oracles. We use these tools to show that quantum computers can train quantum auto-encoders and apply variational quantum eigensolvers or QAOA using quadratically fewer queries than previously known.

The talk is based on joint work with Nathan Wiebe and Srinivasan Arunachalam.