Fast Zeroth-Order Convex Optimization with Quantum Gradient Methods
Authors: Junhyung Lyle Kim
Brandon Augustino
Dylan Herman
Enrico Fontana
Jacob Watkins
Marco Pistoia
Shouvanik Chakrabarti
Venue: NeurIPS 2025 poster ()
Keywords: quantum computing
convex optimization
quantum gradient methods
semidefinite programming
linear programming
zero-sum games
Primary area: optimization

Abstract: We study quantum algorithms based on quantum (sub)gradient estimation using noisy function evaluation oracles, and demonstrate the first dimension-independent query complexities (up to poly-logarithmic factors) for zeroth-order convex optimization in both smooth and nonsmooth settings. Interestingly, only using noisy function evaluation oracles, we match the first-order query complexities of classical gradient descent, thereby exhibiting exponential separation between quantum and classical zeroth-order optimization. We then generalize these algorithms to work in non-Euclidean settings by using quantum (sub)gradient estimation to instantiate mirror descent and its variants, including dual averaging and mirror prox. By leveraging a connection between semidefinite programming and eigenvalue optimization, we use our quantum mirror descent method to give a new quantum algorithm for solving semidefinite programs, linear programs, and zero-sum games. We identify a parameter regime in which our zero-sum games algorithm is faster than any existing classical or quantum approach.

Fast Zeroth-Order Convex Optimization with Quantum Gradient Methods
Junhyung Lyle Kim
Brandon Augustino'
Dylan Herman"
Enrico Fontana"
Jacob Watkins
Marco Pistoia
Shouvanik Chakrabarti
Global Technology Applied Research, JPMorganChase New York, NY 10001 USA
Abstract
We study quantum algorithms based on quantum (sub)gradient estimation using noisy function evaluation oracles, and demonstrate the first dimension-independee query complexities (up to poly-logarithmic factors) for zeroth-order convex opti- mization both smooth and nonsmooth settings. Interestingly, only using noisy function evaluation oracles, we match the first-order query complexities of classical gradient descent, thereby exhibiting exponential separation between quantum and classical zeroth-order optimization. We then generalize these algorithms to work in non-Eucie -un-uuclidean settings by using quantum (sub)gradient estimation to instan- tiate mirror descent and its variants, including dual averaging and mirror prox. By leveraging a connection between semidefinite programming and eigenvalue optimization, we use our quantum mirror descent method to give new quantum algorithm for solving semidefinite programs, linear programs, and zero-sum games. We identify parameter regime in which our zero-sum games algorithm is faster than any existing classical or quantum approach.
Introduction
Convex optimization has long been a central topic of study in computer science, mathematics, operations research, statistics, and engineering due to its large number of scientific and industrial applications. These problems are at the core of many machine learning pipelines, and generalize well studied settings such as linear programming, second-order conic programming, and semidefinite programming, to name a few. convex optimization problem is of the form
Find f E X such that f(ā) min f(x) S,
(OPT)
xEX
where A' C Rdd a closed convex set with nonempty interior, f Rd + R is convex and G-Lipschitz is an parameter. We make the standard
on X' with respect to given norm ||, and assumption that (OPT) is solvable, i.c., there exists an optimal point x'' E arg mingex f()), and that there exists R such that supzex dist(2;, x+) R for suitable distance metric distt-.-)..
In practical applications, problems of the form (PPT) are solved in very high dimension d, to very high precision both. Developing algorithms with better scaling in d and 1/s is primary goal of optimization theory. Due to the ubiquity and practical importance of convex optimization, there has been a significant effort to develop quantum algorithms providing speedups for these problems.
'These authors contributed equally.
shouvanik. chakrabartti@jjmchase...
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Research on convex optimization focuses on two different settings. In the black-box setting, the constraints defining the feasible region and the objective function are accessed via black-box oracles. The focus then is on developing algorithms that repeatedly query these oracles, with the aim of minimizing the number of queries necessary solve the problem, which called the query complexity. In the white-box setting, the objective function and constraints are known explicitly in some form, and the focus is on minimizing the time required to perform the optimization. As an example, linear programs are specified by the vector defining the (linear) objective function, while the constraints are specified by a matrix and right- heht- vector. Aside from linear programs, white-box convex optimization generalizes common settings such quadratic, second-order conic, and semidefinite programming. Black-box optimization algorithms can be directly applied to white-box optimization, but it is often possible to obtain more efficient methods by leveraging the specific problem structure, which has led to the development of many classical algorithms that are tailored to particular settings.
In this paper, we present improved algorithms for convex optimization in both the black- box and white-box settings. We begin with an investigation black-box optimization via (sub)gradien) methods, and show that quantum algorithms with access to only the noisy func- tion value can match the query complexity of classical (sub) gradditt methods that require the (sub)gradient of the objective function. Since the classical computation of a gradient in the oracle setting requires number of queries that linear in the dimensionality d, this represents an exponential speedup terms of d.
Varimnc-reduved
Carmon el al. [1]
(this week)
1/e
Quantum MWU
Bonland et ak 1
Gao al. 30
Notably, our results in the black-box setting ap- ply for optimization in both Euclidean and more general normedd spaces (p 2 1). This allows us to derive algorithms that offer improvements for white-bos box optimization. To this end, we leverage connection between semidefinite pro- gramming and eigenvalue optimization that has been previously studied to motivate the spec- tral bundle method. Specifically, semidefinite programming reduced to nonsmooth opti- mization problem that is Lipschitz continuous in f-ssacc.. Leveraging our black-box results for
Oig 19)
M
Figure 1: Regimes for speedup in solving zero- sum games in the (m, 1/laee See also Corol- lary 3.1 Algorithmss: Mirror Descent (MD), Ma- trix Multiplicative Weights (MWU).
this setting, we obtain algorithms for semidefinite programming, linear programming. and zero-sum games that improve upon the previously best known quantum and classical algorithms in some regimes; see Figure for an illustration.
In short, we demonstrate several algorithmic speedups using quantum (sub)gradient methods in both the black-box and white-box settings. Specifically, contributions be summarized as follows:
In Section 2 we show that, using only a noisy function evaluation oracle (Definition D. the zeroth-order quantum projected subgradient method (E2-space) and quantum mirror descent (C,-- space) match the first-order query complexities (up to polylogarithmic factors in d) achieved by their respective classical counterparts for solving (OPT). See, Theorem 2.1 We thus exhibit an exponential separation between quantum and classical zeroth-order optimization of convex and Lipschitz functions. These results are summarized in Table
In Section 3 we leverage the connection between semidefinite programming and eigenvalue optimization, and demonstrate how the quantum mirror descent framework can be applied to solving white-box settings, including semidefinite programming (Theorem 3.1). linear programming (Theorem 3.2) and zero-sum games (Corollary 3.1). In some regimes, we attain a better complexity (Table and Figure I than the current
approaches (both quantum and classical).
Section we characterize the effort required by zeroth-order quantum gradient methods to solve (PPT) when the objective function has Lipschitz continuous gradients, often referred to as the L-smooth setting in the optimization literature. In this setting, we study the zeroth-order quantum gradient descent (E2-space) and mirror prox (l, (ly-space), again matching first-order query

---

Table 1: Comparison of oracle complexities for zero-order quantum (sub) (sub)gradient methods (this work) and the first-order classical sub)gradieett methods on minimizing G- G-Lipschitzfunnciinss functions with additional structures (2nd column). Algorithms: Gradient Descent (GD), Projected Subgradient Method (PSG), Mirror Descent (MD), Dual Averaging (DA), and Mirror Prox (MP).
Domain
Assumptions on f
Algorithm
Quantum (Oth order)
Result
Classical (Ist order)
fp-space
Convex
PSG
Ô (G
Thm
2.1
O (G (ee")
(Euclidean)
Convex, L-smooth
GD
δ (LR2/s)
Thm 4.2
O (LR2/s)
J-PP., L-smooth
GD
ő (L/P)
Thm 4.3
Ô (L/H)
fp-space
Convex
MD, DA
Ô (G2
Thm
2.1
O(G2R2
(Non-Euue )
Convex, L-smooth
MP
δ (LIF/s)
Thm
4.2
O(LR(/E)
complexities of the corresponding classical algorithms only using noisy function evaluation oracle. See, Theorem 4.2 Additionally assuming f satisfies the μ-PL condition, show (LL/p) query complexity for zeroth-order quantum gradient descent (Theorem 4.3)
Notation. We let Il-1lp denote the f--norm on Fd for p [o]: |ee| == (E le:1²) )/ For
fiite-dimensional space E, we denote its dual space by _ If c Rd equipped with an arbitrary inner product (:,-) and norm || -lpp the dual norm || ||~ is ||9||= == [u]/=e]<:]=:((s) (g,x). We define the (closed) by-ball of radius r centered at c E IRd as (c, ( Rd ||0- clp S r). We define the Bregman divergence associated to as D& y) ((x) - +(y) (Vo(y), v)- We also use the standard definitions of (strongly) convex functions; more detailed notations are summarized in the supplementary material.
Black-box setting: zeroth-order quantum (sub)gradient methods
In the black- box setting, (sub)gradient methods access the problem through a qth-order oracle O for the objective function f. On input E Rd, of returns the function value and its derivatives up to the qth-order:
of x (f(x). Vf(=),.... V)f(x))
Let (()) denote the Lipschitz constant of the qth-order derivative, i.e., for any (I, E X' x X,
S G Ellp-
where || IIp is an appropriate fy-norm and || ||- is its dual norm. For fixed q and any E > 0, the complexity of an algorithm for solving (PTT) can be expressed as a function of d and G(9) R/e (since one can always re-scale the input and output spaces, and adjust the precision accordingly). We focus on the high-dimensional setting where is potentially much larger than the other problem parameters, ie., d >> poly(G(a) R)-1). For any g 2 1, the number of queries to of needed to solve (OPT) to precision E > using classical (sub)gradien methods depends polynomially on (( R/c and thus is "independent" of the ambient dimension d [61]
First-order methods play a fundamental role in large-scale optimization due to their near dimension independence. While the convergence rates of first-order methods are far slower than the (local) quadratic convergence enjoyed by Newton's 's method, first-order methods exhibit an advantage with respect to simplicity, robustness, and the fact that they provably converge to the global optimum of a convex optimization problem irrespective of the starting point. From a practical standpoint, algorithms that rely computing second-order information at every iterate, such as interior point methods (IPMs), are often outperformed by first-order methods for large-scale problems.
Recent studies 31 32] have demonstrated that no quantum speedup over classical (accelerated) gradient descent rates can be achieved when y 2 1. Consequently, it is natural to consider instances of (OPT) where derivatives are unavailable (or accessible only at prohibitive cost). In optimization theory, this is modeled by so called zeroth-order oracles that only specify the objective function value and not its gradients (i.c., q 0), and hence is also called derivative-free optimization.
3

---

In the derivative-free setting, there is reason to be optimistic about the potential for quantum speedup due to the aforementioned algorithms for quantum gradient [ B4 and subgradient 20 75
estima-
tion, which provide an exponential speedup in d for estimating gradient from function evaluations
in the black-box model. However, previous applications of these algorithms to convex optimiza- tion [20] [5] have focused on arbitrarily constrained problems in the high-precision regime, rather than the low- www-precision regime where gradient methods typically outperform more complex techniques such as cutting plane or center of gravity methods. Consequently, the speedups in terms of dimension are only quadratic. It is natural to wonder whether the pnveenion--nddpendeee
rates of gradient methods can be achieved using only function evaluations. Our first set of results answers this question in the affirmative, as summarized in Table I under the approximate binary oracle model below:
Definition 1 (0-approx. binary oracle). A unitary U/ is 0-approximate binary oracle for if
u (لااا) + |r) @ f(x)) such that I17 - flloc < 0.
Approximate binary oracles are the standard function oracle considered for quantum optimization algorithms [10 20 75 since any classical arithmetic circuit for a function can be converted into a binary oracle by implementing each arithmetic operation with reversible quantum arithmetic.
Before discussing the black-box results, we briefly review quantum (sub)gradient estimation.
(Sub)gradientt-ber based methods are a popular class of iterative black-box methods which generate a sequence of candidate solutions based on the (sub)gradicnts of the objective function. Gradient methods lend themselves to quantum speedups due the existence of quantum algorithm proposed by
Jordan 45 and refined by Gilyén et al. (34), to estimate the gradient of function in ((1) function evaluation queries 3 These algorithms were generalized to compute subgradients of convex functions in 22 75,, resulting in the first query complexity speedups for constrained convex optimization. We state the subgradient estimation lemma based on [75), which we slightly modified for our purposes.
Lemma 2.1 (Subgradient estimation (175) Lemma 18))). Suppose f IR + R is a convex function that is G-Lipschitz on Bxx (0, 2r1) with a given norm || I|p with p 2 1, and we have quanium query access to f. which is 6-approximate version of f, as in Definition | Let r1, G > O, p E (0, 1/3). and suppose 0 E (O,ridG/p) Then, we can compute subgradient E IR2 using Olog(d (d/ p)) queries to 9- d-approximate binary oracle, such that with probability 2 1 - p. we have
PG pri
Od pri
f(y)= 2 f(z) + -g. y -) (23d)2
ly xllp -2Gvrr,
l1 glloo S (Eaf(a)
sup
That is, one can obtain an approximate subgradient using an approximate binary oracle in Defi- nition[]] with some bias that has to be appropriately controlled. In Section we also provide an improved gradient estimation based on [72) where one control both the bias and the variance (Theorem(4.)) which we apply to solve convex optimization problems in the L-smooth setting.
Equipped with Lemma 2.1
we study the quantum projected subgradient method, which iterates as:
x(41
1x (zt n92.),
Io.
estimate
Lemma 2.1
(QPSM)
While the projected subgradient method is optimal for convex and Lipschitz functions [61. the con- vergence guarantee depends on problem-dependent parameters being well-behaved in the Euclidean norm. For instance, if f is G-Lipschitz with respect -norm, subgradient method may not retain its dimension-free free rate [16). A powerful extension of the subgradient method to remedy this issue is mirror descent 66 9. which iterates as:
V = (2:) ngo.
Io.
estimate Lemma 2.1 and xt+1 E arg min (4 1(+1) (QMD)
*EXnP
where & is called the mirror map (see Definition 4j, whose gradient defines bijection between the primal and the dual ambient spaces. Due to space limitations, we review mirror descent more detail in Appendix B
A technical challenge in analyzing the above algorithms is that we must handle the additional technicality that these algorithms actually input an erroncous subgradient at point that is not the
2 Here and throughout, the Ö(.) notation suppresses polylogarithmic factors in the usual ((-).

---

Table 2: State-of-the-ar quannum and classical algorithmss for SDP and LP. For zero-sum games. set ra = 1 in LP complexities. Algorithms: Interior Point Method (IPM), Cutting Plane Method
(CPM), Matrix Multiplicative Weights (MWU), Mirror Descent (MD), Primal-Dual Hybrid Gradient (PDHG), and Multiplicative Weight Update (MWU).
SDP solvers
LP solvers
Classical
Time complexity
Classical
Time complexity
IPM 43
O (mmas + m² + ))
IPM 23
( + n)**
CPM 44
δ m (mmmms + m + )
PDHG
S
(Hoffman A,, mn)
MWU 0 76
① mns
Stochastic MD
37
(m + n)
Variance-reduced SMD 18
mn + mm +
Quantum
Gate complexity
Quantum
Gate complexity
QMWU 78
6 /mis Sote
+ v sare (mm))
QMWU 10
5 Vm++nn tode 25
QMD (Thm 3.1
δ (mns + n² (2re))
QIPM
QMD (Thm 3.2
(mma Lefe
point queried, but instead a randomly chosen nearby point. This due to a randomized smoothing procedure employed in [20 (5). We show how to handle such errors in the robust analysis by leveraging the fact that the algorithms using subgradients average over their iterates. Below, we establish that both QPSM and (Mdll@QDaccheeee achieve a query complexity of ((GR/E))) matching the lower bound of classical first-order method 82 64
Theorem 2.1 (Zeroth-order nonsmooth optimization, informal). Let X C R be closed convex set with nonempty interior. Suppose f : R² + R is convex and G-Lipschitz on X with respect to given p-norm || llp and set E (0, 1). There is quantum algorithm A that solves (OPT) using ((GR/E)) queries to a noisy zeroth-order binary oracle U/ (Definition 1 such that:
Euclidean (p 2): A is QPSM (Theorem
B.3+: R = ||
x= ||2: 0 1 (d0)))))
non-Euclidean (p * 2): A is QMD (1 (Theorem C.I.: J/; R v DD x1); 0 O1je,d (d)).
Remark 1. Quantum dual averaging (Theorem C.2 variant of mirror descent, also performs
similarly in the non- Euclidean setting (p + 2). We provide a formal theorem characterizing the
complexity of quantum dual averaging in the supplementary material.
Related work. For black-box convex optimization under noisy evaluation oracle, the most closely related work to ours is by Gong et al. 36 which analyzes quantum gradient methods in the context of nonconvex optimization, under similar oracle model. Their analysis yields algorithm for finding stationary points of an I-gradient Lipschitz (i.e., T-smooth), p-Hessian Lipschitz function using δ (1/5L-75) queries, each of which must be 0(=5/d) accurate. This algorithm can be applied to convex optimization as stationary points are global optima this setting. Our results improve upon this simple application of [36] in three ways: i) our result above do not require Hessian or gradient Lipschitzness; ii) for functions with L-Lipschitz gradients, which we analyze in Section 4 we obtain
a faster ((1/s) rate; and iii) a milder accuracy requirement of (E+*) /d²) (Theorem 4.2
There are also other works 36
that investigate convex optimization in the zeroth-order setting that focus on faster estimation of gradient estimators using quantum mean estimation. The focus in these papers is to improve the e-dependence of classical algorithms and they do not achieve exponential speedups in terms of the dimension d. Finally, under a related but different setting of online convex optimization, [1 investigated similar algorithm to the zeroth-order quantum subgradient method we analyze in Theorem B.3 for the Fuclidean nonsmooth case, yet without taking the noisy evaluation oracle into account.
69
5

---

vns(rpra/e)) where 2 1 3 White-box setting: application to SDPs, LPs, and zero-sum games
Semidefinite programming. Define ry 2 1. Let b Rn be a vector with || S Tp. and A.,..., Am, C' E xx be symmetric matrices with at most non-zero elements in any of their rows. We write the primal semidefinite program (SDP) as:
sup (tr(CX) tr(x) = Pp. tr (A,X) S b, for all i E [m], = 0}. XER
(P)
Here tr(-) denotes the trace and P > 0 indicates that P is positive semidefinite. We make the standard assumption that the matrices {Ai, [em)) are linearly independent. Defining Ao =- / and
bu = rp. the dual problem associated with (P) is given by
inf
bovo + b y vod +
Σ y.A, - sE[m]
(D)
(20-22)
where IR denotes the nonnegative orthant. We assume that the input matrices are normalized with respect the operator norm ||Aillop..... ||Am looppp ||C'|lop S 1, and that any primal-feasible solution satisfies tr(X) = rp- These assumptions are mild (and standard in the literature), since any nontrivial SDP with bounded feasible region can be brought into this form through projection, scaling and (possibly) the introduction of linear slack variables.
SDPs constitute fundamental class of convex optimization problems due to their expressive power,
capturing fundamental applications control 12 information theory 688) machine learning (50 80
finance 25 81. and quantum information science [
29 40 79). Both Linear Programming (LP)
and be used to obtain approximate solutions to NP-Hard problems in polynomial time (55 35
Conic Programming can be cast as special instances of SDP. Famously, SDP can
SDPs have been known be polynomial time solvable (to finite precision) since the pioneering work
of Nesterov and Nemirovskii 65 666 and Grötschel, Lovász and Schrijver [38). The best performing
algorithms for general SDPs (in theory and practice) are interior point methods (IPMs)
3 59
There are also algorithms for SDP based on first-order methods (6] 42 17 (6).
Currently there of quantum IPMs g 48, which replace the classical solution of the Newton linear system in interior
classes of quantum SDP solvers with provable guarantees. One is comprised
point methods with quantum linear systems algorithm (QLSA) [39 22
21 The other class is
comprised of quantum matrix multiplicative weights update methods [13
15 14 77,, 773,, which recast normalized positive semidefinite matrices as mixed quantum states that can be efficiently prepared using Gibbs sampling. Currently the state-of-the-an running time is due to van Apeldoorn
and Gilyén 773, whose algorithm runs in time Ô (Vms(rpra/ed
is an f--nrrm bound on dual optimal solutions (9ō y²) E R x Py Our main result on solving
SDPs is the following theorem. Let w E [2, 2.38) be the exponent of matrix multiplication
23 77
We now describe application of the algorithmic frameworks underlying
results on black-box nonsmooth convex optimization to white-box problems including SDPs, LPs, and zero-sum games. can be shown that, upon performing the normalization (bo. b) = (1, b), the dual SDP in (D) can be
equivalently reformulated as nonsmooth convex optimization problem (see, e.g., 42 70 81
min f(y) == Aamax (c- yERm
- y:A,)
+
(Bigenvalue SDP)
20
8E/m]
This problem concerns the minimization of the largest eigenvalue of a symmetric matrix, and can be readily solved using the quantum mirror descent method (QMD) we developed in the previous section, as we detail below.
Theorem 3.1 (SDP solver, informal version of Theorem D.2 There is quantum algorithm which
solves (D to precision E (0, 1) in time Ö(mnss n² (2) The output is an s-optimal
solution to the dual problem (D. That is, a vector (vi y²) ) E IR x Rm satisfying
YO
I
A - c and boyn + y < OPT +E,
EE m
where OPT is the optimal objective value of the primal and dual SDPs in
P

---

high-precision The objective in (Eigenvalue SDP is 2- 2-Lipschitz with respect to the fj-norm of (Lemma D.I. Therefore, we can apply the (zeroth-order) QMD to find an E-precise approximation of the optimal objective value using (((rpTa/s) queries to an evaluation oracle for f(y). The rub is that our algorithms are sensitive noise in the evaluation oracle, and so we are relegated oracles, i.e., those with polylogarithmic dependence on the inverse accuracy to which we evaluate f- A straightforward implementation is to "classically" compute the inner product term and perform an cigendecomposition on C Eie(m) YrA, to determine its largest eigenvalue. Evaluating f in this manner has cost O((mss + n²") log(1/s)), yielding a quantum SDP solver with gate complexity (mmms + nt 11") (rara(e)))
Remark 2. We compare our rumning times to state of the art quantum and classical algorithms for SDPs and LPs in Table For dense SDPs with m n constraints, our SDP algorithm provides a quadratic speedup in TpTale over the classical matrix-muliplicatiee weights method of Arora and Kale (6). We observe a similar enhancement over the quantum SDP solvers in [73], but their dependence on m and n is superior to ours.
Linear programming. Linear Programs (LPs) correspond to SDPs in which each of the input matrices is a diagonal matrix. The primal and dual LPs can be written as
max {DERS Aeg)
cJx and
min ((00.)) vo A
Tp30 b y:
(LP)
where A E Rmxx E R and 1, E R" is the all-ones vector. LPs have been known to be polynomial-time solvable since the work of Khachiyan [49]. and the first polynomial-time IPM for LP is due to Karmarkar [47].
Naturally, the formulation in (Eigenvalue SDP) becomes simpler for LPs, as the Xmax(-) term simplifies to max (c, - (A,, y) where A, is the jth column of A. Thus, one can evaluate f in time (n) using generalized quantum maximum finding (27 76 33 This yields quantum LP solver with gate complexity ((mm/((rpra/e))) (and O(m 2) complexity for zero-sum games.)
Due to their simpler structure, LPs admit more efficient algorithms than SDPs. Classical IPMs can solve LPs in matrix-multillication time Ô ((m + n)")) [24] 77]. Like the case of SDP, there are quantum IPMs that based on QLSAs [48 56 More recent quantum algorithms accelerate
the IPM framework without using QLSAs: Apers and Gribling [4] give a speedup for tall LPs with m >> n, and Augustino et al. 7 solve LPs through quantum simulation of the central path. Our application of (QM)) to solving LPs results in the following.
Theorem 3.2 (LP solver, informal version of Theorem D.3 There is a quantum algorithm which solves LP to precision E (0, 1) in time ((mmn((rpraee""
Remark 3. In the case of LP solving, the simplified structure of the objective function enables it to be evaluated quadratically faster by quantum amplitude amplification. We thus obtain an algorithm whose dependence on m and compares favorably other quantum and classical algorithms, but we cannot make decisive conclusions regarding an end-to-end speedup without making furthr assumptions the behavior of the T Tyra/E term.
Zero-sum games. There are also fast LP algorithms based on a reduction to zero-sum games, which are matrix games in which each player has a finite number of pure strategies. These problems are fundamental to computer science, economics and machine learning. A standard setup concerns two players Alice and Bob, whose action spaces are [mr] and (n] respectively. Payoffs from the game are encoded in the entries of a matrix A E [_1,1]mxx, If Alice plays action i E [m]] and Bob plays j [m), then Alice obtains the payoff Ayj. while Bob receives a payoff of -Aij. Each player aims to maximize their expected payoff through randomized strategies over the probability simplex (z, y) A" x A m giving rise to the minimax optimization problem:
min max y Ax.
(ZSG)
ZEA YEAM
Saddle points of (ZSG) are called mixed Nash equilibria, which always exist for zero-sum games due von Neumann's minimax theorem [67]
Zero-sum games can be reformulated as LPs, and vice versa (they are L.ss with rp"a = O()). This relationship has led to the development of fast classical and quantum algorithms that obtain
7

---

large speedups in m and n over second-order methods like IPMs, at the cost of polynomial scaling in the inverse precision. A classical algorithm due to Grigoriadis and Khachiyan [37 can solve zero-sum games in time ((m + n))= 2). which implies an (( + (rppraa/ee
algorithm for and be improved quadratically, and a series of works LP. Quantumly, the dependence
30 have reduced the overall complexity of solving zero-sum games from Oyy ne=1) to ( m n.5 + Our quantum algorithm for (ZSG) is as follows.
53
74
Corollary 3.1 (Zero-sum games, informal version of Corollary D.I. There a quantum algorithm which solves (ZSG) to precision e E (0, 1) in time ((m//((1/)))
Figure D Dillustrates the parameter regimes for which our algorithm provides outperforms the state of the art approaches for solving zero-sum games.
Remark It is interesting to note that previous quantum algorithms for zero-sum games (53) 74
301 improved the dependence the leading term from vmm mn to vm nE 2.5 through the of better Gibbs sampling techniques. In contrast, our algoritlum makes ( queries, and does not incur any additional polynomial dependence on 1/E because our per-iteration complexity boils down the cost of evaluating the objective function, which we do with Om log(1/e)) cost.
4 Zeroth-order smooth optimization
In Section 2 we studied zeroth-order convex optimization in general form, where the only structure of the objective function f we assumed is the Lipschitz continuity of f. measured both in E2-space (quantum projected subgradient method) and in é--space (quantum mirror descent). We showed that the zeroth-order quantum algorithms match the first-order query complexities of the corresponding classical methods, and then applied the quantum mirror descent framework to white-box settings in Section 3 yielding the state-of-the-an results in some regimes.
A natural next question to ask is whether the zeroth-order quantum gradient methods can achieve faster convergence rates when the objective function f exhibits additional structures. Motivated by this question, we now analyze quantum gradient methods in the case where the gradient V exists and also L-Lipschitz continuous. This condition often referred to as L-smoothness in optimization literature, and the classical gradient descent enjoys an improved convergence rate.
We first need a quantum algorithm to estimate the gradient. The work of van Apeldoom et al. intro- duced a "suppressed-bin -iis" version of Jordan's quantum gradient estimation, wherein the expectation of the gradient to be controlled is independent of the accuracy to which the phase estimation step is carried out 722 Theorem 31]. We modify this gradient estimation protocol so that the variance is also controlled with noisy evaluation oracles (Corollary) A.I). and hence the gradients of smooth functions We state the informal version below.
can also be estimated efficiently (Theorem
Theorem 4.1 (Gradient estimation, informal version of Theorem A.2). Let f: R - R be G- Lipsehitz with L-Lipschitz gradients, and let f, a be real positive parameters. Further, suppose we can query a O-approximate binary oracle with 0 = Ō / (T). Then, there exists a procedure that outputs k that satisfies [|[]|k -V(()) < o² and [[E[K] V loo S a using (()) calls the unitary ( (see Definition
Equipped with the gradient estimation above, the quantum gradient descent algorithm iterates as:
Ft+ 1 Tt
199
Gn.
estimnte
Theorem
4.1
(QGD)
We also quantize mirror prox, variant of mirror descent, to achieve similar rate for general ly -p-speces, similarly to the nonsmooth cases in Section 2 Quantum mirror prox iterates as:
v = V(((x)) 792.
( = =B)(t)) 792111 F241 arg arg Do (2x Fe41), xEX'PP
2+41
arg min (1 2441) zEXnP
and
(QMP)
again with Ir. and 9s, estimated via Theorem 4.1 We now show that the zeroth-order quantum gradient descent and quantum mirror prox match the first-order rates of corresponding classical algorithms, O(LR2/88 /E), as follows.
8

---

Theorem 4.2 (Zeroth-order smooth optimization, informal), Let X' S CRd nonempty interior. Suppose f Rd R is convex, G-Lipschitz, and L-smooth on X with respect to given p-norm || lpp and set & E (0. There is quanium algorithm A that solves (PP using OLLE /s) queries to a nosy zeroth-order binary oracle U/) (Definition such that:
be a closed convex set with
Euclidean (p 2): A is QGD QGDD (Theorem B.2; 2) R ((a 1/2- x² l12 0 = 1//ad (6*
non-Euclidean (p # 2): A is QMP Theorem
C.3) and R R= / D/( 21)); 0 = O1/e,d (d)))))
The primary technical challenge in deriving the above result that quantum gradient estimation algorithms are inexact and incur errors that depend on algorithmic parameters, which are themselves connected to the query complexity and bounds on the input precision. Our task therefore to prove robust convergence theorems for all the settings considered here that accommodate errors of the form incurred by quantum gradient estimation. The convergence of gradient methods that use erroneous/inexac gradients has been well studied in optimization theory [26, 28) but we were unable to find preexisting robustness results that suffice directly for our purposes.
Remark 5. As an illustration of the challenge, recent paper [T9] considers the optimization of a smooth and strongly convex function with condition number K, and obtain an oracle complexity of (1/²)* due a multipicaative accumulation of errors, which is much slower than classical gradient descent with exact gradients. In order to recover convergence rates that match classical gradient descent, we use proofs based on the classical analysis of stochastic gradient descent with controlled bias (c.f., Lemma B. 2). As a result, our quantum gradient descent do not incur such multiplicative-erro overheads and do in fact match the classical first-order rates.
Departing from convexity. Finally, we also analyze the quantum gradient descent for L-smooth functions that, instead of convexity, satisfy the Polyak-tojasiewicz, inequality:
[V)(2) 2 2p (f(x) - f(x))),
(PL)
which we refer as the p-PE condition, following 44). Note that the μ-PE condition implied by, and hence weaker than, j-strong convexity [46]. In fact, there exist nonconvex functions that satisfy the p-PL condition 78. Therefore, the result below can applied to strongly convex functions and attain the same rate up to constant factors, showing that the zeroth-order quantum gradient descent is efficient for minimizing (structured) nonconvex functions as well as strongly convex functions.
Theorem 4.3 (Informal version of Theorem B. Let f R. R. be G-Lipschitz. p-PL, and L-smooth. The zeroth-order quantum gradient descent (QGD) minimizes f to accuracy E with high probability with θ (k) queries to 0-approximate binary oracle of f with 0 = O2/e,d (=2/d)).
5 Conclusion and discussions
In this work, we studied the zeroth-order convex optimization with quantum gradient methods. We demonstrated that, using only noisy evaluation oracle, zeroth-order quantum gradient methods can match the first-order query complexities of the corresponding classical methods. These results exhibit exponential separations between quantum and classical zeroth- ooddr-ordrrr convex optimization. In particular, we analyzed our framework both in the f2-space (quantum (sub)gradient methods) as well as the fy-space (quantum mirror descent methods). We then applied the quantum mirror descent framework to develop quantum algorithms for solving SDPs, LPs, and zero-sum games, which achieve the state-of-the-ar complexity in some regimes. In short, this work provides improved quantum algorithms for zeroth-order convex optimization, both in black- and white-box settings.
Limitations and future work. The main limitation is that practical performances of the analyzed algorithms cannot be experimentally studied due to the lack of sufficiently powerful quantum hardware at the moment. Theoretically, our results generally match the first-order query complexities of classical gradient descent. For convex optimization, however, there exists faster (and in fact optimal) gradient methods due to Nesterov [62] 64], especially in the smooth setting. An interesting future work is whether the zeroth-order quantum gradient methods can match the accelerated convergence rates of the classical first-order methods. Moreover, the precision requirements are stringent to achieve the presented query complexities. As such, in the white-box setting, other quantum L.P/SDP solvers can have better overall complexity in some regimes. Therefore, alleviating the precision requirement, as

---

well as developing more structure- zeroth-ordes quantum algorithms can be interesting future directions.
Disclaimer
This paper was prepared for informational purposes by the Global Technology Applied Research center of JPMorgan Chase & Co. This paper is not product of the Research Department of JPMorgan Chase & Co. or its affiliates. Neither JPMorgan Chase Co. nor any of its affiliates makes any explicit or implied representation warranty and none of them accept any liability in connection with this paper, including, without limitation, with respect to the completeness, accuracy, or reliability of the information contained herein and the potential legal, compliance, tax, or accounting effects thereof. This document is not intended as investment research or investment advice, or as a recommendation, offer, solicitation for the purchase or sale of any security, financial instrument, financial product or service, or to used in any way for evaluating the merits of participating in any transaction.
Acknowledgements
The authors thank Rob Otter and Shaohan Hu for their support, and all their colleagues at Global Technology Applied Research center of JPMorganChase for helpful discussions and feedback. We are grateful to Sander Gribling for pointing out a bug in the evaluation oracle used for the LP solver in the first arXiv version of this paper, which has been fixed in all subsequent versions.
References
[1] Scott Aaronson. Shadow tomography of quantum states. SIAM Journal on Computing, 4965):8T0 2019.
[2] Ahmad Ajallocian and Sebastian U. Stich. On the convergence of SGD with biased gradients. arXiv preprini urXiv:2008.0005/ 2020.
[3] Farid Alizadeh, Peerre A. Haeberly, and Michael L. Overton. Primal-dual interior-por point methods for semidefinite programming: convergence rates, stability and numerical results. SIAM Journal on Optimization, ((3):7467668, 1998.
[4] Simon Apers and Sander Gribling. Quantum speedups for linear programming via interior point methods. arXiv preprint arXiv:2311.03215, 2023.
[5] David Applegate, Oliver Hinder, Haihao Lu, and Miles Lubin. Faster first-order primal-dual methods for linear programming using restarts and sharpness. Mathematical Programming, 201(1):133-184, 2023.
[6] Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights method: a meta- algorithm and its applications. Theory of Computing, 8(6) 121-164, 2012.
[7] Brandon Augustino, Jiaqi Leng, Giacomo Nannicini, Tamás Terlaky, and Xiaodi Wu. A quantum central path algorithm for linear optimization. arXiv preprint arXiv:2311.03977, 2023.
[8] Brandon Augustino, Giacomo Nannicini, Tamás Terlaky, and Luis F. Zuluaga. Quantum interior point methods for semidefinite optimization. Quantum, 7:1110, 2023.
[9] Amir Beck and Mare Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31(3):167-175, 2003.
[10] Ethan Bernstein and Umesh Vazirani. Quantum complexity theory. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, pages 11-20, 1993.
[11] Adam Bouland, Yosheb M. Getachew, Yujia Jin, Aaron Sidford, and Kevin Tian. Quantum speedups for zero-sum games via improved dynamic Gibbs sampling. In International Confer- ence Machine Learming, pages 2932-2952. PMLR, 2023.
10

---

[12] Stephen Boyd, Laurent EI Ghaoui, Eric Feron, and Venkataramanan Balakrishnan. Linear Matrix inequalities in System and Control Theory. SIAM, 1994.
[13] Fernando G.S.L. Brandão, Amir Kalev, Tongyang Li, Cedric Yen Yu Lin, Krysta M. Svore, and Xiaodi Wu. Quantum SDP Solvers: Large Speed-Ups, Optimality, and Applications to Quantum Learning. Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automala, Languages, and Progrumming (ICALP 2019), volume 132. pages 27:1-27:14, Dagstuhl, Germany, 2019. Schloss Dagstuhl- Leibniz-Zentrum fuer Informatik.
[14] Fernando G.S.L. Brandão, Richard Kueng, and Daniel Stilck França. Faster quantum and classical SDP approximations for quadratic binary optimization. Quantum, 6:625, 2022.
[15] Fernando G.S.L. Brandão and Krysta M. Svore. Quantum speed-ups for solving semidefinite programs. In Rafail Ostrovsky and Chris Umans, editors, 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 415-426. IEEE, 2017.
[16] Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends@ in Machine Learning, 8(3-4):231-357, 2015.
[17] Samuel Burer and Renato D.C. Monteiro. A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Mathematical Programming, 95(2):329-355 2003.
[18] Yair Carmon, Yujia Jin, Aaron Sidford, and Kevin Tian. Variance reduction for matrix games. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, Red Hook, NY, USA, 2019. Curran Associates Inc.
[19] Ahmet Burak Catli, Sophia Simon, and Nathan Wiebe. Exponentially better bounds for quantum optimization via dynamical simulation. arXiv preprint
2025.
[20] Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, and Xiaodi Wu. Quantum algorithms and lower bounds for convex optimization. Quantumm, 4:221, 2020.
[21] Shantanav Chakraborty, András Gilyén, and Stacey Jeffery. The power of block-encoded matrix improved regression techniques via faster Hamiltonian simulation. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programminng (ICALP 2019), volume 132, pages 33:1 13:14, Dagstuhl, Germany, 2019. Schloss
powers:
Leaiuuull--iibbi---eeeee fuer Informatik.
[22] Andrew M. Childs, Robin Kothari, and Rolando D. Somma. Quantum algorithm for systems of linear equations with exponentially improved dependence on precision. SIAM Journal on Computing, (6(6))1920-1)) 1950, 2017.
[23] Michael B. Cohen, Yin Tat Lee, and Zhao Song. Solving linear programs in the current matrix multiplication time. Journal of the ACM (JACM), 68(1):1-39, 2021.
[24] Michael B. Cohen, Aleksander Mądry, Dimitris Tsipras, and Adrian Vladu. Matrix scaling and balancing via box constrained Newton's method and interior point methods. In 2017 IEEE 58th Anmual Symposium on Foundations of Computer Science (FOCS), pages 902-913. IEEE, 2017.
[25] Alexandre d' Aspremont, Laurent El Ghaoui, Michael I. Jordan, and Gert R.G. Lanckriet. A direct formulation for sparse PCA using semidefinite programming. SIAM Review, 49(3):434- 448, 2007.
[26] Olivier Devolder, François Glineur, and Yurii Nesterov. First-order methods of smooth convex optimization with inexact oracle. Mathematical Programming, 146(1-2):37-75, 2014.
[27] Christoph Dürr and Peter Høyer. quantum algorithm for finding the minimum. arXiv preprint quant-ph/9607014, 1996.
[28] Pavel Dvurechensky and Alexander Gasnikov. Stochastic intermediate gradient method for con- vex problems with stochastic inexact oracle. Journal of Optimization Theory and Applications, 171:121-145, 2016.
11

---

of quantum states. IEEE Transactions on Information Theory, 49(2):446 456, 2003. [29] Yonina C. Eldar. A semidefinite programming approach to optimal unambiguous discrimination
[30] Minbo Gao, Zhengfeng Ji, Tongyang Li, and Qisheng Wang. Logarithmic-regrer quantum learning algorithms for zero-sum games. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NeurlPS '23, Red Hook, NY, USA, 2023. Curran Associates Inc.
[31] Ankit Garg, Robin Kothari, Praneeth Netrapalli, and Suhail Sherif. Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Proceedings of the 35th International Conference on Neural Information Processing Systems, pages 29874-29884. Curran Associates, Inc., 2021.
[32] Ankit Garg, Robin Kothari, Praneeth Netrapalli, and Suhail Sherif. No Quantum Speedup over Gradient Descent for Non-Smooth Convex Optimization. In James R. Lee, editor, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), volume 185 of Leibniz International Proceedings in Informatics (LIPIcs), pages 53:1-53:20, Dagstuhl, Germany, 2021. Schloss Dagstuhl Leibniz-Zentrum für Informatik.
[33] András Gilyén. Quantum singular value transformation & its algorithmic applications. PhD thesis, University of Amsterdam, 2019.
[34] András Gilyén, Srinivasan Arunachalam, and Nathan Wiehe. Optimizing quantum optimization algorithms via faster quantum gradient computation. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1425-1444. SIAM, 2019.
[35] Michel X. Goemans and David P. Williamson. Improved approximation algorithms for max- imum cut and satisfiability problems using semidefinite programming. Journal of the ACM (JACM), 42(6): 11111111.. 115-11455 145, 1995.
[36] Weiyuan Gong, Chenyi Zhang, and Tongyang Li. Robustness of quantum algorithms for noncon- vex optimization. In Proceedings of the International Conference on Learning Representations (ICLR) 2025, 2022.
[37] Michael D. Grigoriadis and Leonid G. Khachiyan. A sublinear-time randomized approximation algorithm for matrix games. Operations Research Letters, 18(2):53-58, 1995.
[38] Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric algorithms and combina- torial optimization, volume 2. Springer Science & Business Media, 1988.
[39] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Physical Review Letters, 103(15):150502 150502, 2009.
[40] Aram W. Harrow, Anand Natarajan, and Xiaodi Wu. An improved semidefinite programming hierarchy for testing entanglement. Communications in Mathematical Physics, 352(3):881-906 2017.
[41] Jianhao He, Feidiao Yang. Jialin Zhang, and Lvzhou Li. Quantum algorithm for online convex optimization. Quantum Science and Technology, 7(2)025022, 2022.
[42] Christoph Helmberg and Franz Rendl. A spectral bundle method for semidefinite programming, SIAM Journal on Optimization, 10(3):673-696, 2000.
[43] Haotian Jiang, Tarun Kathuria, Yin Tat Lee, Swati Padmanabhan, and Zhao Song. A faster interior point method for semidefinite programming, In Sandy Irani, Lisa O' CoCnner, and Patrick Kellenberger, editors, 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 910-918. IEEF, 2020.
[44] Haotian Jiang, Yin Tat Lee, Zhao Song, and Sam Chiu-wai Wong. An improved cutting plane method for convex optimization, convex-concave games, and its applications. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 954-953,240 2020.
12

---

[45] Stephen P. Jordan. Fast quantum algorithm for numerical gradient estimation. Physical Review Letters, 95(5)000050,, 2005.
[46] Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the polyak-lojasiewiez condition. In Joint European conference on machine learning and knowledge discovery in databases, pages 795-811. Springer, 2016.
[47] Narendra Karmarkar. A new pollynomill-time algorithm for linear programming. Combinatorica, 1:373-395, 1984.
[48] Iordanis Kerenidis and Anupam Prakash. A quantum interior point method for LPs and SDPs. ACM Transactions on Quantum Computing, 1(1):1-32, 2020.
[49] Leonid G. Khachiyan. Polynomial algorithmss in linear programming. USSR Computational Mathematics and Mathematical Physics, 20(1):53-72, 1980.
[50] Gert R.G. Lanckriet, Nello Cristianini, Peter Bartlett, Laurent Ghaoui, and Michael I. Jordan. Learning the kernel matrix with semidefinite programming. Journal of Machine Learning Research, 5(Jan):27-72, 2004.
[51] Yin Tat Lee and Santosh Vempala. Techniques in optimization and sampling. Draft.
[52] Adrian S. Lewis and Michael Overton. Eigenvalue optimization. Acta Numerica, 5:149-190. 1996.
[53] Tongyang Li, Chunhao Wang, Shouvanik Chakrabarti, and Xiaodi Wu. Sublinear classical and quantum algorithms for general matrix games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 8465-8474 2021.
[54] Chengchang Liu, Chaowen Guan, Jianhao He, and John C.S. Lui. Quantum algorithms for non-smooth non-convex optimization. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomczak, and C. Zhang, editors, Proceedings of the 38th Annual Conference on Neural Information Processing Systems, volume 37 of NeurlPS '24, pages 35288-35311 Curran Associates, Inc., 2024.
[55] László Lovász. On the Shannon capacity of a graph. IEEE Transactions on Information Theory, 25(1):1-7, 1979.
[56] Mohammadhossein Mohanmadisiahroudi Ramin Fakhimi. and Tamás Terlaky. Efficient Use of Quantum Linear System Algorithms in Inexact Infeasible IPMs for Linear Optimization. Journal of Optimization Theory and Applications, 202(1):146-188) June 2024.
[57] Mohammadhossein Mohammadisiahroudi, Ramin Fakhimi, Zeguan Wu, and Tamás Terlaky. An inexact feasible interior point method for linear optimization with high adaptability to quantum computers, 2023. ar arXiv:2307.14445
[58] Mohammadhossein Mohammadisiahroudi, Zeguan Wu, Brandon Augustino, Arielle Carr, and Tamás Terlaky. Improvements quantum interior point method for linear optimization. ACM Transactions on Quantum Computing, 6(1):1-24, 2025.
[59] Renato D.C. Monteiro. Polynomial convergence of primal-dual algorithms for semidefinite programming based on the Monteiro and Zhang family of directions. SIAM Journal on Opti- mization, 8(3):797-812, 1998.
[60] Arkadi Nemirovskii. Prox-metiee meex- with rate of convergence O(1/t) for variational inequali- ties with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1):229-251, 2004.
[61] Arkadi Nemirovskii and David B. Yudin. Problem complexity and method efficiency in opti- mization. Intes-Innersccence, 1983.
[62] Yurii E. Nesterov. A method for solving the convex programming problem with convergence rate (11k2). In Dokl akad nauk Ssst, volume 269, page 543, 1983.
13

---

[63] Yurii E. Nesterov. Primal-dur subgradient methods for convex problems.
Mathematical
Programminng 120(1):221-559, 2009.
[64] Yurii E. Nesterov. Lectures on convex oplimization, volume 137. Springer. 2018.
[65] Yurii E. Nesterov and Arkadi Nemirovskii. A general approach to polynomial-tins algorithms design for convex programming. Report, Central Economical and Mathematical Institute, USSR Academy of Sciences, Moscow, 1988.
[66] Yurii E. Nesterov and Arkadi Nemirovskii. Interior-Point Polynomial Algorithms Convex Programming, volume 13. SIAM, 1994.
[67] John Neumann. Zur theorie der gesellschaftssiilee. Mathematische Annalen, 100:295-320, 1928.
[68] Eric M. Rains. A semidefinite program for distillable entanglement. IEEE Transactions Information Theory,
2001.
[69] Aaron Sidford and Chenyi Zhang. Quantum speedups for stochastic optimization. In A. Oh, Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Proceedings of the 37th International Conference Neural Information Processing Systems, NeurIPS '23, Red Hook, NY, USA, 2023, Curran Associates Inc.
[70] Michael J. Todd. Semidefinite optimization. Acta Numerica, 10:515-560, 2001.
[71] Michael J. Todd, Kim-Chuan Toh, and Reha H. Tütüneü. On the Nesterov direction in semidefinite programming. SIAM Journal on Optimization, 8(3):769-796 1998.
[72] Joran van Apeldoorn, Arjan Cornelissen, András Gilyén, and Giacomo Nannicini. Quantum tomography using state-prepp prate-prrparttion unitaries. In Proceedings of the Seventeenth Annual ACM- SIAM Symposium Discrete Algorithuss (SODA), pages 1265-1318. SIAM, 2023.
[73] Joran van Apeldoorn and András Gilyén. Improvements in Quantum SDP-Solving with Applica- tions. In Christel Baier, loannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 99:1-99:15, Dagstuhl, Germany, 2019. Schloss Dagstuhl-LLeinnzz-eetnri fuer Informatik.
[74] Joran van Apeldoorn and András Gilyén. Quantum algorithms for zero-sum games, 2019, 100,:31904001888
[75] Joran van Apeldoor, András Gilyén, Sander Gribling, and Ronald de Wolf. Convex optimiza- tion using quantum oracles. Quantum, 4:220, 2020.
[76] Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf. Quantum SDP- solvers: Better upper and lower bounds. Quantum, 4:230, 2020.
[77] Jan van den Brand. A deterministic linear program solver in current matrix multiplication time. In Proceedings of the Fourteenth Annual -CAM Symposium on Discrete Algorithms, pages 259-278. SIAM, 2020.
[78] Kun Wang, Chi-Heng Lin, Andre Wibisono, and Bin Hu. Provable Acceleration of Heavy Ball beyond Quadratics for Class of Polyak-Lojasiewicz Functions when the Non-Convexity Averaged-Out In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 28899-22864. PMLR, 17-23 Jul 2022.
[79] John Watrous. Semidefinite programs for completely bounded norms. arXiv:0901.4709, 2009.
arXiv preprint
[80] Kilian Q Weinberger and Lawrence Saul. Unsupervised learning of image manifolds by semidefinite programming. International Journal of Computer Vision, 70(1):77-90, 2006.

---

[81] Henry Wolkowicz, Romesh Saigal, and Lieven Vandenberghe. Handbook of Semidefinite Programming: Theory, Algorithms, and Applications. Springer Science & Business Media, 2012.
[82] Blake Woodworth and Nathan Srebro. Lower bound for randomized first order convex opti- mization, arXiv preprint arXiv: 2017.
15

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our main claims are mostly theoretical. We have summarized our main results in the abstract and introduction accurately.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We briefly discuss the limitation of work in the concluding remarks.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
16

---

Justification: All informal theorems we provide in the main text are formally stated in the supplementary material with proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
This is theoretical paper, and does not include experimental results.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
17

---

Answer:
[NA]
Justification:
This paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
icy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ cppppi.ccppulli//uuuii wwwiiccgguie//eeeeeeeeeis CoodeSubeiiieeee ssi wswonnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
18

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: The research conducted this paper conform in every respect with the NuerIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
This work concerns with theoretical analysis of utilizing quantum computer for mathematical optimization. We do not believe there are significant societal impacts to be discussed in detail.
Justification:
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
19

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This work is theoretical and does not pose such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: This work does not have any experiments, and cite the original paper for previous theoretical results and tools.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the batasets.papersstt paperswi thcode. cww/ datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
20

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper is theoretical and does release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
21

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this work does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
22

---

Technical Appendices and Supplementary Material for "Fast Zeroth-Order Convex Optimization with Quantum Gradient Methods"
In this appendix, we provide more thorough preliminaries and background information that supple- ment the main text. We also state the formal version of the informal theorems from the main text, as well as their proofs. This appendix is organized as follows:
In Section A we establish notation and the class of functions we study this work. We also briefly review the quantum protocols for (sub)gradient estimation.
analyze the efficiency of zeroth-order quantum (sub) methods instantiated with quantum (sub)gradient applied to black-box convex optimization. We consider three classes of functions f that well-behaved with respect to the Euclidean norm: i) convex and G-Lipschitz; iř) convex and L-smooth (i.e., gradients are L-Lipschitz); and tii) L-smooth and μ-PL, which also implies p-strrong convexity.
In Section B
Section we study the zeroth-order quantum mirror descent and its variants, including quantum dual averaging and quantum mirror prox. This extends the quantum (sub)gradient methods from the previous section non-Fuclidean settings (Cy-space).
In Section D we leverage a connection between eigenvalue optimization and semidefinite programming apply the quantum mirror descent framework to convex optimization in white-box settings. We analyze the complexity of this approach applied to solving semidefinite programs (SDPs), linear programs (LPs), and zero-sum games, and identify parameter regimes for which our algorithm outperforms the best-known algorithms for solving these problems.
A Preliminaries
A.1 Notation
We let [d] {1, ......, d). For finite-dimensional space we denote its dual space by E*. & Rd is equipped with an arbitrary inner product (+--) and norm || Il. the dual norm || || is
1 = sup
(g.x).
From Hölder's &s inequality, one has
(x, v) < | l|l/ll/
V(x, y) E R2d x Rdd.
We let I|-ll, denote the usual 6 norm on Id forp E [o]
|ell
Jo p
At times, we also work with Schatten norms, which correspond to the fo-nosms of the singular values of Hermitian operators in given Hilbert space. For example, the operator norm II-Ilop is the Schatten-co norm, and the trace norm || ||ez is the Schatten-1 norm. Note that for e--norms, the dual norm is I|, where
1/p + 1/9 =
Hence, the norm is self-dual, i.e., setting (closed) & ball of radius R centered pd (e,,, R) = (a R² || cllp R).
|| = || ll2. one has || ||~ || 1|2- We define the
23

---

A.2 Convexity and smoothness
This work is concerned with convex functions f R + |- oo] (taking extended-real values) which are proper. meaning [(x) > -oo for all and ((v) < oc for some y. For such functions subgradient may defined.
Definition 2 (Subgradient). Let I : R - (-o0, oo] be a proper convexfunction and let a E &dom(f). We say that X is a subgradient of J at x
f(z) 2 (a) + xg VI E X.
(1)
Equation T defines the subgradient inequality, which asserts that the first-order approximation of convex function f serves as global lower bound. Subgradients extend the concept of differentiability to functions that are nondifferentiable: when f is differentiable, the subgradient is simply the gradient. The set of all subgradients is called the subdifferential of f at x, which we denote by (x))
A function / X + is G-Lipschitz with respect to || on X if
|| S G,
Vx E X.g E 0f(x).
We say that f is L-smooth with respect to if the gradients f are L-Lipschitz continuous:
IV - ffl)l... L || =ll V(z,ī) E x
Note that any twice-continuously differentiable function is L-smooth with respect to || on IR and only if
fV))2,,, - L||=|| for all æ, 2 E R.d
Smoothness assumptions provide a global quadratic upper bound on the function around point æ:
L || x=| f(x) S f(x) + (Vf(x), x) 2
function f is p-strongly convex on X' if there exists a > such that
((Ø) Z f(x) + (v]()), - - x) + カリ x||2.
Collecting these facts, when || = ||2 is the Euclidean norm, smoothness implies
{()))
and strong convexity implies
v²)(2) PI
for all x E X. The ratio = is called the condition number of f.
The Fenchel conjugate f Rdd - cl (TR) of function f defined by
(v) = sup ((x, v) - f(x)) y E ER.
zER
The conjugate function is defined as the point-wise supremum of affine functions of y, and is therefore convex by definition. When f is convex and differentiable, f is the Legendre transform of f.
The conjugate function admits useful identity: the inverse operator for the gradient of f is the gradient of the conjugate:
V = (1
A.3 Quantum gradient estimation
Gradients with suppressed bias. We will use the "low-bias" version of Jordan's protocol for quantum gradient estimation restated below, which were introduced by 772 in the context of state tomography. Such protocols allow for the expectation value of the gradient estimate to be made arbitrarily close to the true value, independent of the protocol accuracy itself.
24

---

Theorem A.1 (Suppressed- bias gradient estimation (172) Theorem 31))). Let L'ro', E (0, and g E IRd such that |/ I 2/2 Let b == [log2 (2) and B = 2 If
exp (2Ti(g, 2)) (2)
S 24 [4(1n66d/)]] +
Bd
given access to 8 8[In(6d/6] + copies of (b)), we can compute k E [[- 21 satisfying
11d
Pr[l go > o' S and
[[[[A]] go1اo S 6.
The procedure has a gate complexity of O (dlog(( (3) log( log( $ log( ( ))) and requires a corre- sponding circuit depth of O (log( log( g log( ()).
utilize the suppressed-bee gradient estimation subroutine above, which we modify such that variance is also controlled with noisy evaluation oracles. We start with the following corollary:
Corollary A.1 (Suppressed-bing low-variance gradient estimation). Let a (0, 31 and E IR such that |0 s Let b = [log2 (4/o)] and B == 2h. If
σ²
(+))
Σ aEGg
exp 2))
B
32 In(8d/o2))
given access to 8 [[[nnd///
oo)l + copies of (2b), we can compute ls [- 21 satisfying
Bilk- g112al o² and [[[[]] gll a.
The procedure has a gate complexity O (dlog? log(1)))(11)))) and requires corresponding circuit depth of O (log(Vd/o)log((/o))
(0. 4]. We use the procedure in Theorem A.1 with parameters o' 0/2, 5 = 30 /4. The number of copies, gate complexity, and cireuit depth follow by direct substitution with minor simplifications. It remains to calculate the variance of k g. Noting that by assumption and the guarantee on k, it holds that | glloc < 1, we observe
Proof. Define
4 0² + Pr[lA glooo 0/21 5
E||| g 1
where the probability' is bounded due the guarantees Theoremm
This completes the proof.
Using the above corollary, we can estimate the gradient of smooth functions with noisy oracles. The quantum gradient descent algorithm we analyze Theorems B.1 and B.2 will therefore invoke the following result each iterate. In the Euclidean case in Section note that 0_ v in the below statement.
Theorem A.2 (Suppressed- -iasssssed-issssss-- Bias Gradient Estimation of Smooth Functions with Noisy Oracles). Let f: Rd - IR. be G-Lipschitz function with L-Lipschitz gradients in p norm ||-I], and let 0, be real positive parameters, o/G < 1. Let 1 < 0, 0. < d be such that
| < 0 0||=||00 Vz Rd
| < 0, 1201/o0, Vx IRd.
satisfying 00. < Define y E Rdd, Then, if
24 LLo'
and let f be 0-approximation for in Bel (y, for some
0- 0
L log (dG2/o2)
25

---

there exists procedure that outputs l that satisfies
Billk V - (0.0)² and
[[]]]] - Vf(v))la S $0.0
using 8[In(T2dG2/od /o2)1 + 1 calls to the unitary Uj = Enery exp exp (2rlflytrz)
(xr) (al. The procedure has gate complexity O (dlog" (VdG/()Vd//)) log(G//o)) and circuit depth of o (1og( [log(V/G)))oog(//o)) The unitary Ug can be implemented using ((1) queries to bi- nary oracle for j, O Ro vavl/// a (GRy)-phase oracle where Rg is a length scale chosen to ensure that for all B (v, r), [(x) S GRo.
3Gr
Proof. First, note that by assumption for arbitrary p-norm ||||| with p 2 1, we have
1(()) f(v)] - G||æ yll z G - ylloo,
and
L - -> - 2 1| y1
02 L 1| - vll.e.
2
It suffices to show how to compute V f(0) by simple shift of co-ordinates, and by similar argument assume without loss of generality that f(0) 0. First, note that since is the 0-approximate version of f and the gradient / is L-Lipschitzness, we have for all x E Gg.
f(rx) 3Gr
[(rx)
(rx)
V((())
f(xx)
[(xx)
[(xx)
V
3Gr
3Gr
3G
3Gr
3Gr
3Gr
3G
0
Lr
+
3Gr
6G
200
(2)
3G
Now, let (1b) 1 Enegg exp
(rrif(ra) 3Gr
(z).
Using the above estimates and the inequality
/Bx
le cabl S b). follows that
V Vf(0)
>)
f(rz)
V
(1) Bd
Σ
exp
2Ti
x
(x)
2T max WEG
3G
3Gr
3G
ZEG
Eg
V 20
2T
3G
(o/3G)2
32
(2((8//o//3G)))
+4
where the last line follows from our choice of 0 in the statement. Since is G-Lipschitz (in norm 2 1), we have
obtain an estimate k satisfying. I 1/3, and we can now apply Corollary A.1 with o - o/3G to
Vf(0)
E
k
(0.a/3G)
3G
[5(0)
and
B[K]-
0.o//G.
3G
Clearly, = 3Gk' is an estimate satisfying our desired properties. The number of copies of ()) required, the gate complexity, and the circuit depth can be determined by direct substitution. It is evident that each copy of (16) can be prepared using a single call Uy, resulting in the desired oracle complexities.
26

---

Quantum subgradients. In the case of minimizing convex and G- G-Lipschitz functions, which can be nonsmooth, the gradients might not be available. In that case, use the subgradient estimation Lemma 2.1 which is based on 755: we slightly modify for our purposes, which we prove below. Note that one can perform a similar analysis with (20 Lemma 2.4].
Lemma A.1 (Subgradient Estimation in arbitrary n--nomm)) Let > 0, G 0. pe (0, 1/3), and suppose 0 E (0, T1 TidGGppp Suppose f : E2 + R. is a convex function that is G-Lipschitz with respect to given p-norm I| with 2 1, and we have quanium query access to f, which is 0-approximate version of J. via a unitary over a (fine-enoug)) hypergrid of Brx (x, 2r1). Then we can compute an approximate subgradient 9 B. using (log((d) (d/p) queries to U and Ut, such that with probubility 2 we have
G
f(g) 2 f(z) + (9.9- z) 23200
0.1
llq - x1| 2G0r1,
(3)
prd
where 1 S 0, 0r < d, and 00.- S d.
Proof. Letr2 -V /af and note that r2 S r1- The quantum algorithm chooses a uniformly random
E B& (0, r2) and applies Jordan's quantum algorithm to compute an approximate gradient at by approximately evaluating f in superposition over a discrete hypergrid in B (2.r2//)))
Since (2, B2(2,22). 77 Lemma 17] implies
22 f(z)
[(++)) - f(z) - (M v()2 S
sup y B. (0.ra/4)
2
Also shown by (75 Lemma 11] and Markov's 's inequality have
2dG
( f(z) pri
(5)
with probability 2 1 - p/2 over the choice of z. If is such that Equation 5 holds, then we get
f(z+ ((2+0) f(z) - (v)(r)
dGr3 0.
sup
Ro. (0,r2/4)
pr
Also we have by Definition
1 0.
Now apply the quantum algorithm of (75 Corollary 15] with r 2r2/d, c= f(2), - and B Gr. This uses O (log(d/)) queries to U and Ut, and with probability p/2 computes an approximate gradient& ğ such that
/ [(=)
8. 42md
Od
0 = 4..42 Ty
(6)
2r2
pri
Also, if is such that Equation 5 holds, then by 75 Lemma 10] we get that
V (ra) f(z) - -0/,
r2 (r))))((2)
dGrg
AdG
sup (E0f(=)
2
pri
pri
and therefore by the triangle inequality and Equation
6 we get that
sup gEAf(z)
||g alloc s sup gE0f(2)
v (r=) f(z)
|_= + | f(z) -(=)-9( -
< sup geff(z)
V (rz) f(z) + (2/)) f(x) -
OdG
0d3
+ 42 m pri
pri
< 232
V
(7)
pr1
27

---

Hence,
Od
sup SEAs(s)
119 10--90 9ll. 23%0,
(8)
pr)
Thus with probability at least p. for all y E dom and for all g E df(z) have that
f(v) 2 f(=) + (g. 2)
f(0) () + (g g.v) + (f(x) - f(0)) + (g. -z)
2 f(0) - (g. 5) - -1 - 9. G G||z|| || |
2 ʃ(0) (Ø.9) 11 Tll. |lvll - 2G =||
Od&G
z f(0) (..)) 23
|yll| 2G
pr
B Convex optimization with quantum (sub)gradient estimation
B.1 Zeroth-order quantum gradient descent
In order analyze quantum gradient descent, we need a quantum algorithm for gradient estimation. As mentioned in the introduction, a core challenge is that quantum gradient estimation algorithms incur errors that depend on algorithmic parameters, which have be handled carefully achieve compelling convergence rates and query complexities.
B.1.1 Strongly convex functions with Lipschitz gradients
We first analyze the quantum gradient descent for functions with L-Lipschitz gradients (also known as L-smooth functions optimization literature). We further assume that f satisfies the Polyak- Lojasiewicz inequality:
V ( 2 2p ()(x))((x))) f(x)))
(P..
which hereafter we refer to as the μ-Ptt condition, following [46 Note that the μ-PE condition is implied by, and hence weaker than, μ-strong convexity [46
Therefore, the results we present below can be applied to strongly convex functions, and attain the same rate up to constant factors.
first state descent lemma for gradient descent with bias and stochasticity, which are the main ingredients for proving Theorems B. and B.2 The proof largely follows 2 modified appropriately for our setting.
Before analyzing the quantum gradient descent equipped with Theorem A.2
Lemma B.1 (Descent lemma of stochastic gradient descent with bias for smooth functions). Suppose fi Rd + R has L-Lipschitz gradients. Consider the biased stochastic gradient descent algorithum It-1 It 199t. where 9t fxxx) + bt + n4, such that
E, [ = Vs(x)) + b, (e Em[ma] 0) and
= 2
11,
where [+][] = E. [-|are] denotes expectation conditional on He. Then, for any step size S t. the following is satisfied:
1
[e(((r)))- [(x)]
-VI((())) + " 11bel12 122 +
2 o
Proof. We start with the L-smooth inequality
64
Equation 2.1.6]:
y f(y) S f(x) (Vf(z). - x) +
ly x x1/2.
(9)
'In fact, there exist nonconvex functions that satisfy the μ-PL condition
78
28

---

Invoking the above with - 21+1 and x f- 21, we have
Sertiss((i) (a)) 2111 - -x4) + 2 ||00411 - 2ellé
= -((x) - 7 (V)(z)))))) + Lnj²
2 l1sel12
f 17 (V)()))))))))) + Lij²
11ge [g + E3 1
2
Lnd
f (V(())))) g.) +
2 (11ge Ee |1 + (gc Eeloe]. Er (ge)))
Taking expectations conditional on Zt, we have
Lnj²
B.[S(+++1)] s f(xx)) - 7
+
E. 119 - R.(g. + [.
2
= -(())) - 11 (z)())) V)())) + +b,) Li²²
(Belllgt E3 | E.llV + +b
L
Lnj²
$ f((1) - (V(()) + +b,) +
0
+
V f(,)) + be11.
2
2
Choose 5 1, then we have
Es [f(++1)] S f(x)) 7 (Vf(x)) Vf(x)) b,)
Ln
2 o,
2 [f + ball2
"
= =f(x)) + 2/2 (-2 (V.( Vf(xa) b.) + [V)(z) be bz + Lu²
!
2 0
2
= f(x,) + "
[- [ + (bb : + La²
2 2.
2
where in the last equality we used the following identity:
-2 (a, a + b) + ||a bll2 = - ||a|12 2/22 + |10122
Lemma B.2 (Stochastic gradient descent with bias for J1-L & smooth functions). Consider the biased stochastic gradient estimator described in Lemma B.1| Assume f: Edd + E is μ-PL as in (PL). which implies y-strong convexity. Then, after running T iterations of stochastic gradient descent, the following satisfied:
116112 2/
nL
((()) f(x)))
2p 0
Proof. First observe that by Lemma
B.1 and
PE
we have
E.]f(x+41) f())=(()))) + f(x)(((==)))))))))) ((x)))(())) s 7 V1
7 111.1112
T2
o
1 0"
11b112
s
L 2 o
1b.11
Assuming ||b, | for all (due quanutm gradient estimation, we can ensure all b, are below
some bound which we denote [[bl],, and unfolding for T iterations, and using the tower law, we have
T-1
T 2
B[f(xr) - f(x') s (1 - (f) f(x*)) +
(1 nu)*
17 101
1011
2
2
k=
|
TTT
- mp) - ff:b)))))))))))))
2fu
2p
29

---

where in the last step we used
(1-c) - Σ 11 c)a
for C (0,1).
A=
k=0
We are now ready analyze the convergence quantum gradient descent for μu-P functions with L-Lipschitz gradients.
Theorem B.1 (Quantum gradient descent for μ-PL smooth functions). Suppose f: R R is G-Lipschitz, T-smooth, and pt-Pt, which also implies p-strong convexity. Consider the (zeroth-order) quantum gradient descent T++1 = 24 - nht with step size 1) = 1/ that outputs the last iterate XT after running T (x log 1/e) iterations, where the (biased stochastic) gradient gt is estimated via the quantum gradient estimation in Theorem A.2 on each iteration. Let Eo == EE/ and == L/ p. Assume that d/co 2 1/5, and one has access O-evaluation oracle satisfying
2²
(
=
8.80 (08xlog((P//0)22)
450d G (32 In (360d G /(EN) +4)
Then, with probability at least 2/3, one can obtain an e-approximate solution to (PT with
T (olog (d² /En))
queries to an 6-approximate binary oracle of f. The procedure has a gate complexity O (dd (d2/Eo) log(d/su)) and corresponding circuit depth of O (log(d /ea) log (d/ea))
With Rohhue oracle access instead, the above complexities must be multiplied by factor of O Rov RovaLL/V VVV. where Ro is a length scale chosen to ensure that for all x E B r)
GRo.
Proof. We start from Lemma B.2 where we plug in the quantum gradient estimation from Theo-
rem A.2 (with 1 0. = /d). First, for the bias term involving ||b|| 2 we have
| 112 || v f2 s d|[B vf(=))] do² Vt.
Next, for the variance term involving o have
of E.ll.g. E, [g.111]] < dlE [l gr Eg [9.]1
s 2d [Eellge vx(x)) E E, ge111.1
s 2do²
Therefore, arrive
2o² B(((TT) f(x)) s (1 ( f(x*)) + 4nL)
24
The first term exhibits linear convergence, which we bound by e/2 as follows. Observe that
T log 1 pm = T(- - --rr)) 2 - log 2(f(#o) - f(x))) = log (2[((x)) - -(xx))
6
6
Using log(1/E) 2 - for & E (0, 1), we have
log - pm
I pm
2
pm
log
1
I-pm
Thus,
1
2( - f(x*))
1
2(f(xo) f(x)))
T pm
log
log
8
log
8
T-pm
30

---

(((()n)
suffices to have the first term bounded by e/2; with r) = 1/L, we have T Now, for the combined bias and variance term, we want
k: klog
do²
E/ 4nL)
S=
su
(1 + Lm)
(10)
2μ
5d
E/ < By assumption ac for the evaluation oracle in Theorem A.2 we get:
& I 1 as required. Plugging (TO) back into the precision requirement
5d
= 2Ld(3G)² (n + +4) 2Ld(3G)² 32 In (2dG22
5d
+4)
4)
Simplifying the above bound gives the desired result the precision requirement to the evaluation oracle. Using our choice of and applying Markov's inequality, we get
1 - 3E (f(x))
f(x*)]]
3
Prr[f(a.) - f(x'((()))))))))) s].
To complete the proof, for each gradient estimation, we make 8 Inn /1=1 Olog(dd /eo))
calls to the unitary Uj per Theorem A.2 and using the bound in 10 This gives the total number of
calls the statement combined with 2 K. log ((((=)))((())))
we obtained previously. Finally,
for the gate complexity, circuit depth, and phase oracle cost, we again use the bound (TO) to the statement in Theorem
B.1.2 Convex functions with Lipschitz gradients
We now perform a similar analysis for convex functions with Lipschitz continuous gradients, but not necessarily strongly convex.
Theorem B.2 (Quantum Gradient Descent for Convex & Smooth Functions). Suppose f: RRd TR. is a convex function with I--Lipschizz gradiens.. Consider the (zeroth-order) quantum gradient descent Tt-1 = 2t 2t-119 799c with step size n 1/L that outputs the last iterate 2T after running T O /E) iterations, where the (biased stochastic) gradient is estimated via the quantum gradient estimation in Theorem A.2 on each iteration, and
|| - xx 1l2. Additionally, assume we are given access to the value of [(x* ( Let Eo == (GRR) Assume one has access to an O-precise evaluation oracle satisfying
e²
G2 d3
0 < A608RA&922T 32 In (11228G2R1/62)
Loglog(
+4)
Then, with probability at least 2/3, one can obtain an E-approximate solution with
θ LRR
(T
log (d/eu)
queries to 8-approximate binary oracle of f. The procedure has gate complexity o (dlog" (d/Eo) log( log(Vd/sa))) and corresponding circuit depth of O (log(d/eo) log( vdjso)).
With (GRa)- oracle access instead the above complexities must be multiplied by factor of O RovaT./ /o), where Rg is length scale chosen to ensure that for all x. E Bd (zo, f(x)) GR
"This can typically be assumed without loss of generality with only polylogarithmic overhead in the inverse emror. This is because as long as a bounded interval containing f fxx is known, we can guess a value and run our algorithm with that guess. The success of the algorithm can be verified by computing single gradient at the final point. This allows the true value of the optimum to be calculated by binary search.
31

---

Proof. We follow the standard convergence proof for gradient descent on smooth and convex objec- tives (e.g.. [5] Theorem 2.9]), with modifications handle with the bias of the gradient. Define
d: == (*+++1) f(=*). By convexity and Cauchy-Schward we have 8, =
( - S (Vf(z)), x²) V (2))a 1=112 [
from which we have the bound / R - [ From Lemma B.1
we have:
11 L
E2 [
6,
2 [ 11 + 2 |1b.11
!!
0
10,11 11 + n²
"
S 6,
2
R2
+
2
4
1
83
6 2L
16 +
2L 0x
R
2L
where we denoted E,, = [- The key insight is that, using Theorem A.2 we can suppress both the bias and variance enough on each iteration to ensure descent. Hence, demand
de and o, S 2R
6e 2R
lbell2 S
(11)
which we will justify later. Given that we assumed access to f(x"), at each iteration we can compute the value & to input to the suppressed-bias quantum gradient algorithm. Then, we have
57
1
1
E, [6c+1] S 6,
11b
2L a
2LR
2L
5,
87
83
$ 6,
2LR
SLR²
SLR
1
8
2
6, 4L
R
Taking expectation again and using the law of total expectation, we have
8:
27
13 [5,
E [6 S E
[o.]
4L
R
4L
R
where the last step follows from an application of Jensen's 's inequality. Rearranging, we have
1
E [6++1] E
[6.41]
E [8++1]
E [6
1
4LK
(E (8,))
[..
[1+11]
E [6+11]
E [6.
Rearranging and unfolding, have
[.
6
4LR
80
4LR
where we used [[6]] 2 E(5,-1 1| coming from the assurance of descent. By L- L-sooothness in 9 we have
L
LR
8u
f(0o) f(x*){++=>))))))
20
x
112
2
Thus,
2
1
1+8
4LR
E E <
E [8
5u
4LR LR
4LR
4LR
t+8
This gives the desired scaling T. remains justify the choices in IT). To that end, we again use Theorem A.2 (with 0 = 0, Vd). For the bias term | l12, have for all t,
| 1l2 [[ v((x))l2 S Vda.
For the variance term involving o²
of = Elllg: B.gh]1 11 < 2 (Billg - + ((
< 4do2.
32

---

Therefore, it suffices to choose 2do² 2 o 16 to compute the precision requirement on the evaluation oracle from Theorem A.2 We will assume that once we observe that 6,+1 S E, we terminate the algorithm, and so 6, in the bias and variance requirements in (11) is lower bounded by Thus, we only have to suppress the bias and variance enough such that
(12)
16R
We now plug in our condition on a in 12 to obtain the precision requirement on the evaluation oracle.
22
o 2Td(3))² (32 /o2) 4)² 2Ld(3G)2 32 In (2dGG2
16R2d
16R2d
c²
+ +4)
The statement in the theorem can be obtained by simplifying the above.
To complete the proof, for each gradient estimation, we make 8[In(72dG* /a²) (IlndG"//o²)) calls to the unitary U3 per Theorem A.2 Using the bound in 12) we have
ICG2 02 ))=
= θ In (RE))))
+ In
E²
giving the total number of calls in the statement combined with 7 = O Finally, for the gate complexity and circuit depth, we again use the bound Theorem A.2
LR
we obtained previously.
(10) to the statement in
Using our choice of T and upplying Markov's inequality, we get
1 Pr [f(() f(x") 3E (f(x)) f(x')]
3
= Pr[ff(x) f(x=) =]
B.2
Zeroth-order quantum projected subgradient method
Suppose that f Rd + IR is G-Lipschitz on X, where X' is closed, bounded, and nonempty. Define K == diam (X) = sup, wup x ||
y/|2- Define 7Tx to be the Fuclidean projection onto X. The subgradient method is defined by the following equations:
1e 1xx (x+ 19::), Of(x).
(PSM)
We now analyze the precision requirement on the evaluation oracle to implement the zeroth-order quantum projected subgradient method for convex and G-Lipschtiz functions, which be nons- mooth. The algorithm we analyze is similar to the (classical) subgradient method but equipped with the quantum subgradient estimation from [75] Lemma 18), which we reproduced in Lemma A.I Note that one can perform a similar analysis with 20 Theorem 2.2].
Theorem B.3 (Quantum projected subgradient method). Suppose f -R is convex function that is G-Lipschitz. Consider the ceroth-order quantum projected subgradient method r1+1 Ix (I: ng:)), with 17 where the ğr is an approximate subgradient at xt computed via quantum subgradient estimation in Lemma A. on each iteration. Assume one has access to an f-precise evaluation oracle for f,
R GVT that outputs the average + E Iz after running T iterations,
with = G Then, using the quantum projected subgradient method, with probability
at least 2/3, one obtain E-approximate solution to [PP with Ö(G² R2 /s²) queries to (G2RR2/²))
0-approximate binary oracle of f and ((dddT))(GR//))) gates, where Tn is the cost of performing the projection onto X.
Proof. Recall that the projected subgradient algorithm iterates as J++1 IIx (x; - v/tt). where ÿ. subgradient 21, and 0 is step size, which choose later. For analysis purposes,
33

---

denote the intermediate variable before the projection step 2.. That is, we can write the projected subgradient method as
2t+1 Zt 7/9t.
2(+1 11x (2++1).
We analyze the case where the projected subgradient method is performed for T iterations, and outputs the average: + Σ Zz. Following standard analysis of projected subgradient methods (e.g. [6. Theorem 3.2)). and utilizing Lemma A.1 (where 0 = 0" = vd when we specifically use the
Euclidean norm || |12, i..., p 2), we have:
OG
f(x)) - f(x') S (0t, - x²) + (23d)
24 x² x'1l2 + dr
pr
DG
(st - -141, - x²) + (23d)
| x² 112 2GV
pm
PG
(l|are - x111 - || - x x²113)
+
11 + (23d)²
|0, x'112 + 2GVV
2n
2
pm
$ 2m
(11ar - x²112 - -|= - z²113)
"
1..12 + (23d)²
OG
K + 2GV
2
pr
OG
< 2n
(114 - x²11 - -113241 - x=13] 13)) +
| 12 - (23d)²
V
K + 2GV
pri
-
x²112
|| - x²1 12) +
1
|gg + 3o113 + (23d)²
V pri
OG
K + 2GV
2n
2
AdaG
AG
$ 2m
(1| - x²112
|| - x
122) + G2 + 23
+ (23d)²
K - 2GVdr
pri
pri
where in the second equality we used
||a|13 + |bb13 ||a -b2 2aa b). and the second inequality
is since Te+1 x and hence ||=+11 x² 22 2 1 x² l12- In the last step, we also used from with 1 = 0. vd such that
ع112 < 232 Od&G
1|g (=
sup
V pri
for some z that is internal to the quantum subgradient estimation algorithm.
Summing over t E (T), and using |||]
- 111 < R22 we get
R²
G
Od (23d) |
OG
Σ [(())))((=))
+ T 23
KT + 2Gvdr
2n
pri
pri
Dividing both sides by T, choosing 11 convexity, we have
OVT, and using / (( m1) S + Σ f(xx) by
n
-
| St ) f(x))
RG -
Od VTpr
BG
-
VT + 23
+ (23d)²
V
K + 2GVdr
pri
We want the above expression to be bounded by e. First, choose T (3RG) 2
and ri 6G Then, the first and the fourth terms are bounded by e/3. We want second term to be bounded by e/3 as well; before doing so, we first choose the failure probability P such that the all I calls of quantum
34

---

subgradient estimation in Lemma A.1 succeed with (overall) probability 2 2/3. Observe that, if we choose p = 1/T",, then the probability that none of the T subroutines fail is:
T
T 2
(1-37)
21
3T
3T
Note that the above bound holds even when each call of the quantum subgradient estimation is dependent; indeed, by union bound, at least one call of the quantum subgradient estimation fails is at most 7 1/7) S 1/3, or equivalently, the probability that none of the 7 subroutines fails is 2 2/3.
With our choice T = (3RG) 2
3
we have = शा. Given our choice the second term becomes
Ad R
xL50G"RR R
23
S (23* 9.6 9.6)
Trp and the precision requirement on the evaluation oracle 0 is
e²
+ (23d) K (OC. RT 6Gvd 1/2
d R²
(23 9.
22
3
Solving for 0, we get 0 = O G
completing the proof.
Finally, from Lemma 18 in [75] the discrete hypergrid used in the subgradient estimation algorithm has radius r 2na, with r2 = d'
0rie
giving the phase oracle cost.
dG
C Generalizing to non-Euclidean geometries
We have seen that one can obtain dimension-free oracle complexities when the objective function f Lipschitz in the Euclidean norm. However, if f is well-behaved in some other norm, the schemes discussed in the previous section may fail to maintain their dimension free rates. Moreover, many problems in optimization are defined over non-Euelidean spaces like the probability simplex and the cone of positive semidefinite matrices.
In 61 Nemirovskii and Yudin observed that one can first define a mapping from the primal space to the dual space, perform the subgradient update in the dual space, and subsequently map back to the primal. This approach allows one better leverage the problem geometry, and is well-suited to high-dimensional constrained optimization problems. In order to keep the paper self-contained, we briefly review some concepts that are essential to the mirror descent framework. Then, we prove that one can instantiate mirror descent with quantum (sub) gradient estimation, and provide specialized implementations, such Nesterov's 's dual averaging [63] and mirror prox [60].
Note that within this section, we use to denote an arbitrary p-norm (p 1), and its dual norm as I...
C.1 Bregman divergence and Bregman projection
The methods we discuss in this section will require distance measures beyond the Euclidean metric. work with the Bregman divergence, defined below.
Definition 3 (Bregman divergence). Let P C TR' be convex open set. Given a strictly conver differentiable funcicioo T R, we define the associated Bregman divergence D3, :PxP xP R Rzo by
Dz 3) - (Vo)))(
Note that (x. .. is nonnegative for all (I, E PxP, since & is convex. The Bregman divergence can be interpreted as the level of error present the first-order Taylor series approximation of to (x:). Unlike the Euclidean distance, the Bregman divergence is not symmetric. This is because the Bregman divergence computed according to the local geometry with respect to 4 at Z.
The following identity will be useful in our analysis later:
(13) For closed convex set X C P. the Bregman projection II : P + X' of point x E Rd onto X' is defined as (T) == arg min Do .). Note that the Bregman projection uniquely defined since d is strictly convex.
(v ( w) D1 .) + D& (+(w, x) D (w)
35

---

VΦ
(1))))
P
79t
-++1
2++1
X
II P
R
Tt+1
V
Figure 2: One iteration of mirror descent. iteration the point F2 E X the primal space P mapped into the dual space Rd, where subgradient step can be taken. Upon mapping back to P, the Bregman projection IT applied to obtain the point r4+1 in X.
C.2 Methods of mirror descent
Mirror decent fundamentally applies a primal-dual approach to convex optimization, relying on the ability to map points from a primal ambient space to its dual space E (and vise-versa). This mapping is defined as the gradient of a mirror map, which we formally define next. For more details on mirror maps, we refer the reader to [16] Section 4.1].
Definition 4 (Mirror map). Let P C RRd be convex open that contains X in its closure, i.e., X' C cl(P). Further assume that the intersection of X and P is nonempty. A mirror map $ : P + R strictly convex, differentiable function, whose gradient V satisfies the following:
1. The gradient of t takes all possible values in Rd, Le., VT(P) = Rdd.
2. The gradient of 4 diverges on the boundary of P, i.e., lim V oc.
At each iterate ( E Rd in the dual space. From here, subgradient step (with step length r)) is taken in improving direction with respect to the dual. One can compactly write the mirror descent iterate as
mirror descent algorithm, primal point x; E n nP is mapped to a point
Et+1 I
V (V4(x)) - n9:)). E 0f(r)).
(MD)
The following lemma from [6 illustrates how the Bregman divergence functions similar to the Euclidean norm squared in terms of projections.
Lemma C.1 (Lemmaa 4.1 in 16 Let r E X and & E P. Then,
(V4 (a) - v4 3) II) z)
< 0 = Do (z. (1)()) + Dr (II% < (x 2).
Adapting a standard convergence proof for mirror descent (see, e.g., [6. Theorem 4.2]) to account for quantum subgradient estimation suffices to prove the following result for l, and Schatten norms.
Theorem C.1 (Mirror Descent Using Quantum Subgradient Estimation). Let C Rd be closed and bounded convex set equipped with given p-norm - with 2 1. Denote K == diam = supz,ex Ixc - yil- Suppose f Rdd -, TR. is a convex function that is G-Lipschitz with respect to || and attains its minimum at x² E P.P. Let be a mirror map that is p-strongly convex on given point
X'P with respect to ||| ||. Suppose Assume one has access to an 0-precise binary oracle for J. with
X n P and define R Do(x" 20, 21).
0 8-0
G2
Consider the zeroth-order quantum mirror descent method
Zt+1
11
(
(V nē.))
(MD)
36

---

with n= G F. that outputs the average T Ei= 2, after running T iterations, where the 9t is an approximate element of (f()) estimated via the quantum subgradient estimation in Lemma A. each iterate. Then, with probability at least 2/3, one can obtain an s-approximate solution with
((( GR
queries to O 0-approximate evaluation oracle of and (((d + Thead) ( where Thexs is the time to carry out the operations necessary to progress to the next iterate.
Viu
GR Jue
gates,
Proof. From Lemma A.1 the output satisfies the following with at least 1 p probability:
BdG ll4 - x|| 2G
f(g)= 2 f(x) + (g. q - x) - 23²00,
..
pr1
where 1 1 0,00 00 S <d and 00. v d. With q t xx and rearranging, have the following:
OdC K + 2Grr
E = 23 0.
(14)
pr
Ad3G
2 23
|| x1| + 2Grr
/ - -(x") + (0,x" - x))
where we also define the quantity E Continuing, have
f(x1) f(x*)*++++))))))())) < (gc. 24 - x²) + E
Eq. MD 1
(VD(I+)) (T)(++)), - xx) +
Eq 13
(Do (x",zz) + Do (2i, Bo+1) - D& (x", 1(41)) + +11
7
Lem
(Dx (a*, ax)) + Du (ot, F(+1) - Du (x", m(41) Dw (#1+1: F(41)) + E1-
1
The term Dq (x*
xx) D& (x", IT+1) leads to a telescopic sum when summing over t [T]. What remains is to bound the other term using j-strong convexity of the mirror map combined with the identity
az bb < a²
E.
4b
Indeed,
Do (2r, F+41) D& (5e+1, B(41) = ((x)) - ((. - (T)+)t)), x(+1)
11 |1 Z141 11
S (v)(x) (1((.41), It I141)
2
n (gr, Ft x(41) 1 11 I141l1 11?
S 1 llxell. | - xz+1 ||
1
||,,,
2z+ 112
2
/ ||,0 - re+1ll 112
S n llāe - g + sll. || - xe+1|l
2
S n ((1g. - all. + +G) ||ar - x1+1ll)
.t2 || - =2++1l
(n(G Ez))²
2/1
G2
(15)
where in the second to last step, we used from
8):
DdG
sup gEaf(=)
1 - ~l1. < 232
= 2
(16)
pr
37

---

for some that is internal to the quantum subgradient estimation algorithm. Therefore,
T
Dz Dz(x".01
G
Σ s=1
(
+
TE1 + T -m
P
R²
G
Od&G
K 2Gtr + (23) 02 02
19 -T-
+
0.
T
"
pr
pr
Dividing both sides by T, taking 1
n / and using convexity, i.c.,
(1x)
one obtains
1 T
2GR -f(x")
Gd Giri +
R
0² Od
VμT +0
(V.) pri
K
(17)
VnT
pri
We want the above expression be bounded by c. First, choose T
6GR (6GG)) /
2
and 1ı 0 (
Then, the first and the fourth terms are bounded by e/3. We want the middle terms to be bounded by e/3 as well; before doing so, we first choose the failure probability P such that the all I calls of quantum subgradient estimation in Lemma A. succeed with (overall) probability 2/3. Observe that, if we choose p = 1/(3T), then the probability that none of the T subroutines fail is:
(1-37)
(1
1 3T
T 2 3T
21
Note that the above bound holds even when each call of the quantum subgradient estimation is dependent; indeed, by union bound, at least one call of the quantum subgradient estimation fails is at most T 1/(37) I 1/3, or equivalently, the probability that none of the subroutines fails is 2 2/3.
With choice T
(GR
we have O
vpze
R
Given these choices, the precision requirement on the evaluation oracle is determined by the middle two terms in (17).
giving
0 = 0 (
We now review some common setups for the mirror descent framework that are relevant to the sequel, following a discussion from [16 Chapter 4.3]. When one takes ((x) = || on P = Rd the mirror map is strongly convex with respect to || ||2 and the associated Bregman divergence is (2(2, Ø)= _ | = = In other words, mirror descent reduces the projected subgradient method described in Theorrm B.3
For the simplex A {x Rdd entropy
EiElg I4 1), one take the mirror map be the negative
((x)
Σ
24 log I,
sEld
on P RQ. which is I-strongly convex with respect to || Il1. This setting is relevant for linear programming and zero-sum games. When X' A4. one has æ1 (1/d, .t. ///d....//d),, R² log(d) and projection is simply defined as renormalization by the normm, i.e., for any T. E P
: |
38

---

As consequence, the iterates also admit simple closed form expression:
Dt 1 9gt.
11+1 = Eield R1,se "o1."
9t E (f()). i e [d],
(18)
and the associated Bregman divergence is the Kullback-Leibler (KL) divergence
Do (x, 8)
Σ iE|d
xy log(24/74).
Mirror descent can also be applied to solve semidefinite programs by casting the problem into the form of minimizing convex function over the spectraplex
S = {X R tr(X) 1,X 0}.
Here, the relevant mirror map the negative von Neumann entropy
((X): (X log(X)),
which is -strongly convex with respect to the trace norm || || (i.e., the f--norm of the singular values). The associated Bregman divergence the quantum relative entropy
(X) S (X) == (x (log(X) log(X)),
and the Bregman projection is simply renormalization with respect to trace:
X
gd
X
tr(X)
In fine, the iterates take the form
exp(log(XX) (Xe) 119t)
X Lr (exp(log( Xx) - 119:))
(19)
For X' 3d, one can choose the starting point X I which gives R log(d).
Observe that for functions f that are 1-Lipschitz with respect to || || mirror descent with the negative log(d)
entropy mirror map enjoys
rate of convergence, whereas the projected subgradient
method in Theorem B.3 only achieves a rate O (V (V++ T Moreover, the rate convergence for the
spectraplex is the same that for the simplex.
As noted in [66 Chapter 4.2], one can re- write mirror descent iterates as
Is+1
arg arg min (2r
rEXiP
arg min ((x) - (V (z. (#.+1),z) rEXip
(20)
arg min ((x) (V4(x,) - 19.. x.)
=EX-p
arg min 7) x)) + DT(
(21)
xEX-p
Next, we will see how 20) is used to motivate Nesterov's dual averaging 63 while 21 yields the so-called mirror prex perspective 60] The former can be more efficient than the prototypical mirror descent scheme in some settings, whereas mirror prox will allow us to work with functions whose gradients are Lipschitz in arbitrary norms.
C.3 Dual averaging
Now we discuss an alternative instantiation of the mirror descent algorithm, commonly referred to as Nesterov's s dual averaging or lazy mirror descent. The basic idea is to replace the mirror descent
update (MD) with
v
V(((x)) 1J9t.
(DA)
39

---

with yt+11 E P, and is chosen such that (2())) = 0. If asked to return primal point, we project the current dual point using
[-1 (g.. x) + ((x))
2t E arg min xEXUP
(DA-Project)
==1
Theorem C.2 (Quantum Dual Averaging). Let X C R.d. be closed and bounded, convex set equipped with a given p-norm || . with 2 1. Denote K := diam(X') -upx, || vll- Suppose RRd IR is convex function that is G-Lipschitz with respect to || and attains its minimum at x² E X.P. Let & be a mirror map that is p-strongly convex on n P with respect to || I. Assume one has access 0-precise evaluation oracle for with
0 0-0 GAROK22OO0
and access to a starting point 2ι E X such that ( 0, then define R² Dø(x", ,0(xx",1), Consider the zeroth-order quantum lazy mirror descent method (DA) with 1) G / T.. that outputs the average + Et= (using Equation (DA-Project) after running T iterations, where the ğ, is an approximate element of (xz) estimated via the quantum subgradient estimation in Lemma A. at each iterate. Then, with probability at least 2/3, one can obtain an e-approximate solution with ((()))
GR 2 queries to 0-approximate binary oracle of and Ö (al GR )²) gates.
Proof. As usual, let Se be the output of the quantum subgradient algorithm for xy. Let E fl,..., T)
and define
(x(x) = (āt, x)) + (xx)
Also define
E arg min
Σ (īt, x) ((x))
arg min (v)-1(x)) xEXUP
(22)
zEAPP
Since & is j-stroogly convex, one has that v/. is also u-strongly convex for all s. Therefore,
P | x.,1
(2.(1))) (xx)) S (Vrs, (x++1) 2o+1 Iz)
/ | 1=
s
(23)
2
where the second inequality follows from the first-order optimality condition. We also have
(x++1) (x.,) = 3 ( (x.) + 17 (ā., Øs41 xz)
> n (ā,, 2x41 x..)
(24)
Combining 23
and (4). one obtains
/
2 1s+1 x= < 17 (ū,, H. - Bot1) I nllrslll ||0.41 - xzll
S (( - gll. - +G) ||0011 - xzll).
so following the derivation of 15 we have
1) (g,, F. T < nllã. ll || - 2xll
4 < "/ ((lă. - -ll. + | xxll)
2 | - xx.12
< G2
1/233
(25)
/
with E2 as in Equation
16.. Next, we claim that for any X n and any 0.
(G. xo41) + D
Σ (g. - x²) <
(26)
77
40

---

which using the definition of Bregman divergence and the fact that (2())) = 0, this amounts to
F(x) ((x1)
Σ Us. Hs x) S
(ss Ris - Is+1)
(27)
By rearranging, Equation (27 can be equivalently expressed
G. rst1) + $(x1)
(ūs, + ((x)
(28)
We prove (28) by induction on r, and hence prove Equation Note that the result trivially holds at 0 since 2ı E arg min ((x). Assuming by induction the statement holds for 1, it follows that r, we have
Σ (g.. Dot1) + ((x1) I (ār, 2r+1)
D(x1)
[g. 2s+1) +
7
Cg xr+1) (0
S (ūr: Tr+1)
11
((x)
(G..2) +
17
Thus, by induction the statement holds for all r. The second-to-last inequality follows from the induction hypothesis, and the last inequality holds by the definition of 2 (Equation (22) Hence
combining Equation 26 with Equation (25), we have for any optimizer x: and r =
T
(Jay I, - xx) G
R2
FTT J
Σ
where by definition R² = Do (x* 21). Continuing like in the proof of Theorem Equation (14
C.1 with Ej as in
T
/ T Σ xs )
- -1(x))
S T
1
Σ (f(xs) - s(x)))
KE(T]
1
$
(g., Vg - -x") + +1
T
sE[T]
R² G2
3
+
Tn
One will note that the last line is exactly Equation (15) from the proof of Theorem C. but divided by
T. Hence, the same T,, r1, and 0 from the proof Theorem C.I suffice to ensure the sub-optimality
C.4 Mirror prox
Mirror prox is variant of mirror descent that enables achieve rate 1/T for smooth functions, and is described by the following set of equations:
v v ( (zx)
V (5+1) V - (2
Zt11 E arg min Do (z,, Z+41)
and
I++1 E arg min D (I, T(41). zERпP
(MP)
Theorem C.3 (Quantum Mirror Prox). Let X Rd be closed and bounded, convex set equipped with a given p-norm || with 2 1. Denote K == diam(XX) = supz,yex | y|]- Suppose dRd R is convex function that is G-Lipschitz and L-smooth with respect || and attains
41

---

44
(
.1
P
21 : Σ [E
79
x
X
Rd
II
V 1 (ZT)
V
Figure Dual averaging.
its minimum at x² X.P. Let 4 be mirror map that is u-strongly convex on X n P with respect to ll ll. Suppose we are given point 21 E X n P and define R Dx(x", x1). Assume one has access to an A-precise hinary evaluation oracle for f. with
0=0
LO. log (Vdo. (V0OLKGG/ss)
Consider the zeroth-order quantum mirror prox (MP), with t. that outputs the running average + -ED Ret1 after iterations. Then, with probubility at leust 2/3, one can obtuin an E-upproximate solution with Ö LR²
queries to 0-approximate binary oracle of f and Ö (d + TTex))
GR 2
pe
gates, where Taea is the time carry out the operations necessary to progress to the next iterate.
Proof. Let Bn be the estimate of the gradient fyy) returned by quantum gradient estimation. Let x² X nP be minimizer. Then,
f(441) f(x*)
$ (V](2( 1), Zt+1 - x*))
(geeu1 20+1 - x²) ) + V fV((z)+)) Iati: 2841 Ze+1 -1zu11 T1+1 x²) + (g Ft+1 l++1) (0zm1 Jos: 2141 Te41)
x²)
+ ((V((E++1 Izc11 2+11 x²).
We start by bounding the first three terms in the above expression. For the first term, we have
Eq. MP
(g T++1
x²)
VV
(T( xx))
Lem. 61
VV((x;)
( I4+1 - x²)
Eq 13
Da(x", xx)) D xz+1) Da (c441,1z)).
The second term is bounded using the same steps as the first, and accounting for strong convexity of the mirror map:
(gz, Z+41
Tz+1)
MP
(
( 2411 Tt+1)
Lem.
(V((1))
V 241 - -1++1)
Do Do(
Do [(41) - Do -D(
Do (x
| 2+11 || - 2z !!?
2
42

---

For the third term, we have
(ge41 9w 2++1 2(+1)
S (9at1 2(11 - xx+1) + (92, (x()))) 214 - x(+1)
-VVf(2++1) - (f(x))) 2++1 x(-1)
[f((z++) - V f (2) |+ || rs+1ll + 119s. - Vf(xz)) + 11 - Vf(e++1)leK
< -|| - xz. 2++1 Fz+ill + 11 v](x))]] + | - V[(==+))loK
$ 2 F1+1 x L 2|- 2 + 11 V.( + 119 Vf(244))|
where we used that K is bound on the ||-|| diameter of X' and 2411 #141, EXP.
Summing the above terms and setting = & gives
LK - [D(x", 21) D(x", sx41)l+
119., vf(x+)]l+
LK 19 Vf(2+1))l..
+
Next we take the expectation of the future iterates conditioned on 24+1:
f(z+1)- - f(x) v L
DD(=* ((("",=)) 2x) (000)=="=_))==-_1_0 + LK
11 (x(e)))
+
E Blllg ((l+ii)lll
Note that given 2e+11 Ir. is uniquely determined by the strong convexity of Da. and hence by MP] so E[h(Ie, Ge.. 2 h(F,, Ix..) for any deterministic h. Continuing, we have that
B 12441 ()(=+1)) [= < 18 Eig.,, 1 -etp:lllll==1 + || (Z(+)) - Elgzys 12e+alll
S 0. 0.E 0.E111944 Bf 1++ [e44]]
+ 0. [f((++)) El [2c+0]
< 20.0.
Then we condition on xz41;
D(x, xx) E[D -E[(2,, Blllgr. [[(a))laaoo) +40
LK P
B[ f(x))
1
Similarly, have
Elllgz. - vf(x)))) [x] < 20.0.
Taking expectation everything and using the tower law, get:
LK
B[f(2++) f(x)) < 1
E(D(,, B(D(a* ([D(=*,ae1)) + 60, a.
p
Averaging over and using convexity, we have
T 21
Elf
-(x))]
E[f(z) f(x*)]
T
T
L (D(x", .11
EE(D(a* ((D(()xx))) + 60, o
LK
L LD(x 211)
LK
+60, /
HT
LRR2
LK
+ 10.
μT
p
43

---

Now, say we set T O required precision
LR
and O
We can then apply Theorem A.2 get the
0.LK
0 θ
LO K log (Vd0 (dd0.LKG(Heg (uE)))
If use our choice of T and apply Markov's inequality, then get
T
Pr
f
Σ T
)
Et+1
-(x0)
D Application to SDPs, LPs and zero-sum games
D.1 From SDP to eigenvalue optimization
Following a discussion found in [8] Chapter 11.1], we will review how the dual problem (D) can be
reformulated as an eigenvalue optimization problem. We are interested in solving the primal and dual SDPs
sup [tr(CX) tr(X) = Tpp tr (AiX) < b; for all E [m]] X z 0}, XERaxn
(P)
and
inf (B x Rm
Ty3l + +b y yo! + Σ
yiA, - C -=
(D)
ic(m)
where Ao = I, b0 Tp and || Aalloop..... Am llop: ||O|lop S 1, |10|l Tp-
We say that (X, yo. v) E nx x 18 a primal-dual feasible solution if
tr(X)= Tps Lr (A:X) < by for all i E [m],
X
yo I +
yiA - 0.
xE(m]
A primal-dual feasible solution (X, No: positive definite.
Wo.)) v) is strictly feasible when X and you + Exe(mi UsAm C
The primal problem P is strictly feasible by assumption. The dual problem D is also strictly
feasible since ||C||op I 1 and Ag I, so strong duality holds. Consequently, any primal-dam dual
optimal solution (X*, V6. y²)
P has zero duality gap:
tr(C'** Tpyn - b. y² -0
and the optimal objective value OPT tr(CX*) rp20 bt "y" is finite and attained. By Hölder's inequality, one has
OPT |[](((")))))) ||C||opl | X*
S rp.
since |CClop < L, tr = Tp and X ž O. We may thus assume without loss of generality ra for any dual optimal solution
that there exists finite value ra 2 such that (1 (v6. v²) T. x Rum
Upon normalizing (bc. b) R with respect to its -orm norm (1, 1/rp(bo. b) it is easy to see that the set of feasible solutions is subset of the spectraplex
X nxn tr(X) = 1. = 0}.
Hence, the primal and dual SDPs may be written as
(r((C)): tr (A:X) < & for all i [m]].
max E
(P)
44

---

and
min EX
Yo + 6%6 y: yo! +
v.A, - -2
(D)
KE m
The optimal objective value of the normalized pair optimal solutions to these problems are equivalent up constant scaling: if (X" Vo v²) is optimal
( is OPT/rp E [-1, 1]. and the sets of
for D then (RX*, Vo v²) is optimal for D
The Karush-Kuhn-TTurn Kuhn-TTuckr (KKT)) optimality conditions for (P (and hence, D stipulate that
a primal-dual feasible solution (X', . (h) optimal if and only if
X 7 7. X 0,
where z" = vō Eielm) Em] V/ A; C. As consequence, any optimal X and 2 are simultaneously diagonalizable. Letting Ruxn be orthonormal matrix, may write
x' PAx-P', =' P'
where Ax- and Az. diagonal matrices whose entries are the nonnegative eigenvalues of X* and Z", respectively. Since X * (as tr(X*) * 0) and Ax+Az- = 0, it follows
A A 14-4-c) -c)
Amin (Az.) = Amin I
Σ y C = y4 + Amia *E[m]
Σ iE|m
Rearranging terms, we obtain
vo
Amain
Σ v - Amax C Σ Vc Ai
=Amux
(29)
(E(m)
iE[m]
and thus solving equivalent to solving minyeRy, ((V), where
f(y) Amax (C- Σ y: + ET
(SDP-eig)
(E(m]
Note that this reduction is valid for any nontrivial SDP with bounded feasible set 42 linear term 6 may also be incorporated into the Xmax(.) term by replacing each A, with A, b see 770 Section 6.3].
81 The
Problem SDP-eegg is nonsmooth convex optimization problem and is well-studied in the literature, see e.g., [52] and the references therein. Before proceeding further, we recite a few important facts to keep the paper self-contained.
First, note that since bo/rp 1, by 29 one has
f(1)) Amax C-
Σ mE(m)
oe A
+ TT
TT
(r,yO bTy²" y²)
Tp
min
Tp300 bT y = OPT OPT/rg /Tp
Tp (uo.)))RxRgoooe Evetm nA Cra}
Since dual optimal solutions (yń y² solution to (SDP-cig), it follows that SDP has global minimizer in the dilated m-dimensional simplex
D satisfy (36 - S rd. and y is also an optimal
A
R
Σ Σn=
(E(m)
This motivates us solve (SDP-eig) with mirror descent using the simplex setup described earlier in Section
The complexity of our algorithm will scale with the Lipschitz constant of the objective in (SDP-eig)
The upshot of using mirror descent is that we can choose to work with the norm in which / is well-behaved.
45

---

Lemma D.1. The objective function f R + R in SDP-cig is 2 2-Lipschitz on R with respect to the e n-norm.
Proof. The idea is to consider the two terms defining f separately, and sum their Lipschitz constants. By Hölder's inequality, the Lipschitz constant of the linear term b% is simply [|b]| S 1. For the other term, let M(y) C Eielm) Br Ai, which Hermitian matrix for all y E R Thus, for any (y, 8) E Rm R one has
Ammax (mnax((M)) (M(y)) Amax (M (M(D) & (I M(o)
Σ sc/m]
1t Tsl
|| AAlllop
max {IlAi|lop) 11 Øl sc|m]
where the first inequality is a consequence of Weyl's Perturbation Theorem for Hermitiain matrices. Since IA Il S 1, we have that (M) is 1-Lipschitz with respect to the é norm.
The proof is complete upon summing the Lipschitz constants of Amax (M)x))(y)) and 8 y.
We are now in a position to establish the (black-box) complexity of determining an s-optimal solution to the dual SDP ( using quantum mirror descent method.
Theorem D.1. Let f R. - R be the objective function in eiDP-eigh and let Tp. 2 1 be such that an optimal solution to the SDP (P-(D) satisfies tr(X*) = p and 1ly 1| S Td. Suppose that one has access to an O-precise binary evaluation oracle to f, with 0 = O /rpram4..) 4.5). Then, with probability at least 2/3, the quantum mirror descent method described in Theorem C.I solvvee (P-(D
to additive error E (0, 1) using at most Ö ( (m=e=)) queries to a binary evaluation oracle for f and mm ("ara)²) gates.
The output is a vector ÿ 1850 such that
(yō 1/*)
-Aamin
Σ (ra. 0,) C - iE(mJ
.r
E R
m
is feasible solution to D that satisfies
boyo
+ b 8" < OPT e
In other words, (vō 4²) E R Rm is e-precise solution to D
Proof. Let (A1....,, Am, b, C)) be the input data defining D). and denote the optimal objective value by OPT. We first normalize i - b/r, and re-scale the input space + y/ra- With these modifications, the result in Lemma certifiess that f is 2-Lipschitz over 13th with respect to the fi-norm, and the optimal objective value of the normalized problem is OPT/rpra- Accordingly, we seek to approximate the optimal objective value of (P) to additive error E E (0, 1), we must solve
1 Fd
min f(0) Amax SEA"
Σ sE[m]
i.Ai
+ TT
to precision g' = E//prr
The basic idea to utilize the simplex setup for mirror descent, taking the negative entropy function as the mirror map +(Ø) = Ete m) Ji log Di. and choosing the starting point = m m $1, E A 20- Recalling that & is 1-strongly convex on A and that our choice of starting point ensures R (l)g(m)), the result Theorem C.I (taking determine 7 E A satisfying
since || I|-- = (loo) establishes that one can
f(5)) <
OPT
E
rara f(/) < OPT +
(30)
T rd
rprd
46

---

using at most
2 - - ("era)a)
-(p2r))
-
queries to the O-precise binary evaluation oracle for f and (m Tnex))
("
gates, where
Trex represents the cost to proceed to the next iterate.
To make the gate complexity explicit, note that Ô (m) work is required to proceed the next iterate. After estimating 9t E R at iterate t, we compute the entries of De+1 E A according to (18). setting
Dr 19...
Ie+
Eie(m)
which clearly requires (m) operations. One can also reduce storage requirements by recursively maintaining the running average as the convex combination:
Σ +Ei+1
t
0.
V1 +
16+1-
1+
Finally, show that output 5* encodes e-precise solution to the dual SDP y" = rağ" E Rgo and set
D
Define
y0 = Aminn
Σ v - sE/ml
cC
E R.
Then, 36 + Eieim Vt - = 0 (in fact, Amin (y6
+ Eig(m)) -) = 0), so (yō- y*) E
R x 20 a feasible solution to DD. Applying (30), one can also observe
1 c-
Po +b= y² =rp (36 6T v²) rpra
Amax
U.
+ +b
ryra f(ā")
Td
(E(m)
OPT +
Thus far we have established the query complexity of our algorithm applied to solving SDPs. However, these queries are to a black-box evaluation oracle for the objective function f. In order to make our results comparable to other SDP solvers found in the literature, we need to open the black-box and establish the cost of each of these evaluations terms of queries to the input data defining (P ( This is what we do next.
D.2 Complexity
D.2.1
Semidefinite programs
Theorem D.2 (SDP Solver). Suppose that the SDP problem data (A1...., Ams C) is stored in sparse-ace access data structure. Choose E (0,1). Then, with probability 2/3, the quantum mirror descent method described in Theorem C.1 ssolvss P additive error E using
O (mmss + n²) (rpra/e)² polylog (m, n, (r,raae))))
queries and gates. The output is E-precise solution (vã v²) R x P% to the dual SDP
Proof. We first discuss the cost of implementing the evaluation oracle.
To compute the inner product b we need O(m log(1/0)) queries to the elements of b. To see this, note that Om log(1 (1g)) queries are necessary implement the unitary
Up 1z) + 1a 6)
47

---

With access to Us. one can compute the inner product
(0) 00) - b) lB:)) [0)
(m)) gates bb) lus) 1 (0 1 (ti) (b
Since Ug- = Ub. the above circuit requires 2 applications of Ub. and hence, O (m log(1/8)) queries to the elements of in total. Note that the total number of gates also (m 10)(1
Implementing the matrix M = C EiE Vi Ai from y requires (mns) gates, and from here we can perform an eigendecomposition on M to find the top eigenvalue using O' log(1/0) gates. Hence, the high-precision regime, we can implement an 0-precise evaluation oracle for using
( + n²) log(1/0))
queries and gates.
Setting 0 = Ō(= am and applying Theorem D.1 the total number of queries can be bounded
δ (mms n²)) ("x"ae) O
(ooss-n)). n²) -
("ord) polylog (,, n, Tpld ))
and the number of gates is
o (mns + + + m))
PoPd ) =0
+ n²) -0
(Tp'd'
polylog m, n. rp'd
The theorem statement is obtained upon noting that, given J", one can compute
Σ (r - c) rr. E E x R
(16, y*)
Amii
iefmj
using at most O (mms + n()) operations.
D.2.2 Linear programs
Recall that LPs are a special case of SDPs in which each of the input matrices A Am. C is diagonal matrix. In this case, the dual slack matrix Z is also diagonal matrix. Thus for LPs, may write the objective function in (SDP-eig) as
f(y) Amax (c-
(C- ycA (E(m)
+ TT y
max jE(n)
(c-
C
yiAi
8T y.
iE(m)
53
One can leverage the simplified structure of the objective for L.ss to obtain an attractive running time, show next.
Theorem D.3 (LP solver). Let (A, b)c) be the input data for an LP with m constraints and n variables. Suppose that the columns of and e are stored in a quantum read-only memory. Then, with probability 2/3, the quantum mirror descent method described in Theorem C.1 solves the primal- dual pair LL f additive error E using
(mva (ryra/e)² polylog (m, n, TorafE)
queries and gates. The output is an é-precise solution to the dual LP problem.
Proof. As discussed earlier in the proof of Theorem D.2 can compute the linear term 6 y using (m) gates.
For the other term, recall that in LP we need evaluate
{c- Σ A:
Σ A;
-C
max
min jE(m)
[E(n
[E|m]
iE|m]
jí
48

---

To do so, we proceed as follows. Letting j E [nx], we implement UMs, which acts as
(b) (b) 0) (0) (0) (()) QROM queries
(m)) gates
li} ()) |Az) lcz) (0)
4 bb) (b) (A,, ez) (oz) 10),
The above requires (m) gates. With this construction, we can apply generalized minimum finding 776 Theorem 49] to compute smallest entry with O(vn) applications of Uas and its inverse.
From here, setting 0 O / and applying Theorem D.1
did in the proof of
Theorem D.2 suffices to bound the query and gate complexity of determining V' using the mirror descent method. To complete the proof note that can construct an s-precise solution (yo v²) x I2 to the dual LP from y E Rgo with cost Om))n)) Clearly, computing y" Fa y takes (m) operations, and one can compute
Σ 1/5 A
-
36
min jE(m]
sE/m]
with cost Omm)n), using the same strategy we employed to evaluate f.
D.2.3 Zero-sum games
Zero-sum games are matrix games in which each player has a finite number of pure strategies. These problems are well-studied in the game theory literature, and a standard setup concerns two players Alice and Bob whose action spaces are [m]] and [n] respectively. Payoffs from the game are encoded in the entries of a matrix A E [-1, 1..1 1| If Alice plays action i E [m] and Bob plays j E [n], then Alice obtains payoff Aıj. while Bob receives payoff of -Ay. Each player aims to maximize their expected payoff through randomized strategies (z, v) A x A", giving rise to the minimax optimization problem:
min max y Az. #EA" yEA"
(ZSG)
Saddle points of ZSG are called mixed Nash equilibria, which always exist for zero-sum games due to von Neumann's 's minimax theorem [67].
Zero-sum games can be reformulated as LPs and vise-versa. The general idea follows from the fact that a linear function over the simplex attains its maximum on a vertex, i.e.,
min max y Ax min max c Axx A YEA"
xEA" sE|m]
where e, E RT denotes the i-th unit vector in the standard orthonormal basis for R". Therefore, upon introducing one additional variable can equivalently solve the LP:
min -|-1I
{Ap Ax S 1p1n).
where 1, E IR" is the all-ones vector of length n. The dual is similarly formulated as
(Na: A Aalm)
max (1.)x)
Note that the optimal objective values of these problems are equivalent under strong duality, and so we call X the value of the game. We also have rp, ra 2. These observations motivate the following corollary of Theorem D.3
Corollary D.I (Zero-sum games). Let A E [-1, mmmx be the payolf matrix of a zero-sum game. Suppose that the columns A and stored in quantum read-only memory. Choose E (0. 1).
Then, with probability 2/3, the quantum mirror descent method described in Theorem C.I solves ZSG additive error e using
mm/n 22
O
polylog (m, n, 1/8)
queries and gates.
49


Reviews:
[{"review_id": "OrUHEzGwLY", "reviewer": "Reviewer_Xxvf", "summary": "This paper presents a unified algorithmic framework for zeroth-order convex optimization with certain quantum oracles to achieve dimension-independent optimization errors. By assuming the errors in the function values of the quantum oracle to be vanishingly small, the proposed achieved rate is comparable to the errors achievable under the classical first-order-oracle setting under stochastic unit-variance errors. The key technical idea in the proposed approach is to leverage a gradient estimator analyzed in [74] (presented as in Lemma 2.1) to adapt first order algorithms to the quantum zeroth order setting. This approach is extended beyond zeroth order convex and smooth optimization, and achievability analysis was provided form SDP, LP, and zero-sum games.", "questions": "While the topic investigated in the manuscript is clearly of significance and there might be technical merits of the proposed results. As mentioned in the earlier discussion on the weakness of the submitted draft, we recommend the authors to provide following discussions for the manuscript to be considered publishable. \n\n1. The achieved rates of the quantum algorithm must be compared to the ones achieved by the best known classical algorithms under the same vanishing error condition, i.e., the noise variance decays with the same polynomial dependency of epsilon and d. \n\n2. The comparison between classical and quantum algorithms needs to be based on the above fair comparison, and any claims in the abstract needs to be justified in the manuscript. \n\n3. We recommend the authors to clearly mention in the abstract that the quantum oracle considered in this work under the pure state assumption is known to be strictly easier than its classical counterpart. There has been abundant works in recent years that demonstrated this distinction, which should also be mentioned.\n\n4. Section 2 mentioned that one main benefit of first-order methods vs newton's approach is the convergence of global optimum irrespective of the starting point (line 103-107 on page 3), however we would point out that this global convergence is achievable with a modified newton's method with second-order smoothness condition.", "limitations": "yes", "rating": 2, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:  Zeroth-order optimization is important in settings where gradients are unavailable or expensive to compute, and understanding potential speedup of quantum algorithms is an important topic that could have significant impact in Neurips society. Any significant result in this direction on improving the best known results and approaches could provide valuable theoretical insights. In terms of clarity, the technical sessions of this paper are well-written and accessible. The assumptions are clearly stated and proved, and the analysis is carefully structured. \n\n Weaknesses: A main issue of the submitted manuscript is the mismatch between the noise amplitude between the proposed quantum framework and the classical oracles, which results in an unfair advantage of the proposed scheme on achieving an optimization error that could have been achieved and outperformed by the classical oracles under the same noise condition, even under zeroth order access. \n\nFor instance, definition 1 assumes that the quantum oracle has a zeroth order measurement error of theta which is conventionally presumed to be constant. But through a careful investigation, the achievability results presented in this work in fact requires the measurement error theta to be polynomially smaller than the targeting estimation error epsilon (e.g., see the 2.1). Knowing that under such vanishing error condition, the classical zeroth order oracle can in fact achieve rates that are orderwise better than the rates in e.g. Table 1 that was used in the comparison. Particularly, the bound on the gradient estimation error this manuscript relies on (Lemma 2.1) is weaker than the guarantees of the classical zeroth order two point gradient estimator under the same regime of theta used in the main theorems. Therefore, if we apply the same analysis under the same error conditions, the rates achievable for classical algorithms would outperform the rates of quantum algorithms presented in this work, which is the opposite of what is claimed in the abstract. \n\nTwo other important but relatively minor issues: 1. the abstract claims an exponential separation between quantum and classical optimization but this is not clearly elaborated in the main text. 2. the quantum oracle considered in this work assumes a pure state access which is well known to be algorithmically easier than its classical counterpart. Therefore, it is not a generalization of the classical access. However, this distinction is not made clear in the abstract, which could potentially mislead the readers into thinking the proposed result is a quantum speedup.", "was_revised": true, "final_justification": "After the discussion period, our main concerns remain, as elaborated in our responses to the authors. Especially, while we appreciate the authors' contribution, we recommend an accurate presentation on the contribution and scope of the paper, especially on the quantum vs classical comparison.", "rebuttal": "Dear reviewer Xxvf,\n\nThank you for your detailed comments and feedback. We appreciate your positive comments regarding the significance of the results, and the clarity of the presentation. You raise important technical points in your review, however, we feel that there is some misunderstanding regarding the most important ones. Below, we address each of your questions and concerns in detail.\n\n> Definition 1 assumes that the quantum oracle has a zeroth order measurement error of theta which is conventionally presumed to be constant. But through a careful investigation, the achievability results presented in this work in fact requires the measurement error theta to be polynomially smaller than the targeting estimation error epsilon (e.g., see Thm 2.1). Knowing that under such vanishing error condition, the classical zeroth order oracle can in fact achieve rates that are orderwise better than the rates in e.g. Table 1 that was used in the comparison. \n\nThank you for this thoughtful comment. It is indeed important to compare the classical and quantum settings under similar noise assumptions. However, as we clarify below, the speedup demonstrated in our paper persists under our noise assumptions.\n- Firstly, we note that the noise $\\theta$ in the oracle cannot be chosen to be a constant independent of $d,\\epsilon$ even in the classical case, since if the noise is asymptotically polynomially larger than $\\max\\left(\\frac{\\epsilon^2}{d},\\frac{\\epsilon}{d}\\right)$, no classical algorithm can output an $\\epsilon$-approximate minimum using $\\mathrm{poly}(d,\\epsilon)$ queries (see Theorem~3.1 in [RL16]). Therefore any polynomial query classical algorithms also tolerate noise that is falling polynomially with the target error and the dimension.\n- Furthermore, the last column in Table 1, we state the classical **first-order** query complexity, not zeroth-order. If we instead choose to write classical zeroth-order, every row in the classical column is multiplied by $d$; importantly, this holds even when the function evaluation oracle has perfect precision (i.e., completely noiseless) [JNR12]. Thus the quantum algorithm exhibits an exponential speedup in terms of $d$ **even if the classical oracles are completely noiseless**, and the following statement is not accurate.\n> Knowing that under such vanishing error condition, the classical zeroth order oracle can in fact achieve rates that are orderwise better than the rates in e.g. Table 1 that was used in the comparison. \n\nFinally, we are aware that the classical methods can be accelerated by using Nesterov's accelerated gradient methods, for instance in the smooth setting. However, this is an orthogonal discussion to our claim of exponential speedup in terms of the dimension $d$. In principle, nothing prevents us from considering accelerated zeroth-order quantum gradient methods. Indeed, as we reflected in our response to reviewer fZUu02, analyzing Nesterov's accelerated gradient method within our framework constitutes a natural future direction. \n\n> Particularly, the bound on the gradient estimation error this manuscript relies on (Lemma 2.1) is weaker than the guarantees of the classical zeroth order two point gradient estimator under the same regime of theta used in the main theorems. Therefore, if we apply the same analysis under the same error conditions, the rates achievable for classical algorithms would outperform the rates of quantum algorithms presented in this work, which is the opposite of what is claimed in the abstract.\n\nThank you for this thoughtful comment. By the \"classical two point gradient estimator,\" we believe you are referring to the work by [DJW15] (otherwise, please let us know which reference you have in mind). Their **lower bound** result clearly exhibits dimension dependence: at least $\\Omega(d/\\varepsilon^2)$ observations are necessary using two function evaluations, and at least $\\Omega(d^2/\\varepsilon^2)$ using a single function evaluation. Note that these results are in the **noiseless** function evaluation setting. \nTo sum up, we are unsure how to interpret your comment \"classical algorithms would outperform the rates of quantum algorithms presented in this work.\" We note that classically, even for (strongly convex) quadratics, a tight bound of $\\Theta (d^2/ T)$ exists [Sha13]. Based on these observations, the claim of speedup in the abstract is indeed accurate.\n\n> The abstract claims an exponential separation between quantum and classical optimization but this is not clearly elaborated in the main text.\n\nWe appreciate the opportunity to clarify this point. As we mention in the main text (e.g., line 74), we achieve exponential separations in terms of the dimension $d$ for convex optimization using zeroth-order oracle. This is evident in Table 1, where we state the classical first-order query complexity to highlight that they match our results on zeroth-order quantum gradient methods. \nIn future versions, we will make an effort to highlight the separation even more clearly.\nWe can change the last column of Table 1 to classical (0th order) query complexity, in which case every row is multiplied by the dimension $d$, to present the exponential separation in a more explicit way. \n\n> The quantum oracle considered in this work assumes a pure state access which is well known to be algorithmically easier than its classical counterpart. Therefore, it is not a generalization of the classical access. However, this distinction is not made clear in the abstract, which could potentially mislead the readers into thinking the proposed result is a quantum speedup.\n\nWe appreciate this comment and agree that it is very important to be careful about the nature of quantum oracle access that is assumed. However, we note that the oracle access assumed in our manuscript does not return the function value encoded in the amplitudes of a pure state (which is indeed incomparable to a standard oracle), but rather simply allows the classical oracle to be queried in superposition. Given a classical circuit implementing the classical oracle, we can construct a quantum circuit for our oracle by replacing each gate with a reversible equivalent using Toffoli gates. Using such a construction, the gate complexity of the quantum oracle is within a constant factor of that of the classical oracle. A speedup that assumes this sort of oracle access is the standard assumption for almost all quantum speedups in query complexity, including well-known algorithms such as Simon's algorithm [Sim97], and most previous works on quantum speedups for convex optimization [CCLW20, vAGdW20, GKNS21, GAW19, Jor05].\nTherefore, the algorithms presented in this work **do in fact constitute a quantum query speedup in the usual sense**.\n\n\n> Section 2 mentioned that one main benefit of first-order methods vs newton's approach is the convergence of global optimum irrespective of the starting point (line 103-107 on page 3), however we would point out that this global convergence is achievable with a modified newton's method with second-order smoothness condition.\n\nThank you for the suggestion. We will reflect this in the text in future versions.\n\nWe thank the reviewer for very specific technical comments and giving us the opportunity to clarify some important points. Please do not hesitate to ask follow up questions during the discussion period, and if your concerns are adequately addressed, we kindly request you to reflect it in the score. Thank you again for your time and effort in reviewing our paper.\n\n[JNR12] K. G. Jamieson, R. D. Nowak, B. Recht, 2012 \"Query Complexity of Derivative-Free Optimization\".\n\n[DJW15] J. C. Duchi, M. I. Jordan, M. J. Wainwright, A. Wibisono, 2015 \"Optimal rates for zero-order convex optimization: the power of two function evaluations\".\n\n[Sha13] O. Shamir, 2013 \"On the Complexity of Bandit and Derivative-Free Stochastic Convex Optimization\".\n\n[RL16] A. Risteski, Y. Li, 2016 \"Algorithms and matching lower bounds for approximately-convex optimization.\" \n\n[CCLW20] S. Chakrabarti, A. M. Childs, T. Li, X. Wu, 2020 \"Quantum algorithms and lower bounds for convex optimization.\"\n\n[vAGdW20] J. van Apeldoorn, A. Gilyén, S. Gribling, R. de Wolf, 2020 \"Convex optimization using quantum oracles.\"\n\n[GKNS21] A. Garg, R. Kothari, P. Netrapalli, S. Sherif, 2021 \"No Quantum Speedup over Gradient Descent for Non-Smooth Convex Optimization.\"\n\n[GAW19] A. Gilyén, S. Arunachalam, N. Wiebe, 2019 \"Optimizing quantum optimization algorithms via faster quantum gradient computation.\"\n\n[Jor05] S. P. Jordan, 2005 \"Fast quantum algorithm for numerical gradient estimation.\"\n\n[Sim97] D. R. Simon, 1997 \"On the Power of Quantum Computation.\""}, {"review_id": "zOBAaB6ke7", "reviewer": "Reviewer_fZUu", "summary": "This paper presents new quantum algorithms for zeroth-order convex optimization—that is, optimization using only noisy function value queries, without access to gradients. The main contributions are:\n\nExponential Quantum Speedup: The authors show that quantum algorithms can match the first-order query complexities of classical gradient-based methods, even though they only use zeroth-order (function value) oracles. This results in an exponential speedup in the dimension d compared to classical zeroth-order methods, whose complexity is typically linear in d\n\nDimension-Independent Query Complexity: The proposed quantum algorithms achieve dimension-independent query complexities (up to polylogarithmic factors) for both smooth and nonsmooth convex optimization problems, a significant improvement over classical zeroth-order approaches.\n\nGeneralization to Non-Euclidean Settings: By leveraging quantum (sub)gradient estimation, the authors extend their methods to non-Euclidean spaces using quantum mirror descent and its variants (including dual averaging and mirror prox), broadening the applicability of their techniques.\n\nApplications to White-box Problems: The framework is applied to important structured optimization problems such as semidefinite programming (SDP), linear programming (LP), and zero-sum games. For these, the quantum algorithms achieve better or comparable complexities to the best known classical and quantum methods in certain parameter regimes.\n\nTechnical Advances: The paper develops robust quantum subgradient and gradient estimation procedures that work with noisy oracles, and provides convergence guarantees for quantum versions of projected subgradient, mirror descent, and mirror prox methods\n\nApplications and Speedups:\n\nSDP and LP: The quantum mirror descent framework yields SDP and LP solvers with gate complexities that provide quadratic speedups in certain regimes over classical matrix multiplicative weights methods and some previous quantum approaches.\n\nZero-sum Games: The algorithm achieves improved complexity for finding Nash equilibria in zero-sum games, outperforming prior classical and quantum algorithms in some parameter ranges", "questions": "Stated above.", "limitations": "None.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Overall, i think this is a nice paper  making a good contribution to Quantum optimization. \n\nThe results are fairly theoretical (which i think is OK) and assume access to sufficiently precise quantum oracles; practical implementation awaits advances in quantum hardware. I guess it'd be nice if the authors discuss what happens if the oracles are a bit noisy.\n\nThe quantum algorithms match the rates of standard (non-accelerated) classical first-order methods, but do not (yet) achieve the accelerated rates of Nesterov-type methods. Again, it'd be good to have a discussion on this.\n\nThe precision requirements for the oracles are stringent; relaxing these is an open direction for future research", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer fZUu,\n\nThank you for your constructive comments and feedback. We are glad that you find our work to be a good contribution to the field of quantum optimization. Below, we address your primary concerns and questions in detail.\n\n> What happens if the oracles are a bit noisy?\n\nWe already consider noisy oracles, as shown in Definition 1 and the noise tolerance of each algorithm is reflected in the corresponding theorem. If you mean what happens if oracles are noisier than what our theorems require, then in general the final sub-optimality guarantee will not hold.\n\nWe note that this is also the situation for classical algorithms, and each gradient method has a maximum noise tolerance (which is at most $\\max\\left(\\frac{\\epsilon^2}{d},\\frac{\\epsilon}{d}\\right)$ for any algorithm with polynomially many queries [RL16]. We also note that the classical algorithms with the highest robustness are generally slower than gradient methods. The situation is the same for quantum algorithms, and while we provide noise thresholds for all our algorithms for reasons of concreteness, developing the most robust algorithm is a somewhat orthogonal endeavor.\n\nFinally, we emphasize that in the classical setting, even with infinitely-accurate (i.e., noiseless) zeroth-order oracles, the query complexity remains linear in $d$ [JNR12], and therefore our methods listed in Table 1 exhibit an exponential query speedup in the whole noise regime for which the guarantees hold.\n\n> Is Nesterov-type acceleration possible?\n\nThank you for the thoughtful comment. Indeed, Nesterov-type acceleration should be possible. The complication, though, is the well-known error accumulation on using erroneous oracle, for the accelerated methods [DGN14]. As a result, we expect the noise tolerance $\\theta$ might be more stringent than the non-accelerated results we provided in the current work. Looking into the accelerated scenario definitely is an interesting future step.\n\n> Can you relax the precision requirements?\n\nThe main message we wanted to convey in this work is that zeroth-order quantum gradient methods can match the classical first-order query complexity of gradient descent-type of algorithms. That being said, it is possible that the precision requirement can be relaxed to a certain degree, e.g., improving polynomial dependence on the $\\varepsilon$ and $d$ for $\\theta$ required in Theorem 2.1, for instance. This may necessitate further development in the underlying quantum gradient and subgradient computation subroutines.\n\n\nThank you again for your time and efforts in reviewing our paper. We hope the above clarification addresses any outstanding questions or concerns. Please do not hesitate to ask follow up questions during the discussion period. \n\n[JNR12] K. G. Jamieson, R. D. Nowak, B. Recht, 2012 \"Query Complexity of Derivative-Free Optimization\".\n\n[RL16] A. Risteski, Y. Li, 2016 \"Algorithms and matching lower bounds for approximately-convex optimization.\" \n\n[DGN14] O. Devolder, Y. Nesterov, 2014 \"First-order methods of smooth convex optimization with inexact oracle.\""}, {"review_id": "sDxohBC463", "reviewer": "Reviewer_eitt", "summary": "This paper shows that quantum algorithms can solve zeroth-order convex optimization problems, using only noisy function evaluations, with query complexity matching that of classical first-order methods. By combining quantum gradient estimation with standard optimization routines like projected subgradient and mirror descent, the authors achieve exponential improvements in dimension over classical zeroth-order methods. They extend the framework to smooth functions, non-Euclidean settings, and structured problems like SDPs, LPs, and zero-sum games, demonstrating improved complexities in several regimes.", "questions": "In view of the \"Weaknesses\" section:\n\n* Are there genuinely new technical challenges in adapting classical convergence guarantees to the quantum zeroth-order setting, beyond tracking bias and variance from oracle errors?\n* Does any part of the analysis fundamentally rely on quantum-specific insights, or could the results be derived by combining known quantum gradient estimation techniques with standard optimization proofs?\n\nIt would be important for the authors to clarify this, as it directly impacts the novelty and technical contribution of the work..", "limitations": "No limitations", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "* Strengths:\n    * The key positive result is that zeroth-order quantum methods match the rates of classical first-order methods, exhibiting an exponential separation from classical zeroth-order optimization.\n    * The paper offers a unified and complete treatment across various settings—nonsmooth and smooth objectives, Euclidean and non-Euclidean geometries—using tools like mirror descent, dual averaging, and mirror prox.\n    * The framework is broadly applicable and extends to important structured problems such as semidefinite programming, linear programming, and zero-sum games.\n    * The paper is well written. It is mathematically precise, and the results are well contextualized within the broader literature on quantum optimization.\n* Weakness\n    * The core technical contribution seems limited to plugging known quantum gradient (or subgradient) estimators into standard first-order convex optimization routines. Once an oracle with sufficiently controlled bias and variance is assumed (or constructed), the convergence analyses for mirror descent, projected subgradient, or gradient descent follow in a largely black-box, modular fashion. The analysis mirrors classical proofs, accounting for estimation error.", "was_revised": true, "final_justification": "In response to the reviewer comments, the authors have clarified their contribution.", "rebuttal": "Thank you for your constructive comments and feedback. We are glad that you find our work to exhibit key positive results in a unified and complete manner across various settings. Below, we address your concerns in detail.\n\n\n> Are there genuinely new technical challenges in adapting classical convergence guarantees to the quantum zeroth-order setting, beyond tracking bias and variance from oracle errors?\n\nThank you for the question. While the framework of our analysis appears to follow classical convergence analysis closely, there are some subtle but fundamental challenges posed by the guarantees of quantum gradient estimators. The primary difference from typical classical gradient estimators is that the quantum gradient estimators exhibit non-zero bias, resulting from the phase estimation, a subroutine used in the original quantum gradient estimation [Jor05]. Most classical convergence proofs are specific to unbiased estimators and thus extending them to handle bias is a non-trivial challenge. These extensions are more technically complicated in the case of arbitrary normed spaces. In fact, the gradient estimation algorithms of [Jor05, GAW19] would not in fact be sufficient for most of our results and we must use instead a modified version of the improved gradient estimation from [vACGN23], which utilizes suppressed-bias phase estimation, such that we can also control the variance (c.f., Corollary A.1 and Theorem A.2). As an illustration of this challenge, a recent paper [CSW25] (Theorem 47) considers the optimization of a smooth and strongly convex function with condition number $\\kappa$, and achieves an oracle complexity of $(1/\\varepsilon)^\\kappa$, exactly due to the complication of existing bias in quantum gradient estimation. \n\nThe quantum subgradient methods pose similar challenges, with the estimate obeying the subgradient guarantee at a point that is shifted from the input point, again with a biased error term. \n\nWe note that quantum gradient estimation algorithms have been studied for nearly two decades at this point, and quantum algorithms for zeroth-order convex optimization (in the regime $d \\ll 1/\\epsilon$) are also nearly 5 years old. However, despite the naturalness of the question, an exponential speedup in $d$ for the regime $1/\\epsilon \\ll d$ has not been demonstrated. We believe this gap in the literature, which is first addressed by this work, illustrates the non-triviality of the technical challenge.\n\n> Does any part of the analysis fundamentally rely on quantum-specific insights, or could the results be derived by combining known quantum gradient estimation techniques with standard optimization proofs?\n\n\n\nThank you for the question. If by ``quantum-specific insights\", you mean an entirely new quantum subroutine that directly uses low level tools such as phase estimation or singular value transforms, then the answer is no. We use a minor modification of suppressed bias gradient estimation from [vACGN23] and the quantum subgradient methods from [CCLW20,vAGGdW20] as our building blocks. However, as discussed in the section above, the optimization proofs are not standard since care needs to be taken to incorporate the quantum estimators into the analysis. \n\nWe note that this style of analysis, where known quantum subroutines must be carefully integrated into classical frameworks, is common in the field of quantum machine learning, including several recent papers at NeurIPS/ICML.\n\nFinally, we note that our whitebox results present a new paradigm for quantum algorithms for SDPs/LPs whose performance dominates all known algorithms in some parameter regimes. The fundamental building block for these results are the gradient methods in normed spaces, which is constructed for the first time in this work.\n\n\n\n\nWe thank the reviewer for pushing us to be more precise about the technical significance of our contribution, and we hope this clarification addresses the concern raised. If so, we kindly request the reviewer to reflect it in the score. Thank you again for your time and efforts in reviewing our paper.\n\n[Jor05] S. P. Jordan, 2005 \"Fast quantum algorithm for numerical gradient estimation.\"\n\n[GAW19] A. Gilyén, S. Arunachalam, N. Wiebe, 2019 \"Optimizing quantum optimization algorithms via faster quantum gradient computation.\"\n\n[vACGN23] J. van Apeldoorn, A. Cornelissen, A. Gilyén, G. Nannicini, 2023 \"Quantum tomography using state-preparation unitaries.\"\n\n[CSW25] A. B. Catli, S. Simon, N. Wiebe, 2025 \"Exponentially better bounds for quantum optimization via dynamical simulation.\"\n\n[CCLW20] S. Chakrabarti, A. M. Childs, T. Li, X. Wu, 2020 \"Quantum algorithms and lower bounds for convex optimization.\"\n\n[vAGdW20] J. van Apeldoorn, A. Gilyén, S. Gribling, R. de Wolf, 2020 \"Convex optimization using quantum oracles.\""}, {"review_id": "3LeYzKqdMx", "reviewer": "Reviewer_7YDD", "summary": "This paper studies quantum algorithms for zeroth-order convex optimization using quantum gradient estimation with noisy function evaluation oracles and shows that by relying solely on noisy function value queries, the quantum algorithms match the first-order query complexities of classical gradient descent methods. The framework are then generalized to non-Euclidean settings via quantum mirror descent and its variants. Leveraging connections between SDP and eigenvalue optimization, the framework is applied to solve white-box problems, including SDPs, LPs, and zero-sum games, and achieves a better time complexity on the dependences of $r_d, r_p$ and $\\varepsilon$.  For smooth objectives with Lipschitz gradients, quantum gradient descent and mirror prox achieve convergence rates matching classical first-order methods. A fast query complexity is also proven under the PL condition assumption.", "questions": "Suggestions:\n1. In the white-box section, the authors' algorithms achieve improvements in terms of $r_d$, $r_p$, and precision $\\varepsilon$, but exhibit slightly worse dimensionality dependence compared to other algorithms. Though such phenomena are common in recent works of quantum optimization, the authors are suggested to briefly explain the source of the additional dimensionality dependence.\n\n2. In Theorem D.3 and Corollary D.1, the authors are advised to explicitly specify the form of the error rather than solely referring to it as \"additive error\".\n\n3. The caption of the result table is suggested to include the meaning of symbols and explicitly highlight which factors demonstrate quantum advantage.\n\n4. The statement about dimension independence may not be entirely rigorous. Under the error function value black-box setting, the quantum gradient estimation method still exhibits a logarithmic dependence on the dimension in its query complexity. Based on my knowledge, the quantum community only proved that in the error-free black-box setting, the bounded error quantum gradient estimation can achieve a query complexity of complete dimension independence.\n\n5. If I understand right, the \"domain\" in Table 1 refers to a normed space, not the feasible domain. The authors are suggested to add a brief clarification to avoid potential confusion.\n\nQuestions:\n1. Regarding SDP problems, the quantum algorithms in this work output a dual solution under additive error, is it possible to derive error bounds for primal solutions? \n\n2. Selecting an appropriate mirror map is one of the crucial steps in implementing quantum mirror descent. Note that the authors provided several examples (e.g., for feasible domains like the probability simplex and Schatten-1 norm). For other feasible domains, are there general methodologies for choosing the mirror map and the Bregman divergence?\n\n3. Regarding the result in Table 1, is there any classical or quantum lower bound?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "In previous work, quantum gradient estimation methods have demonstrated the capability for zeroth-order black-box approaches to match the performance of classical first-order black-box methods. However, when applied to concrete optimization problems, quantum advantages may fail to materialize—particularly in the presence of erroneous black-box settings. Therefore, rigorous analysis and ensuring correct parameter choices are both challenging and significant.\n\nThis work provides a rigorous proof that quantum gradient estimation with erroneous black-boxes, when employed as a gradient estimator subroutine in projected gradient descent and mirror descent, maintains the original convergence rate. This establishes a solid theoretical foundation for broader applications. Furthermore, the authors demonstrate quantum advantages in applications to SDPs, LPs, and zero-sum games, achieving superior complexity compared to prior approaches relying on the HHL algorithmic family. Consequently, this work holds substantial theoretical value and lays an important groundwork for future investigation to the application of quantum gradient estimation.", "was_revised": true, "final_justification": "This work give a few methods where quantum gradient estimation replaces classical first-order information, and analyzes the error requirement of quantum zeroth-order black-box for preserving the same rates as classical first-order method. This provides a theoretical foundation for future physical implementations. The white-box acceleration, however, is conditional (requiring m ≪ n), leaving considerable room for future investigation of applications. Overall, I maintain my original score and lean toward acceptance.", "rebuttal": "Dear Reviewer 7YDD,\n\nThank you for your constructive comments and feedback. We appreciate your positive comments on the rigor, significance, and theoretical value of our work. In the following, we address your suggestions and questions in detail.\n\n> White-box results exhibit slightly worse dimensionality dependence compared to other algorithms. Though such phenomena are common in recent works of quantum optimization, the authors are suggested to briefly explain the source of the additional dimensionality dependence.\n\nThank you for the suggestion, and we will include a longer explanation in an updated manuscript. \nIndeed, our white-box results indicate a worse dimensionality dependence compared to other \\textit{quantum} algorithms, yet, the comparison requires more subtlety since these other quantum algorithms also have worse dependence on the error and other problem-dependent parameters. As a consequence our white box results present a complimentary paradigm to these other quantum algorithms which are often based on quantum matrix multiplicative weight updates.  The source of our increased dimension dependence is largely due to the fact that our black-box results require highly accurate function evaluations, and so the subroutines we use to instantiate white-box versions of these black-box algorithms cannot tolerate $\\text{poly} (1/\\varepsilon)$ scaling (we need $\\text{polylog} (1/\\varepsilon)$ scaling). Though this results in a higher dimension dependence, our dependence on the scale-invariant error term $r_p r_d/ \\varepsilon$ is significantly better. This is crucial, since both $r_p$ and $r_d$ can scale polynomially with $n$ and $m$, respectively. On the other hand, we also show that even for applications in which $r_p$ and $r_d$ are of size $\\tilde{O} (1)$, there exist regimes in which our algorithms outperform the quantum algorithms that appear to have superior scaling with respect to $m$ and $n$. \n\n> Theorem D.3 and Corollary D.1, the authors are advised to explicitly specify the form of the error rather than solely referring to it as \"additive error\".\n\nWe thank the reviewer for their suggestion to improve the clarity of our results. In an updated version of the manuscript, we will replace the closing sentence of Theorem D.3, which originally read  \"The output is an $\\varepsilon$-precise solution to the dual LP problem.\" with \"The output is a classical description of a vector $y \\in \\mathbb{R}^{m}_{\\geq 0}$ satisfying $A^{\\top} y - c \\leq 0$ and $b^{\\top} y \\leq \\text{OPT} + \\varepsilon$.\" We will also update the statement found in Corollary D.1 in a similar fashion.\n\n> The caption of the result table is suggested to include the meaning of symbols and explicitly highlight which factors demonstrate quantum advantage.\n\nThank you for the suggestion. We will change the main text accordingly to improve the clarity of our results.\n\n> The statement about dimension independence may not be entirely rigorous. Under the error function value black-box setting, the quantum gradient estimation method still exhibits a logarithmic dependence on the dimension in its query complexity. Based on my knowledge, the quantum community only proved that in the error-free black-box setting, the bounded error quantum gradient estimation can achieve a query complexity of complete dimension independence.\n\nThank you for the suggestion. Indeed the gradient estimates incur a logarithmic dependence, which is reflected in the theorems of the paper. We will make sure to say (near) dimension-dependence instead of dimension-dependence in updated versions of the manuscript.\n\n- If I understand right, the \"domain\" in Table 1 refers to a normed space, not the feasible domain. The authors are suggested to add a brief clarification to avoid potential confusion.\n> In an updated version of the manuscript, we will replace \"domain'' with \"ambient space.''\n\n\n> Regarding SDP problems, the quantum algorithms in this work output a dual solution under additive error, is it possible to derive error bounds for primal solutions?\n\nUnder standard assumptions, strong duality holds, and so the output of our dual-only algorithm can be used to estimate the optimal objective value of the primal problem up to additive error $\\varepsilon$. If one is interested in using this dual output to \\textit{compute} an approximately optimal primal solution, the dual solution can be given as input for a simplex-spectraplex saddle point problem. Note however, that this still requires solving another optimization problem.\n\n> Selecting an appropriate mirror map is one of the crucial steps in implementing quantum mirror descent. Note that the authors provided several examples (e.g., for feasible domains like the probability simplex and Schatten-1 norm). For other feasible domains, are there general methodologies for choosing the mirror map and the Bregman divergence?\n\nThe choice of mirror map is indeed crucial, as \\textit{i)} the query complexity of the mirror descent algorithm depends polynomially on the strong convexity parameter of the mirror map; and \\textit{ii)} we need to be able to efficiently compute the Bregman projection induced by the mirror map in order to update the solution in each iterate. Broadly, the mirror maps we discuss in the manuscript are the standard ones found in the literature, because \\textit{i)} they are all 1- or 2-strongly convex with respect to their applicable domains and \\textit{ii)} the Bregman projection associated to these maps admits a closed form expression. We also point out that optimization problems over more complicated problem domains can be reduced to the domains we consider. For example, one can reduce SDP problem whose feasible set is defined by the intersection of an affine space with the cone of positive semidefinite matrices, to mirror descent over the spectraplex through a well-known reformulation as a saddle point problem. \n\n> Regarding the result in Table 1, is there any classical or quantum lower bound?\n\nThank you for the question. Indeed, classical lower bound exists: for the first-order methods (last column of Table 1), when the objective function is $L$-smooth, one can have quadratic improvements via Nesterov's accelerated gradient methods [Nes83]. Intuitively, these \"accelerated\" methods use not only the gradient information in the current iterate, but also the past information. In short, the classical first-order methods constitue the update of the form $x_{t+1} \\in x_0 + \\text{span}\\{ \\nabla f(x_0), \\dots, \\nabla f(x_t) \\}$. \n\nHowever, we want to emphasize that the main message we wanted to convey in this work is that zeroth-order quantum gradient methods can match the classical first-order query complexity of gradient descent-type of algorithms. That is, nothing prevents us from analyzing zeroth-order quantum accelerated gradient methods in the similar manner that we presented our current work. As we replied to Reviewer fZUu, this constitutes a natural future direction.\\\\\nQuantumly, there exists lower bounds that illustrate there is no quantum advantage with first or higher order oracle [GKNS20, GKNS21]---this is exactly why we considered the zeroth-order setting, and showed exponential separation in terms of the dimension. \n\nThank you again for your time and efforts in reviewing our paper. We hope the above clarification addresses any outstanding questions or concerns. Please do not hesitate to ask follow up questions during the discussion period.\n\n[GKNS20] A. Garg, R. Kothari, P. Netrapalli, \\& S. Sherif, (2021). No quantum speedup over gradient descent for non-smooth convex optimization. arXiv preprint arXiv:2010.01801.\n\n[GKNS21] A. Garg, R. Kothari, P. Netrapalli, \\& S. Sherif, (2021). Near-optimal lower bounds for convex optimization for all orders of smoothness. \\textit{Advances in Neural Information Processing Systems}, 34, 29874-29884.}\n\n[Nes83] Y. E. Nesterov, 1983 \"A method for solving the convex programming problem with convergence rate $O(1/k^2)$\""}]

Author rebuttal:

Meta-review: This paper studied quantum algorithms for zeroth-order convex optimization. There are two main parameters: dimension d and precision eps, and previous quantum algorithm literature on this topic mainly studied the dependence in terms of d. This paper carefully studied quantum algorithms for zeroth-order convex optimization in terms of eps dependence. In particular, this paper proved that for various convex optimization algorithms, including Gradient Descent (GD), Projected Subgradient Method (PSG), Mirror Descent (MD), Dual Averaging (DA), and Mirror Prox (MP), the quantum algorithms achieve a similar convergence rate compared to that of classical first-order algorithms. If compared to classical zeroth-order algorithms with a linear factor in d, the proposed quantum algorithms achieve an exponential speedup in d. Technically, the results rely on a “suppressed-bias” version of Jordan's quantum gradient estimation algorithm + detailed analysis of corresponding classical algorithms. As applications, the proposed quantum algorithm provided new bounds for solving SDPs, LPs, and zero-sum games.

Among the reviews, there are three with positive scores (7YDD, eitt, fZUu) and one with negative score (Xxvf). There were adequate discussions between Xxvf and the authors with a few interactive rounds, but disagreements still exist. Given this, the AC carefully checked the manuscript as well as the arguments from both Xxvf and authors. The perspective from the AC is as follows:

- Xxvf is confused about the setting of the noise: It is noted that the paper's claim are all based on **adversarial** noises, i.e., a function value can be an arbitrary one within a certain error compared to its true evaluation (Definition 1). This model is more restricted than having stochastic noises. In this sense, all the proved bounds are stronger than having a precise evaluation oracle and hence present robustness.
 
- Xxvf is also confused about the oracle setting: Both classical and oracle here are set for black-box functions. Such black boxes are implemented by arithmetic operations - classically those are additions, multiplications, etc., and quantumly those are the same arithmetic operations in superposition (quantum adders, multipliers, etc.). There is no sampling in constructing the oracles. 

- However, the authors did not make correct citations to classical lower bounds. The AC agrees with Xxvf's comment that the mentioned classical lower bound papers [JNR12], [DJW15], [Sha13] all considered **stochastic** convex optimization with $\Omega(1)$ variance, and it is to be emphasized that lower bounds on stochastic convex optimization and non-stochastic convex optimization are not the same problem. Nevertheless, I think [WS17] below is a correct bound to refer to as it proved a $\Omega(L^2 B^2/eps^2)$ classical first-order lower bound (L being the Lipschitz parameter and B being an upper bound on x's norm) that allows each query to give any subgradient and applies to any randomized algorithm. It would be even better to find a $\Omega(d \cdot L^2 B^2/eps^2)$ classical zeroth-order lower bound, but the AC cannot easily find such a result - would be great for authors to check more into corresponding literature. 

In all, given that

- This paper studied quantum algorithms for zeroth-order convex optimization in terms of eps dependence, which an important setting, with further applications into widespread optimization problems such as SDPs, LPs, and zero-sum games, and 

- Three reviewers voted for positive scores, and the review with negative score got confused with points clarified above,

the decision to accept this paper at NeurIPS 2025.

Nevertheless, the authors should make the following changes in the final version of the paper:

- Make correct citations to classical lower bounds (see the point above), especially the [WS17] paper. It would be helpful if the authors can find a paper with classical $\Omega(d)$ lower bound using zeroth-order oracle, or discuss about why it is believed that this holds for classical **non-stochastic** convex optimization. 

- All promised changes in rebuttal.

- This was not raised by reviewers, but when the AC checked the paper, it is observed that the authors should expand "Limitations and future work" at the end of the paper about the applications studied in this paper, from the following two perspectives:

- - In rebuttal, the authors mentioned that this paper considered the high-dimensional, low-precision regime. However, it is noted that
that in such cases, especially when the precision is as low as a constant, the bound for SDP may be worse than the earlier quantum work [72], and the bound for LP may be worse than the earlier quantum works [11,29]. I suggest the authors to further discuss the limitations of their results compared to previous quantum algorithm works, in particular highlight more on which domains the proposed quantum algorithms are better.

- - Given that the applications to LP, SDP, and zero-sum games all have polynomial dependence in 1/eps, I suggest the authors to comment more on whether Nesterov-type acceleration is possible for these applications in particular given that the noise tolerance might be more stringent than the non-accelerated results.

**References**

[JNR12] K. G. Jamieson, R. D. Nowak, B. Recht, 2012 "Query Complexity of Derivative-Free Optimization".

[DJW15] J. C. Duchi, M. I. Jordan, M. J. Wainwright, A. Wibisono, 2015 "Optimal rates for zero-order convex optimization: the power of two function evaluations".

[Sha13] O. Shamir, 2013 "On the Complexity of Bandit and Derivative-Free Stochastic Convex Optimization".

[WS17] B. Woodworth and N. Srebro. "Lower bound for randomized first order convex optimization." arXiv preprint arXiv:1709.03594 (2017).
Decision: Accept (poster)