Multidimensional stochastic optimization plays an important role in analysis and control of many technical systems. To solve the challenging problems of multidimensional optimization, it was suggested to use the randomized algorithms of stochastic approximation with perturbed input which have simple forms and provide consistent estimates of the unknown parameters for observations under “almost arbitrary” noise. They are easily “incorporated” in the design of quantum devices to estimate gradient vector of a multi-variable function.
Multidimensional stochastic optimization plays an important role in analysis and control of many technical systems. To solve the challenging problems of multidimensional optimization, it was suggested to use the randomized algorithms of stochastic approximation with perturbed input which have simple forms and provide consistent estimates of the unknown parameters for observations under “almost arbitrary” noise. They are easily “incorporated” in the design of quantum devices to estimate gradient vector of a multi-variable function.
Variational quantum algorithms rely on the optimization of parameterized quantum circuits in noisy settings. The commonly used back-propagation procedure in classical machine learning is not directly applicable in this setting due to the collapse of quantum states after measurements. Thus, gradient estimations constitute a significant overhead in a gradient-based optimization of such quantum circuits. This paper introduces a random coordinate descent algorithm as a practical and easy-to-implement alternative to the full gradient descent algorithm. This algorithm only requires one partial derivative at each iteration. Motivated by the behavior of measurement noise in the practical optimization of parameterized quantum circuits, this paper presents an optimization problem setting that is amenable to analysis. Under this setting, the random coordinate descent algorithm exhibits the same level of stochastic stability as the full gradient approach, making it as resilient to noise. The complexity of the random coordinate descent method is generally no worse than that of the gradient descent and can be much better for various quantum optimization problems with anisotropic Lipschitz constants. Theoretical analysis and extensive numerical experiments validate our findings. Published by the American Physical Society 2024
Hybrid quantum-classical optimization algorithms represent one of the most promising application for near-term quantum computers. In these algorithms the goal is to optimize an observable quantity with respect to some classical parameters, using feedback from measurements performed on the quantum device. Here we study the problem of estimating the gradient of the function to be optimized directly from quantum measurements, generalizing and simplifying some approaches present in the literature, such as the so-called parameter-shift rule. We derive a mathematically exact formula that provides a stochastic algorithm for estimating the gradient of any multi-qubit parametric quantum evolution, without the introduction of ancillary qubits or the use of Hamiltonian simulation techniques. The gradient measurement is possible when the underlying device can realize all Pauli rotations in the expansion of the Hamiltonian whose coefficients depend on the parameter. Our algorithm continues to work, although with some approximations, even when all the available quantum gates are noisy, for instance due to the coupling between the quantum device and an unknown environment.
Hybrid classical quantum optimization methods have become an important tool for efficiently solving problems in the current generation of noisy intermediate-scale quantum computers. These methods use an optimization algorithm executed in a classical computer, fed with values of the objective function obtained in a quantum processor. A proper choice of optimization algorithm is essential to achieve good performance. Here, we review the use of first-order, second-order, and quantum natural gradient stochastic optimization methods, which are defined in the field of real numbers, and propose stochastic algorithms defined in the field of complex numbers. The performance of all methods is evaluated by means of their application to variational quantum eigensolver, quantum control of quantum states, and quantum state estimation. In general, complex number optimization algorithms perform best, with first-order complex algorithms consistently achieving the best performance, closely followed by complex quantum natural algorithms, which do not require expensive hyperparameter calibration. In particular, the scalar formulation of the complex quantum natural algorithm allows to achieve good performance with low classical computational cost.
We study stochastic optimization with heavy-tailed gradient noise. We first propose a novel quantum mean estimator for multivariate heavy-tailed random variables that achieves lower query complexity than optimal classical estimators in the low-dimensional regime. We further develop an unbiased quantum mean estimator by applying a generalized multi-level Monte Carlo technique. We prove quantum lower bounds showing that, when the dimension d of the random vector is small and can be viewed as a constant, our quantum estimators are optimal up to logarithmic factors. We further derive stronger dimension-dependent lower bounds for tail index p>4/3, showing that a nontrivial dependence on the dimension is unavoidable in the low-dimensional regime. Based on these estimators, we propose a quantum normalized stochastic gradient descent method (QNSGD), which finds an ε-stationary point using O~(dε−2p−25p−4) queries to the quantum stochastic gradient oracle. For a convex objective function, we propose a quantum projected stochastic gradient descent method (QPSGD), which computes a solution with ε-optimal solution using O~(dε−2p−23p−2+ε−2) queries in expectation. These sharper bounds improve upon the classical lower bounds Ω(ε−p−13p−2) for nonconvex problems and Ω(ε−p−1p) for convex problems in the low-dimensional regimes d≲ε−p−1p and d≲ε−p−12−p, respectively.