Optimizing quantum optimization algorithms via faster quantum gradient computation

DOI10.1137/1.9781611975482.87zbMATH Open1431.68038arXiv1711.00465OpenAlexW2766294686MaRDI QIDQ5236271FDOQ5236271

Authors: Srinivasan Arunachalam, Nathan Wiebe 

Publication date: 15 October 2019

Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: We consider a generic framework of optimization algorithms based on gradient descent. We develop a quantum algorithm that computes the gradient of a multi-variate real-valued function $f:mathbb{R}^{d}ightarrowmathbbR$ by evaluating it at only a logarithmic number of points in superposition. Our algorithm is an improved version of Stephen Jordan's gradient computation algorithm, providing an approximation of the gradient $ablaf$ with quadratically better dependence on the evaluation accuracy of $f$, for an important class of smooth functions. Furthermore, we show that most objective functions arising from quantum optimization procedures satisfy the necessary smoothness conditions, hence our algorithm provides a quadratic improvement in the complexity of computing their gradient. We also show that in a continuous phase-query model, our gradient computation algorithm has optimal query complexity up to poly-logarithmic factors, for a particular class of smooth functions. Moreover, we show that for low-degree multivariate polynomials our algorithm can provide exponential speedups compared to Jordan's algorithm in terms of the dimension $d$. One of the technical challenges in applying our gradient computation procedure for quantum optimization problems is the need to convert between a probability oracle (which is common in quantum optimization procedures) and a phase oracle (which is common in quantum algorithms) of the objective function $f$. We provide efficient subroutines to perform this delicate interconversion between the two types of oracles incurring only a logarithmic overhead, which might be of independent interest. Finally, using these tools we improve the runtime of prior approaches for training quantum auto-encoders, variational quantum eigensolvers (VQE), and quantum approximate optimization algorithms (QAOA).

Full work available at URL: https://arxiv.org/abs/1711.00465

Recommendations

• The theory of variational hybrid quantum-classical algorithms
• A comparison of various classical optimizers for a variational quantum linear solver
• On barren plateaus and cost function locality in variational quantum algorithms
• Combinatorial optimization through variational quantum power method
• Fast-QTrain: an algorithm for fast training of variational classifiers

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Nonconvex programming, global optimization (90C26) Quantum algorithms and complexity in the theory of computing (68Q12)

Cited In (8)

• The Python's lunch: geometric obstructions to decoding Hawking radiation
• Quantum classification algorithm with multi-class parallel training
• Modular quantum computing and quantum-like devices
• Title not available (Why is that?)
• Extracting a function encoded in amplitudes of a quantum state by tensor network and orthogonal function expansion
• Title not available (Why is that?)
• Benchmarking the quantum approximate optimization algorithm
• Quantum algorithms for numerical differentiation of expected values with respect to parameters

This page was built for publication: Optimizing quantum optimization algorithms via faster quantum gradient computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236271)