Optimizing quantum optimization algorithms via faster quantum gradient computation

1 Introduction

• Quantum optimization has received less attention than other quantum algorithmic areas, while generic real-world optimization problems often fail the delicate requirements of non-Grover techniques.The introduction surveys applications including Monte Carlo, derivative-free, least-squares, annealing, adiabatic, satisfiability, travelling-salesman, and quantum approximate optimization methods.Source: §1 · p. 3
• The paper introduces a quantum gradient algorithm that achieves a quadratic reduction in query and gate complexity under reasonable continuity assumptions and is essentially optimal for a class of functions.It also improves protocols for quantum chemistry simulation and quantum neural-network training.Source: §1 · p. 3

1.1 Prior work on quantum gradient methods

• Jordan’s algorithm [Jor05] provides exponential speedups for black-box gradient computation, while later approaches represent vectors as quantum states to obtain dimension-dependent improvements for specific optimization algorithms.Rebentrost et al. [RSPL16] and Kerenidis and Prakash [KP17] achieve favorable dimension scaling in restricted settings, with limitations involving gradient-step dependence or strong data-access assumptions.Source: §1.1 · pp. 3–4

1.2 Classical gradient-based optimization algorithms

• Classical gradient descent repeatedly moves from x^(t) to x^(t+1) = x^(t) − δ∇p(x^(t)) and uses multiple random starts to seek a local minimum.The method relies on the fact that −∇p(x) is the direction of fastest decrease and is widely used for well-behaved objectives.Source: §1.2 · p. 4

1.3 Complexity measure and quantum sampling

• The complexity model represents the objective through a coherent probability oracle because quantum optimization procedures commonly estimate measurement probabilities by sampling.The central question is how many probability-oracle queries Up suffice to compute the gradient when x uses finite-precision binary encoding.Source: §1.3 · p. 4
• Quantum improvements use amplitude estimation for O(1/ε) function evaluation, quantum minimum finding, and gradient computation with quadratic improvement in dimension d, accelerating nearly all parameters except iteration count T.These results are summarized in Table 1.Source: §1.3 · p. 5, Table 1 · p. 5
• Classical acceleration methods may reduce the number of gradient steps T, but combining them with quantum sampling is difficult because they often require unbiased approximate-gradient samples.The proposed algorithm outputs a classical gradient description, unlike recent quantum gradient-descent methods [RSPL16] [KP17].Source: §1.3 · p. 5

1.4 Conversion between probability and phase oracles

• The authors simulate phase oracles from probability oracles, and probability oracles from phase oracles, to ε precision using O(log(1/ε)) queries under stated conditions.These conversions use Linear Combination of Unitaries techniques [BCC+15].Source: §1.4 · p. 5
• The oracle-conversion techniques let quantum optimization procedures interchangeably use probability or phase access, and are presented as potentially useful beyond this paper.The authors state they are unaware of prior results establishing this simulation.Source: §1.4 · p. 5

1.5 Improved gradient computation algorithm

• For an analytic probability function with bounded partial derivatives at zero, the new algorithm computes an ε-accurate coordinate-wise gradient with high probability using e O queries to the probability oracle.Similar complexity bounds hold with phase-oracle access.Source: §1.5 · p. 6
• The algorithm replaces Jordan’s single-evaluation approach [Jor05] with higher-degree central differences, requiring only ε-accurate function evaluations at log(1/ε) points.It applies one-dimensional formulas to slices of the multivariate function before a d-dimensional quantum Fourier transform.Source: §1.5 · p. 6
• The gradient method relies on smoothness to control directional derivatives of most one-dimensional slices, allowing low-precision evaluations to suffice for gradient estimation.After evaluating the function, it applies a d-dimensional quantum Fourier transform to produce a classical approximate gradient.Source: §1.5 · p. 6
• For degree-k multivariate polynomials on [−R,R]^d with R = Θ(1), the algorithm achieves query complexity e O(k log(d)/ε).This is the stated special-case bound from Theorem 23.Source: §1.5 · p. 6
• When k = O(log(d)), the polynomial-gradient algorithm gives an exponential speedup over Jordan’s algorithm [Jor05] in its dependence on dimension d.The comparison is specifically with respect to the dimension d.Source: §1.5 · p. 6

1.6 Smoothness of probability oracles

• For typical quantum optimization protocols, measurement probabilities of parametrized circuits are analytic and have all partial derivatives bounded in magnitude by 1.These properties satisfy the smoothness requirements used by the gradient computation algorithm.Source: §1.6 · p. 7

1.7 Lower bounds for gradient computation

• The lower-bound analysis addresses whether quantum gradient computation can improve over classical O(d/ε) complexity by more than a quadratic factor.Although low-degree multivariate polynomials admit exponential speedups, the paper shows that such speedups do not hold generally for smooth non-polynomial functions.Source: §1.7 · p. 7
• Ω(d/ε) queries are required by a generic quantum gradient computation algorithm for a family of smooth functions.This proves optimality of the paper’s gradient algorithm up to poly-logarithmic factors for that function class.Source: §1.7 · pp. 7–8
• The lower bound is established with a hybrid-method theorem for arbitrary phase oracles, overcoming the difficulty of applying standard discrete-query lower-bound techniques to continuous inputs.The method bounds the queries needed to distinguish a finite family of functions from a target function through controlled phase-oracle access.Source: §1.7 · p. 8
• The hard family contains f_j(x) = 2εx_je^(-∥x∥²/2), whose gradients at 0 identify the functions while their phase oracles require Ω(d/ε) distinguishing queries.The proof compares these functions with the constant-zero function.Source: §1.7 · p. 8
• Using probability-to-phase oracle conversion with eO(1) overhead, the phase-oracle lower bound becomes an eΩ(d/ε) lower bound for ε-accurate gradients with probability-oracle inputs.Thus the limitation applies to the probability-oracle model used by quantum optimization procedures.Source: §1.7 · p. 9
• The lower-bound result also supports near-optimality for ε-precise gradient computation in every p-norm, p ∈ [1,∞].The cited comparison uses conversion from p-norm accuracy to εd−1/p accuracy in the infinity norm.Source: §1.7 · p. 9

Applications

• For arithmetically evaluated functions, the cheap gradient principle4 means gradient computation typically costs about as much as function evaluation, so Jordan’s algorithm usually offers only a constant-factor speedup.Classical gradient computation is already efficient in this regime, leaving limited room for quantum speedups.Source: §1.8 · p. 9
• Sampling-based objective evaluation is the practically relevant application regime because Jordan’s algorithm can require prohibitive precision overheads, especially when VQE or QAOA target precision ∝1/d.Arithmetic evaluation typically has poly-logarithmic precision dependence, whereas sampling complexity is polynomial in reciprocal precision.Source: §1.8 · p. 9
• The lower bound rules out super-quadratic speedups for ε-accurate gradients of generic smooth functions in the sampling case, limiting the attainable improvement to quadratic.The qualification ignores polylogarithmic factors and concerns approximation in the ∥·∥∞ norm for functions satisfying Theorem 25’s requirements.Source: §1.8 · p. 9

Comparison method

• The optimized semi-classical comparison method uses quantum amplitude estimation for function values, then computes coordinates classically with a high-order central difference formula requiring O(log(1/ε)) evaluations.Each evaluation uses roughly ε-precision, matching the proof strategy described for Theorem 1.Source: §1.8 · p. 10

Applications

• Across VQE, QAOA, and quantum auto-encoding, the algorithm provides a quadratic speedup in the dimension d of each associated problem.The applications are introduced for VQE [PMS+14] [WHT15], QAOA [FGG14], and quantum auto-encoding [WKGK16] [ROAG17].Source: §1.9 · p. 10

VQE

• VQE varies an efficiently parameterizable ansatz, often a unitary coupled cluster expansion, to minimize an energy expectation mapped to a measurement probability.This mapping makes the VQE objective accessible to the quantum gradient methods.Source: §1.9 · p. 10

QAOA

• QAOA tunes parameters in a parametrized state family to minimize an objective such as a constraint-violation count, whose expectation value can be mapped to a measurement probability [FGG14].After normalization and standard techniques, QAOA has the same measurement-probability structure as VQE.Source: §1.9 · pp. 10–11

Quantum auto-encoding

• For quantum auto-encoders, the algorithm quadratically speeds training of low-dimensional representations of high-dimensional data [WKGK16] [ROAG17].The quantum auto-encoder is presented as an analogue of classical auto-encoding for data compression and related machine-learning tasks.Source: §1.9 · p. 11

• Sections 3–8 cover quantum optimization models and classical gradient descent, probability-to-phase oracle conversion, quantum gradient computation, query lower bounds, applications, and future directions.The main gradient algorithm appears in Section 5, with complexity established in Theorem 25; technical calculations are deferred to Appendix A.Source: §2 · p. 11
• The paper fixes notation for vectors, basis elements, translated sets, norms, matrices, index sets, polylogarithmic complexity, Hilbert spaces, and all-zero qubit states.It uses e_i for standard basis vectors, [d] for {1,2,...,d}, and ẽ O(C) to suppress poly-logarithmic factors.Source: §2 · p. 11
• Higher-order calculus is introduced through index-sequences, multi-index products, partial derivatives, analyticity, and directional derivatives for multivariate functions.For α ∈ [d]^k, |α| = k and ∂_α f denotes the corresponding k-fold partial derivative.Source: §2 · pp. 11–12
• Central-difference formulas approximate directional derivatives and gradients, while Appendix A derives generic degree-2m approximation-error bounds needed for asymptotic results.These formulas arise from polynomial interpolation and extend one-dimensional derivative approximations to high-dimensional gradients.Source: §2 · p. 12

3 A generic model of quantum optimization algorithms

• Quantum optimization circuits prepare an initial state, apply fixed and tunable gates, and verify the output, with quality measured by the probability of obtaining 1 on an auxiliary qubit.Parameters may be classical values or quantum variables encoded by qubits; quantumly tunable circuits enable quantum optimization techniques but require extra qubits and controlled gates.Source: §3 · p. 13

3.1 Classical gradient ascent algorithm

• Classical gradient ascent repeatedly evaluates the objective gradient, steps toward steepest ascent from fixed or random initial parameters, and reports the best result across random restarts.The method generally converges to a local maximum, while globally optimal solutions require multiple restarts.Source: §3.1 · p. 14

3.2 Quantum speedups to the classical algorithm

• Quantum amplitude estimation reduces estimating p(x) to error ε from Ω(1/ε^2) classical repetitions to O(1/ε) circuit uses.This improvement applies even to classically controlled circuits and requires few additional quantum resources.Source: §3.2 · p. 15
• Grover-based maximum finding reduces the number of random-start repetitions to O(√N) while retaining high-probability discovery of a point with p(xT) ≥ p̃, but may require substantial qubit overhead and uniform longest-path execution.The cited improvements are [Bul05a] [LPL14], while maximum-finding generalizations are [DH96, NW99, AGGW17].Source: §3.2 · p. 15
• The improved Jordan-based gradient computation gives a quadratic speedup in d, with much smaller qubit overhead than Grover-based maximum finding, and can combine with maximum finding while preserving essentially the classical guarantees.The resulting algorithm achieves quadratic speedups in all parameters except T, according to the supplied complexity summary.Source: §3.2 · p. 15

4.1 Oracle access to the objective function

• Probability oracles encode objective values as measurement probabilities, whereas binary and phase oracles provide finite-precision values or phases for quantum algorithmic use.Binary-oracle conversion from probability access costs O(1/ε) queries for log(1/ε) bits, motivating direct phase-oracle access.Source: §4 · p. 16, §4.1 · pp. 16–17
• The framework assumes discrete query points, supports fractional phase queries, and uses probability-oracle simulation to make fractional-query implementation nearly as easy as full queries.These oracle models apply to finite hypergrids for functions on R^d, with fractional phase access defined for query parameters r ∈ [−1,1].Source: §4.1 · pp. 16–17

4.2 Conversion between probability and phase oracles.

• Probability-to-phase conversion via LCU [BCK15] avoids analogue→digital→analogue conversion and incurs only logarithmic precision overhead.The construction uses the Grover operator’s invariant two-dimensional subspace and LCU techniques rather than first producing a binary oracle.Source: §4.2 · pp. 17–18
• Phase-to-probability conversion uses O(log(1/ε)/δ) controlled phase-oracle invocations when p(x) ∈ [δ,1−δ], establishing oracle equivalence with the previous conversion.The bounded-away-from-extremes condition is necessary because probability encodes squared amplitudes and can lose information near 0 or 1.Source: §4.2 · p. 21

4.3 Conversion between Phase oracle, Binary oracle and Fractional Phase oracle

• Phase oracles can implement binary-oracle phase rotations with constant binary-oracle calls, while binary-oracle simulation from phase access uses quantum phase estimation and exponential precision cost.For phase 2πSf within error δ, binary precision is set to η = Θ(δ/|S|); m-bit binary recovery uses approximately 2^m log(1/η) phase queries.Source: §4.3 · p. 22

5.1 Overview of Jordan’s algorithm

• Jordan’s algorithm estimates a d-dimensional gradient from one function evaluation on a superposition, using a phase oracle, inverse Fourier transforms, and measurement [Jor05, Bul05b].The method exploits local approximate linearity and requires only one sufficiently precise phase-oracle implementation.Source: §5.1 · pp. 22–23
• The improved phase-query analysis makes precision dependence essentially linear rather than quadratic in 1/ε, rigorously obtains square-root dimension scaling, and is optimal up to poly-logarithmic factors for a smooth-function class.These improvements address limitations of Jordan’s Binary oracle model and higher-order Taylor terms [Jor05].Source: §5.1 · pp. 23–24

5.2 Analysis of Jordan’s algorithm

• Jordan’s analyzed procedure prepares a fixed-point grid, applies a modified phase oracle, performs registerwise inverse Fourier transforms, and measures each register to estimate gradient coordinates.For an approximately affine function, the analysis bounds coordinatewise estimation error and amplifies success probability by repeating the procedure and taking coordinatewise medians.Source: §5.2 · pp. 25, 27

5.3 Improved quantum gradient algorithm using higher-degree methods

• The higher-degree method applies Jordan’s algorithm to central finite-difference approximations, cancelling even-order terms and reducing error proportionally to δ^(2m+1) when f is (2m+1)-times differentiable.For bounded higher derivatives with δ ≤ 1/c, the approximation error becomes exponentially small in m.Source: §5.3 · pp. 27–28
• For degree-k multivariate polynomials with k = O(log(d)), choosing m = ⌈k/2⌉ yields an exponential speedup in dimension d over Jordan’s algorithm.This choice makes B = 0 when R = Θ(1), producing the stated improved query complexity.Source: §5.3 · p. 28

5.4 Smoothness conditions and approximation error bounds

• For non-polynomial functions, higher-derivative bounds can scale as B ≈ d^m even under strong regularity, so additional smoothness conditions are needed to preserve favorable dimension scaling.The next subsection develops approximation-error bounds under such smoothness assumptions.Source: §5.3 · p. 28, §5.4 · p. 28
• The theorem applies to analytic functions satisfying derivative-growth conditions, with finite-domain boundaries potentially increasing complexity when evaluation points lie near the boundary.The stated result assumes evaluations throughout R^d, while applications naturally permit evaluations at distant points.Source: §5.4 · p. 29
• The algorithm achieves approximately 1/ε precision scaling together with dimension-dependent scaling, improving [Jor05] quantitatively and qualitatively.The result outputs an ε-approximate gradient using phase-oracle queries.Source: §5.4 · pp. 29–30
• A matching lower bound shows that this query complexity is optimal up to logarithmic factors for the analyzed smooth-function class.The lower bound is established in Section 6 and matches the upper bound up to log factors.Source: §5.4 · pp. 28, 30

5.5 Most quantum optimization problems are “smooth”

• For probability oracles generated by products of controlled rotations and fixed unitaries, every k-th derivative satisfies the bound |∂_αp(x)| ≤ 2^k.This establishes the smoothness condition required by the gradient-computation theorem for a broad quantum-optimization setting.Source: §5.5 · p. 30
• Because parameterized rotation unitaries are analytic, probabilities formed from their products with fixed matrices and vectors are analytic as well.The derivative bounds follow from operator-derivative bounds and product-composition lemmas.Source: §5.5 · pp. 30–31

6 Lower bounds on gradient computation

• The lower bound requires Ω(d/ε) queries for computing gradients of suitable smooth functions, matching Theorem 25 up to logarithmic factors and translating to probability oracles.Probability-oracle simulation uses only logarithmically many phase-oracle queries.Source: §6 · pp. 31–32

6.1 Hybrid method for arbitrary phase orcales

• The hybrid method lower-bounds distinguishing a phase oracle from a family of alternatives, even with controlled or inverse oracle queries.The method is related to adversary-style arguments and has also been applied to quantum SDP-solving [AG18].Source: §6.1 · pp. 32, 34, §6 · p. 32

6.2 A family of functions for proving the gradient computation lower bound

• The family’s members are uniquely identified by the gradient at 0 to accuracy ε, so estimating that gradient is at least as hard as distinguishing them from the constant 0 function, requiring Ω(d/ε) queries.Here ∇f0(0)=0 and ∇fj(0)=2εej, and the phase-oracle procedure identifies j with success probability at least 2/3.Source: §6.2 · pp. 34, 36

6.3 Lower bound for more regular functions

• The lower bound extends to a broad class of more regular analytic functions, showing the gradient algorithm is essentially optimal for many gradient-computation problems.The paper notes that typical objective functions satisfy stronger derivative bounds than the original lower-bound example, and Cornelissen proved the conjectured extension.Source: §6.3 · p. 36
• The regular-function argument relies on a grid symmetric around zero; shifting its midpoint increases typical phase magnitudes and weakens the intended lower-bound construction.A bounded analytic example with the required gradient and derivative control is f(x)=sin(cx_1+...+cx_d).Source: §6.3 · p. 36

7 Applications

• The gradient algorithm applies to VQE, QAOA, and quantum auto-encoder training, yielding a quadratic speedup in the dimension for each application.VQE and QAOA are treated essentially identically, while auto-encoders require a slightly different formalism.Source: §7 · p. 37

7.1 Variational quantum eigensolvers

• For VQE, a Hadamard-test verifier converts the energy expectation into a probability oracle, enabling gradient computation quadratically faster than earlier pre-fault-tolerant approaches.The verifier outputs 1 with probability 1/2 − ⟨ψ|H|ψ⟩/2, and phase-oracle simulation uses O(log(1/δ)) applications of the verifier.Source: Figure 3 · p. 38, §7.1 · pp. 39–40
• The same analysis applies to QAOA because its parametrized-state objective has the same Hermitian-operator structure as VQE, differing mainly in state parameterization [FGG14].For combinatorial optimization, the objective can count satisfied clauses represented as sums of tensor products of Pauli operators.Source: §7.1 · p. 40

7.2 Quantum auto-encoders

• Quantum auto-encoder training is formulated as maximizing the probability of recovering an input pure state after encoding and decoding.For n-qubit inputs mapped to k-qubit states, encoding and decoding channels can be represented by unitaries with ancillas, allowing the objective to fit the gradient-optimization framework.Source: §7.2 · p. 41, §7.2.1 · p. 41

7.2.1 Training quantum auto-encoders

• Auto-encoder optimization can use stochastic gradient descent on individual states or a uniform superposition over inputs, provided the parameterized circuits satisfy the required smoothness condition.The circuit objective is implemented as a probability, and structured polynomial-parameter circuits avoid the exponentially large parameterization of arbitrary unitaries.Source: §7.2.1 · p. 41, Figure 5 · p. 42

• The algorithm is asymptotically query-optimal up to logarithmic factors for estimating gradients of certain smooth functions in max-norm.Its construction uses differentiation formulas based on high-degree interpolatory polynomials.Source: §8 · p. 42
• High-degree methods quadratically improve query-complexity scaling with approximation quality over Jordan’s approach, while low-degree multivariate polynomials can yield exponential speedups over Jordan’s or classical algorithms.Lower bounds for certain smooth functions show near-optimality for the corresponding function class.Source: §8 · p. 43
• Applications across machine learning and quantum chemistry simulation obtain polynomial speedups by combining the improved gradient algorithm with phase–probability oracle interconversion.The authors identify finding applications with exponential speedups for low-degree multivariate polynomials as an open direction.Source: §8 · p. 43
• Future research includes generalizing lower bounds under stronger high-order derivative promises, accelerating stochastic gradient descent, and computing higher-order derivatives such as the Hessian.These advances could improve quantum analogues of Newton’s method and the scaling of epochs needed to reach a local optimum; the Hessian direction is related to Jordan’s algorithm [Jor08, Appendix D].Source: §8 · p. 43

A Error bounds on central difference formulas

• For low-degree polynomial functions, Theorem 23 can provide potentially exponential speedups in the dimension compared with Jordan’s algorithm.Under uniformly bounded higher derivatives, choosing m = log(d/ε) gives an improved precision dependence but fails to capture the desired dimension scaling.Source: A Error bounds on central difference… · pp. 48, 52
• Numerical experiments show that, for k = 2m, the relevant coefficient quantity is lower bounded by (m/e)2m, so the proven upper bound is qualitatively tight.This validates the coefficient estimates used in the central-difference analysis despite discarding cancellations.Source: A Error bounds on central difference… · p. 48
• Theorems 23 and 24 combine central-difference formulas with higher-dimensional calculus to bound quantum gradient-computation query complexity under bounded-derivative and analytic-function conditions.Theorem 23 assumes bounded higher derivatives and phase-oracle access, while Theorem 24 assumes analyticity and improves the dimension dependence.Source: A Error bounds on central difference… · pp. 48, 51, 54
• Theorem 23 yields an approximate gradient with infinity-norm error at most ε and succeeds with the probability specified by the theorem.Its smooth-function query bound scales as e O(d/ε), improving the dependence on ε while remaining worse in d than Jordan’s algorithm.Source: A Error bounds on central difference… · pp. 48, 51
• Theorem 24 considers an analytic function f: R^d → R and establishes its stated property for all but a 1/1000 fraction of points y.Source: A Error bounds on central difference… · pp. 54–55

Applications of the conversion

• The phase-to-probability conversion translates the lower-bound proof to the probability formalism with a log(1/ε) loss and supports generalized fractional queries.Fractional queries are implemented by converting to probability, reducing the probability with an ancilla qubit, and converting back to phase.Source: B Interconversion between phase and… · p. 55

Phase-to-probability conversion

• O(log(1/ε)/δ) controlled phase-oracle invocations implement a probability oracle when p(x) ∈ [δ,1−δ].The construction uses amplitude encoding, LCU techniques, and phase estimation for arbitrary δ.Source: B Interconversion between phase and… · pp. 55–57

Conversion guarantee

• Phase and probability oracles can be converted back and forth with logarithmic precision overhead when probabilities are bounded away from 0 and 1.The phase-to-probability construction relies on the approximation lemma from [AGGW17, Lemma 37].Source: B Interconversion between phase and… · pp. 55, 57

Limitation

• Conversions from probability to phase can lose information when p is close to 0 or 1 because probability encodes the squared amplitude.Amplitude-to-phase conversion can avoid this loss but requires handling potentially complex amplitudes; inner-product oracles provide an alternative via the Hadamard test.Source: B Interconversion between phase and… · p. 57

• The appendix introduces a generalized robust oblivious amplitude amplification procedure [BCC+15] with improved constants in the error bounds.Source: C Robust oblivious amplitude… · p. 58
• The robust amplification analysis applies Jordan’s theorem to decompose the space into one- and two-dimensional invariant subspaces, enabling the amplification guarantee for all states in Im(Π1).The proof analyzes the transformed projector WΠ1W† against Π2 and applies the two-dimensional lemma componentwise.Source: C Robust oblivious amplitude… · pp. 58–59
• The 2D subspace lemma shows that G = W(2Π1 − I)W†(2Π2 − I) preserves the relevant subspace and acts there as a rotation by angle 2θ.The lemma assumes W|ψ⟩ = sin(θ)|φ⟩ + cos(θ)|φ⊥⟩ and compatible orthogonal projectors Π1 and Π2.Source: C Robust oblivious amplitude… · p. 58