Source-linked AI summary
Quantum gradient descent and Newton's method for constrained polynomial optimization
Patrick Rebentrost, Maria Schuld, Leonard Wossnig, Francesco Petruccione, Seth Lloyd
TL;DR
Many optimization problems require iterative methods, while the quantum treatment of such optimization has been less developed for non-quadratic or non-convex objectives. This paper develops quantum gradient-descent and Newton algorithms for sparse polynomial optimization under a unit-norm constraint, using quantum access to gradient and Hessian operations. The resulting algorithms scale polylogarithmically with vector dimension when only a small number of iterations is needed, but exponentially with the iteration count.
Problem
General non-quadratic convex and non-convex optimization problems lack a universal single-shot solution, motivating quantum iterative methods beyond existing quadratic settings.
Method
The paper develops quantum gradient-descent and Newton algorithms for sparse polynomial optimization under spherical constraints, operationalizing gradient and Hessian information from coefficient oracles.
Results
The algorithms achieve O(polylog(N)) dependence on vector dimension N when the required number of iterations is small.
Takeaways & Limitations
The approach can be useful for high-dimensional optimization when a small number of iterations yields a significant improvement over the initial guess.
Takeaways & Limitations
Resource requirements grow exponentially with the number of iterations, limiting the approach for optimizations that require many steps.
Abstract
from arXiv · showhide
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 principal component analysis 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 beneficial for high-dimensional problems where a small number of iterations is sufficient.
1. Introduction
Optimization often requires iterative search, especially for non-quadratic convex or non-convex objectives where no general single-shot solution is known. This work develops quantum gradient-descent and Newton methods for such settings, targeting polynomial optimization under normalization constraints.
- Motivation: Non-quadratic convex and non-convex objectives generally require iterative search because no single-shot solution is known in general.For strictly convex functions on convex sets, a unique global minimum exists, but broader objective classes can have multiple minima.
- Classical methods: Gradient descent finds local minima by repeatedly moving along the negative gradient, but unfavorable landscapes can require many steps.Long, narrow valleys are given as an example of a problematic landscape.
- Classical methods: Newton’s method incorporates second-derivative curvature information to correct gradient step sizes and often improve convergence.The method is motivated as a second-order alternative to first-derivative-only updates.
- Quantum approach: The paper provides quantum versions of gradient descent and Newton’s methods that use copies of a current state plus its gradient and Hessian to prepare an improved state.The next candidate is produced from multiple copies of the current quantum state at each iteration.
- Quantum approach: The algorithms target polynomial optimization with normalization constraints and make gradients and Hessians operationally available using quantum techniques and coefficient-access oracles.The detailed class includes sparse homogeneous even-order polynomials and sketches extensions with inhomogeneous terms.
- Scope: The algorithms scale exponentially with the number of steps, making them unsuitable for many-iteration problems but potentially acceptable when only a few steps suffice.This trade-off is especially relevant to Newton’s method or local search, where fewer iterations may be needed.
2. Problem statement
The paper formulates gradient and Newton updates for sparse, even-order homogeneous polynomials under a unit-sphere constraint. It also motivates inhomogeneous extensions because constrained Newton directions can be perpendicular to the feasible sphere and fail to update the candidate.
- Iterative methods: Gradient descent updates an initial point using local steepest-descent information, while Newton’s method additionally uses curvature through the Hessian.The Hessian entries are second derivatives evaluated at the current point.
- Iterative methods: Figure 1 compares ordinary and projected updates, with projected methods renormalizing each candidate to remain on the unit sphere.The feasible solution is the minimum found on the constrained set.
- Polynomial class: The objective class consists of sparse homogeneous polynomials of even order 2p over N-dimensional vectors, with a small number of nonzero coefficients.The polynomial is represented using tensor products and a higher-dimensional matrix form.
- Polynomial class: For p = 1, the polynomial reduces to the quadratic form f(x) = x^T A x, while p = 2 maps a two-dimensional input to a four-dimensional tensor-product representation.The matrix A in the p = 2, N = 2 example has size 4 × 4.
- Quantum operators: The gradient and Hessian are represented as operators whose action on the current vector supplies the update information needed by the quantum algorithms.The norm bounds scale as Λ_D = O(pΛ_A) and Λ_H = O(p^2Λ_A).
- Spherical constraint: For homogeneous quadratic forms, projected Newton directions can be perpendicular to the unit sphere, causing Newton’s method not to update the initial guess.The paper therefore considers adding a linear inhomogeneity c^T x to broaden the class of optimizable functions.
- Spherical constraint: Quantum state normalization naturally imposes x^T x = 1, so the optimization problem seeks a local minimum on the unit sphere.The paper notes applications of spherical constraints in image and signal processing, biomedical engineering, speech recognition, and quantum mechanics.
- Assumptions: The analysis assumes a sufficiently close initial guess, a positive-semidefinite Hessian near the solution, and smoothness conditions supporting monotonic convergence.These assumptions are stated to guarantee saddle-point-free optimization and convergence to the minimum.
3. Quantum gradient descent algorithm
The quantum gradient-descent routine represents normalized candidate vectors as quantum states and uses gradient-operator simulation, phase estimation, and conditioned matrix multiplication to produce improved states. Its resources scale polylogarithmically with dimension but exponentially with iteration count, making few-step or local searches the supported regime.
- 3.1. Data input model: Candidate vectors are amplitude-encoded as n-qubit states with normalization constraint x^T x = 1, assuming N = 2^n after padding when necessary.The initial state can be supplied through a preparation oracle, with polynomial coefficients accessed through a separate oracle.
- 3.2. Computing the gradient: The gradient operator is simulated as a quantum Hamiltonian using copies of the encoded state and oracle access to the polynomial coefficient matrix.The construction uses density-matrix-based techniques and matrix-exponential simulation.
- 3.2. Computing the gradient: With i.i.d. imperfect states, the gradient operator can be applied to prepare a state proportional to D|x⟩ with accuracy O(ε_D), using resources determined by κ_D and ε_D.The required simulation time is set proportional to κ_D/ε_D, and the resulting matrix multiplication has accuracy ε_D.
- 3.3. Single gradient descent step: A single gradient step prepares an improved normalized state for step size 0 < η(t) < 1/(2Λ_D), with polynomial resource dependence and success probability at least 1/16.The updated-state error includes the previous-step error and the conditioned matrix-multiplication error.
- 3.4. Multiple steps: Multiple gradient steps require a number of initial-state copies that grows exponentially with the number of steps, restricting the method to settings where few iterations suffice.The paper identifies faster-converging Newton iterations and local searches as possible settings where this limitation is more acceptable.
4. Quantum Newton’s method
The quantum Newton method prepares improved normalized candidates by applying the gradient and inverse Hessian to the current quantum state. Its per-step resources are logarithmic in dimension but repeated steps require exponentially many copies, making few-step regimes most suitable.
- Quantum Newton update: A Newton step combines gradient-state preparation with inversion of the Hessian on its well-conditioned subspace.The update uses the direction H^-1D|x⟩, with zero or extremely small Hessian eigenvalues excluded.
- Single-step guarantee: A single Newton step prepares an improved normalized state with accuracy O(ηϵ_nwt + ϵ(t)) and success probability at least 1/16.The step-size condition is η(t) < 1/(2 max{ΛD, ΛH−1, ΛDΛH−1}).
- Quantum Newton update: The algorithm uses phase estimation, conditional rotations, postselection, and reverse phase estimation to implement gradient multiplication and Hessian inversion.The gradient and Hessian operators are simulated through assumed quantum simulation methods.
- Resource requirements: The required oracle queries and elementary operations for one step scale polynomially in p, sA, Λ, and 1/ϵ_nwt, with elementary operations carrying a log N factor.The gradient and Hessian requirements are combined using Λ = max{ΛD, ΛH}.
- Iteration trade-off: The number of initial-state copies grows exponentially with iterations T, while Newton accuracy can improve quadratically near an optimum under stated regularity conditions.This trade-off favors applications requiring few iterations or local search.
5. Inhomogeneous polynomials
The framework extends to selected inhomogeneous polynomial objectives under the same unit-norm constraint. These extensions add simulation, vector-addition, and resource costs, with efficient optimization restricted by sparsity.
- Problem class: Odd-order and inhomogeneous polynomial extensions are included, although detailed treatment of some examples is left for future work.The paper provides a similar procedure for a subset of inhomogeneous polynomials.
- Problem class: The extension represents selected inhomogeneous polynomials as a homogeneous even component plus terms of uneven degree up to 2p − 1.The problem seeks a local minimum subject to x^Tx = 1.
- Extension limits: Efficient sparse Hamiltonian simulation restricts the number of inhomogeneous terms, with sparse B_ij matrices implying relatively few inhomogeneous monomials.The restriction follows from the simulation requirements rather than from the polynomial representation alone.
- Extension procedure: Inhomogeneous updates require analytical gradients and Hessians, quantum simulation of their evolution, additional vector additions, and conditional matrix operations.Inner- and outer-product terms involving the vectors c_j require additional simulation subroutines.
- Extension limits: The inhomogeneous extension adds computational overhead, while total computational steps remain exponential in iterations T and logarithmic in solution-vector dimension.The overhead arises from additional matrix multiplications and vector additions.
6. Discussion and conclusion
The work develops quantum iterative optimization for polynomial problems and identifies when its dimension scaling can be advantageous, while emphasizing exponential dependence on iteration count and limits in featureless landscapes.
- Contributions: The algorithms optimize polynomials under spherical constraints using quantum gradient and Hessian operations, extending quantum optimization beyond quadratic objectives.The authors also discuss possible extensions beyond polynomial objectives using quantum states representing current solutions.
- Complexity: The algorithms scale exponentially in the number of optimization steps, limiting their usefulness when many iterations are required.The paper relates this dependence to the hardness of the optimization problem.
- Potential applications: The approach may be useful for high-dimensional problems where a constant number of steps substantially improves an initial guess, and for locally convex problems solved with Newton’s method.The Newton-method scenario is supported when iteration counts depend only weakly on system dimension.
- Complexity: O(polylog(N)) performance is obtained in the vector-space dimension N when the required number of iterations is small.This scaling is stated for the optimization algorithms summarized in the conclusion.
- Limitations: For featureless landscapes with few solutions, many iterations are required and the algorithms scale polynomially in N, without outperforming Grover search.Grover search finds M solutions in time O(sqrt(N/M)) in the described gradient-free setting.
Appendix A. Simulating the gradient matrix MD and the Hessian part MH1
Appendix A gives Hamiltonian-simulation constructions for the gradient and Hessian operators by reducing them to sparse-matrix simulations, with polylogarithmic dependence on N in the gate counts.
- Gradient simulation: The derivative auxiliary operator MD can be simulated with O(p^3Λ_As_Aτ^2/ϵ) oracle queries and ˜O(p^4Λ_As_Aτ^2 log N/ϵ) quantum gates.The construction uses the sparse-matrix oracle access assumed for A.
- Gradient simulation: MD is decomposed into terms related to A through permutation matrices, allowing each term to be simulated with sparse Hamiltonian simulation.The permutation operations require log N swap operations per register exchange.
- Scope: Improved simulation methods may reduce the stated dependencies because simulating MD only serves to implement the gradient operator D.The appendix explicitly leaves open more efficient ways to compute the relevant sparsity function.
- Hessian simulation: The Hessian auxiliary operator MH1 can be simulated with O(p^6Λ_As_Aτ^2/ϵ) oracle queries and ˜O(p^6Λ_As_Aτ^2 log N/ϵ) quantum gates.Its construction uses p^2 small-time simulations of A and permutation operations.
- Hessian simulation: For MH1, the total simulation procedure uses O(mp^2Λ_As_A) oracle queries and ˜O(mΛ_As_Ap^2 log N) quantum gates over m time steps.The gate bound is stated for Λ_A ≥ 1.
Appendix B. Sample-based Hamiltonian simulation with erroneous Hamiltonian
Appendix B analyzes errors from sample-based Hamiltonian simulation when the quantum states used to represent the current solution are imperfect, under small random-error assumptions.
- Error model: The analysis assumes independent, bounded, random sample errors whose norms are much smaller than one.The erroneous samples are written as the intended state plus an error vector.
- Gradient Hamiltonian: Sample errors enter the simulated gradient Hamiltonian through O(p) erroneous contributions, with random symmetric error variables of standard deviation O(β).The analysis uses a central-limit argument to bound their aggregate effect.
- Gradient Hamiltonian: The gradient simulation error combines matrix-simulation and sampling contributions, with the matrix-simulation term chosen as ∥E_MD∥ = O(p^2∆t^2).The corresponding implementation uses O(pΛ_As_A) oracle queries and ˜O(p^2Λ_As_A log N) gates per small step.
- Error scaling: Sample-based simulation generally has quadratically worse time-error dependence than black-box Hamiltonian simulation, scaling as O(τ/ϵ) for the latter.The comparison is made for erroneous Hamiltonians.
- Hessian Hamiltonian: The Hessian analysis has O(p^2) error contributions rather than O(p), leading to higher p-dependent complexity bounds.The appendix notes that the displayed p^8 and p^10 dependencies may be significantly improved.