Abstract Optimization problems in disciplines such as machine learning are commonly solved with iterative methods. Gradient descent algorithms find local minima by moving along the direction of steepest descent while Newton’s method takes into account curvature information and thereby often improves convergence. Here, we develop quantum versions of these iterative optimization algorithms and apply them to polynomial optimization with a unit norm constraint. In each step, multiple copies of the current candidate are used to improve the candidate using quantum phase estimation, an adapted quantum state exponentiation scheme, as well as quantum matrix multiplications and inversions. The required operations perform polylogarithmically in the dimension of the solution vector and exponentially in the number of iterations. Therefore, the quantum algorithm can be useful for high-dimensional problems where a small number of iterations is sufficient.
Abstract Optimization problems in disciplines such as machine learning are commonly solved with iterative methods. Gradient descent algorithms find local minima by moving along the direction of steepest descent while Newton’s method takes into account curvature information and thereby often improves convergence. Here, we develop quantum versions of these iterative optimization algorithms and apply them to polynomial optimization with a unit norm constraint. In each step, multiple copies of the current candidate are used to improve the candidate using quantum phase estimation, an adapted quantum state exponentiation scheme, as well as quantum matrix multiplications and inversions. The required operations perform polylogarithmically in the dimension of the solution vector and exponentially in the number of iterations. Therefore, the quantum algorithm can be useful for high-dimensional problems where a small number of iterations is sufficient.
Optimization problems in disciplines such as machine learning are commonly solved with iterative methods. Gradient descent algorithms find local minima by moving along the direction of steepest descent while Newton's method takes into account curvature information and thereby often improves convergence. Here, we develop quantum versions of these iterative optimization algorithms and apply them to polynomial optimization with a unit norm constraint. In each step, multiple copies of the current candidate are used to improve the candidate using quantum phase estimation, an adapted quantum state exponentiation scheme, as well as quantum matrix multiplications and inversions. The required operations perform polylogarithmically in the dimension of the solution vector and exponentially in the number of iterations. Therefore, the quantum algorithm can be useful for high-dimensional problems where a small number of iterations is sufficient.
Abstract The gradient descent method is central to numerical optimization and is the key ingredient in many machine learning algorithms. It promises to find a local minimum of a function by iteratively moving along the direction of the steepest descent. Since for high-dimensional problems the required computational resources can be prohibitive, it is desirable to investigate quantum versions of the gradient descent, such as the recently proposed (Rebentrost et al. 1 ). Here, we develop this protocol and implement it on a quantum processor with limited resources. A prototypical experiment is shown with a four-qubit nuclear magnetic resonance quantum processor, which demonstrates the iterative optimization process. Experimentally, the final point converged to the local minimum with a fidelity >94%, quantified via full-state tomography. Moreover, our method can be employed to a multidimensional scaling problem, showing the potential to outperform its classical counterparts. Considering the ongoing efforts in quantum information and data science, our work may provide a faster approach to solving high-dimensional optimization problems and a subroutine for future practical quantum computers.
Gradient-based algorithms provide the fundamental tools for the optimizations and are the essential components of many modern technologies. Theoretically, the extreme points of a cost function can be found by iterative descent(ascent) of the variable along the direction of the gradient. However, the time complexity to calculate a gradient is at a level of O(poly(d)) for the d-dimension problems. For processing the high-dimension case, especially modern machine-learning engineering with the number of optimized parameters being in billions, quantum techniques are introduced. Via the dressed amplitude encoding and nonunitary module, a gradient-based quantum optimization algorithm for general polynomials is proposed, aiming at solving the fast-convergence problems with both time and memory complexity in O(poly(logd)). Furthermore, numerical simulations are carried out to inspect the performance of the newly born protocol by considering the noises or perturbations during the initialization, operations, and truncations. For the potential values in high-dimension optimizations, this gradient-based quantum optimization algorithm is supposed to facilitate the polynomial optimizations, being a subroutine for future practical quantum computers.
The gradient descent method aims at finding local minima of a given multivariate function by moving along the direction of its gradient, and hence, the algorithm typically involves computing all partial derivatives of a given function, before updating the solution iteratively. In the work of Rebentrost et al. [New Journal of Physics, 21(7):073023, 2019], the authors translated the iterative optimization algorithm into a quantum setting, with some assumptions regarding certain structure of the given function, with oracle or black-box access to some matrix that specifies the structure. Here, we develop an alternative quantum framework for the gradient descent problem, based on the seminal quantum singular value transformation framework. We show that given only classical information of function of interest, it is possible to construct a quantum gradient descent algorithm with a running time logarithmical in the number of variables. In particular, our framework consumes exponentially less qubits than the prior quantum gradient descent algorithm and removes the need for any coherent oracle access to classical information. Thus, our work provides another example demonstrating the power of quantum singular value transformation framework, and in particular, it adds another instance revealing that quantum coherent access is not necessary for quantum computational advantage.
Gradient Descent is an optimization algorithm used for finding the minima of a function. It moves along the function with steps proportional to the negative of the gradient. Quantum version of this algorithm has the advantage of exponential speedup for problems with high dimensional inputs. On the other hand, Factorization Machines (FMs) are modeling classes with important advantages in comparison with other modeling ones such as SVMs. They, in contrast to SVMs, use factorized parameters in order to model all interactions between variables. Accordingly, unlike SVMs, they can estimate interactions in problems with large sparsity. In this work, we show that Factorization Machine can be implemented on quantum computers, using quantum gradient descent to learn the parameters of a FM. The parameters we have chosen to learn via quantum gradient descent is a bottleneck in learning parameters of a FM. Our proposed idea results in time computational complexity O(k polylog n) where k and n are the dimensions of the parameter matrix. By doing so and under some constraints on the dimensions, an exponential speedup over classical algorithms can be obtained.
Solving systems of linear equations is one of the most important primitives in quantum computing that has the potential to provide a practical quantum advantage in many different areas, including in optimization, simulation, and machine learning. In this work, we revisit quantum linear system solvers from the perspective of convex optimization, and in particular gradient descent-type algorithms. This leads to a considerable constant-factor improvement in the runtime (or, conversely, a several orders of magnitude smaller error with the same runtime/circuit depth). More precisely, we first show how the asymptotically optimal quantum linear system solver of Childs, Kothari, and Somma is related to the gradient descent algorithm on the convex function ∥Ax−b∥22: their linear system solver is based on a truncation in the Chebyshev basis of the degree-(t−1) polynomial (in A) that maps the initial solution x1:=b to the t-th iterate xt in the basic gradient descent algorithm. Then, instead of starting from the basic gradient descent algorithm, we use the optimal Chebyshev iteration method (which can be viewed as an accelerated gradient descent algorithm) and show that this leads to considerable improvements in the quantum solver.