Optimizing quantum optimization algorithms via faster quantum gradient computation

DOI10.1137/1.9781611975482.87MaRDI QIDQ5236271zbMATHOpenAlexFDO

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)

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

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)

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).

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

Cited in

(8)

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

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)