Quantum Speedups for Minimax Optimization and Beyond
Authors: Chengchang Liu
Zongqi Wan
Jialin Zhang
Xiaoming Sun
John C.S. Lui
Venue: NeurIPS 2025 poster ()
Keywords: minimax optimization
quantum computing
Primary area: optimization

Abstract: This paper investigates convex-concave minimax optimization problems where only the function value access is allowed.
We introduce a class of Hessian-aware quantum zeroth-order methods that can find the $\epsilon$-saddle point within $\tilde{\mathcal{O}}(d^{2/3}\epsilon^{-2/3})$ function value oracle calls.
This represents an improvement of $d^{1/3}\epsilon^{-1/3}$ over the $\mathcal{O}(d\epsilon^{-1})$ upper bound of classical zeroth-order methods, where $d$ denotes the problem dimension.
We extend these results to $\mu$-strongly-convex $\mu$-strongly-concave minimax problems using a restart strategy, and show a speedup of $d^{1/3}\mu^{-1/3}$ compared to classical zeroth-order methods.
The acceleration achieved by our methods stems from the construction of efficient quantum estimators for the Hessian and the subsequent design of efficient Hessian-aware algorithms.
In addition, we apply such ideas to non-convex optimization, leading to a reduction in the query complexity compared to classical methods.

Quantum Speedups for Minimax Optimization and Beyond
Chengehang Liu The Chinese University of Hong Kong Tliuchengchang@gmall com
Zongqi Wan" Great Bay University zqwan@gbu. edu. cn
Jialin Zhang
Xiaoming Sun Institute of Computing Technology, CAS sunxiaoming@ice ac on
Institute of Computing Technology, CAS changjialin@in
John C.S. Lui
The Chinese University of Hong Kong cslui@cse. cuhk. edu. hk
Abstract
This paper investigates convex-concave minimax optimization problems where only the function value access is allowed. We introduce class of Hessian- aware quantum zeroth-order methods that can find the e-saddle point within ( function value oracle calls. This represents an improvement 11/3 over the (dc upper bound of classical zeroth-order methods, where d denotes the problem dimension. We extend these results to f--strongyy- convex j=strrogglycconcaee minimax problems using a restart strategy, and show a speedup of /3 1/3 compared to classical zeroth-order methods. The acceler- ation achieved by methods stems from the construction of efficient quantum estimators for the Hessian and the subsequent design of efficient Hessian-aware algorithms. In addition, apply such ideas non-convex optimization, leading to a reduction in the query complexity compared to classical methods.
Introduction
We consider the following unconstrained minimax problem:
min max h(x, x yeR
(I)
where - is convex in x and concave in Let d = n, z = TT E Rdd and
define f(z) f(x,y). The above problem has received considerable attention in the field of machine learning due its wide applications, including fairness-aware learning [52 32), AUC maximization (51, 20), robust optimization 3], game theory [48), and reinforcement learning [15.
43
There are numerous classical algorithms to solve the convex-concave minimax problem 1 First- order methods, such the optimistic gradient descent ascent (OGDA) (44, 36), extra gradient method (BG) (27 38), along with their variants [40, 33) find an e-saddle point within ((e gra- dient oracle queries when h(:,-) smooth. When (²h(,,-) is Lipschitz continuous, second-order
The corresponding author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

methods offer faster convergence rates. The Newton proximal extra gradient method (NPE) [37] and its cubic-rogularized realization [31 22 require ( queries to the second-order oracle. Very recently, Chen et al. [11] further improved the second-order oracle complexity to ((c-4/7). These results have been generalized to the cases where the p-th order derivative of h(:.-) -) is Lipschitz, with
query complexity of O(c FFT) to the p-th order oracle 30
24
However, access to the gradient oracle or higher-order oracles of h(.,-) is not always available, as the calculation of the exact gradient (or higher order) information can be expensive or even infea- sible [42 35, 25 53 This necessitates the design of efficient derivative-free algorithms to solve equation Beznosikov et al. [4] proposed a gradient-free algorithm with O(de-)) query com- plexity h(..-) for the smooth convex-concave minimax problem (.. Subsequently, this rate was improved to (de by Sadiev et al. [45], whose dependence on e matches the lower bound for first-order methods [54].
The aforementioned methods for minimax problems are all designed for classical computing ma- chines. However, the advantage of quantum computing has been investigated for various optimiza- tion problems. Accessing quantum counterparts of the classical oracles always leads to better query complexities or even breakthrough over the classical lower bounds, including convex [47 & g [5]
or non-convex optimization [46, 19), semi-definite programming [ G), non-smooth optimiza- tion I 33 28 stochastic optimization [41, [55, 46). and so on. There are also some previous studies on some specific minimax problems, including the zero-sum game [29. [6] and minimizing
the maximal loss [49). However, it remains open question whether quantum speedup is available for general concave minimax problems. Thus, the first question we aim to address is:
Can quantum zeroth-order methods be designed to surpass the (dc query complexity of clas- sical zeroth-order methods, thereby demonstrating quantum speedup for general convex-concave minimax problems?
natural approach to achieve this is to leverage the fast gradient estimator [26]. which can ap- proximate the gradient of smooth objective function within Ô(1) queries to the quantum function value oracle, based on the quantum Fourier transform (50). In convex optimization, employing the fast gradient estimator within cutting-plane algorithms and gradient descent leads to improved query complexities compared to classical zeroth-order methods. Specifically, the quantum cutting- plane method [ and the quantum gradient descent method (2 achieve query complexities of ((d) and O)) respectively, improving upon the Ocd) and O(e complexities of classical zeroth- order methods by a factor of d. For non-convex optimization, similar strategy has been used in the design of quantum perturbed AGD 19], resulting in an improved query complexity of ((-/))
compared to the Ö complexity of the classical zeroth-order method (53). These methods use the quantum gradient estimators to achieve the same query complexities as classical first-order methods by accessing only zeroth-order oracles, which reduces the dependency on d. On the other hand, the oracle complexity of classical second-order methods enjoys better dependency on e when compared to the classical first-order methods. This motivates us to ask:
Can we go beyond quantum estimation for the gradient and design efficient Hessian- aware quantum zeroth-order algorithms with better dependence on both e and d?
In this paper, we provide an affirmative answer to the above two questions. To this end, we develop quantum estimator for the Hessian matrix using the finite difference method and design novel aase zeroth-order optimization framework. We summarize our contributions as follows.
* For the (HAQZO), with query complexity of Óde ((d))-233 to find the e-saddle point, which surpasses the classical zeroth-order method by factor of c 11/3, We further accelerate such query complexity to Ö(d + d2/3g-2/3 by proposing double-loop Hessian-
problem, we propose Hessian-aware quantum zeroth-order method
quantum method (HAQZO*) that can reuse the Hessian estimators. HAQZO* accelerates the classical algorithms in terms of e -1 and d. We compare HAQZO and HAQZO+ with the existing method in Table [ The detailed analysis of HAQZO and HAQZO+ can be found in Sections 4.1 and 4.2
respectively.
For the Soanglyy-oonee--stonggyyoooooo and propose Restart-HAQZO We prove that Restart-HAQZO* finds the e-point with query complexity of O(d (L2/H) outperforms the classical method by factor d'/3, -1/3.
problem, we apply the restart strategy in HAQZO+

---

Table 1: We summarize the complexities of function value oracles to find the c-saddle point (c.f.
Section for the convex-concave minimax problem (
Methods
Oracle
Query Complexity
Reference
ZOSPA
classical
O (dc-2)
Beznosikov et al.
ZOVIA
classical
O (de
Sadiev et al. [45]
HAQZO Algorithm K
quantum
Ô (dc
Theorem
HAQZO
Algorithm
quantum
O (d (2/3
Theorem 4.5
Table We summarize the complexities of function value oracles find the c-point for μ-strongly-
convex-p-stronn /-strroglyycoocay minimax problem (.. i.e. ||z - z < c. We use L, (i = 2) denotes
Lipschitz continuous parameter of i-th order derivatives of f(().
Methods
Oracle
Query Complexity
Reference
ZOVIA
classical
Ô (dIz/P)
Sadiev et al. [45]
Algorithm
quantum
Ô (d/s
d2/3 (L2/3(L22))2/)))
Theorem 4.8
Table 3: We summarize the complexities of function value oracles to find the e-stationary point of < e. We use d to denote the dimension of the non-convex minimization problem (10). i.c. [[)
problem.
Methods
Oracle
Query Complexity
Reference
GFM
classical
O (de
Zhang and Gu [53]
DF-CNM
classical
Ô (d2t-3/2)
Cartis al.
Zero-Order CNM
classical
Ô (d + (3/22-3/22
Doikov and Grapiglia [13]
Q-Perturbed-AGD
quantum
Ô (E-1/4
Gong et al. [19]
Algorithm 0
QCNM
quantum
Ô dd222/223313)
Theorem
The comparison of the query complexities can be found in Table and the detailed analysis presented in Section 4.3
We further generalize the design of Hessian- quantum methods to solve non-convex prob- lems with Lipschitz continuous Hessian. We propose the quantum cubic regularized-Newton method (QCNM) with query complexity O(d + /222-3//2 -122) to find the e-stationary point, which is better than all classical zeroth-order algorithms. The proposed QCNM method also joys an improved quantum query complexity over the existing mate--oftthe-ee quantum algorithm when ( -1/2), demonstrating the power of designing Hessian-aware quantum algorithms. We compare QCNM with existing classical algorithms and quantum algorithms in Table 3 and present the results in Section
2 Preliminaries
We make the following assumptions on f(z) 2 h(x,y).
Assumption 2.1. We assume f() y) is convex in and concave in

---

we let 3 sufficiently large such that Assumption 2.2. We assume the f()). vf(.). : f() are Lo- L1, and L Liphhisc continuous,
respectively, i.e. we have ff f(z') Lollz z [V Vf(zzl - Li z z'Il. and
[(z) - v s²)(2))| - |2|2 - -
(2)
for any z' E R
We aim to find the approximate saddle point 33. 31 12
which defined as follows.
x"
Definition 1 (Nesterov (3)). Let IB (w) be the ball centered at w with radius B. Let z
_
y"
be the saddle point of function f(-). For given point 2
y1 S 3 holds, we define the restricted gap function as max [| x"11, l8
x
[
G) == yEBa(y")
min f xxBx(x')
We call à an e-saddle point if Gap(2; S c and B = 22[1zo =))
V vx y)
In the following context, we define F-) as F(z) A JV =
where J =
v (yh(x, y)
diag(Im, II,). The Jacobian of F(.) can be written as VF FF).. The following propo- sition shows that F-)) is monotone if f()) satisfies Assumption 2.1
Proposition 2.3 (Lemma 2.7 (30)). If satisfies Assumption 2.1 then for all z, z' IR it holds that (z) F Fzz)), (.'))e z
z²) 2 0. For a given à E Rd its gap be bounded by Gap(2; B) s
max (2*) (2), 2 z)-
We define the quantum evaluation oracle for function f(-)- Definition 2.4 (Quantum Function Evaluation Oracle). A quantum evaluation oracle for function f is defined as the following unitary transformation
U [z) 12) @ f(z)).
Here @ is the bit-wise XOR operation. We say that have quantum evaluation oracle for f with accuracy Eg if we have a quantum evaluation oracle for f. such that [f(z) f(z) S eg for all z.
Remark 2.5. The quantum advantages are stated in terms of query complexity on the function eval- uation oracle. In many situations, query complexity dominates the computational complexity of algorithm, which considering the generalized linear model such that fxx = A(ATx where A E Rdxn, The circuit implementation of the oracle of f may involve dominating computational complexity if > d in this example, and our algorithm achieves meaningful quantum speedups under such setting.
natural setting both classical and quantum optimization. For example,
Gradient and Hessian Estimation via Quantum Function Evaluation Oracle
Before introducing our quantum algorithms, we first introduce the quantum estimators for the gra- dient and Hessian of the objective function by using the quantum evaluation oracle on f()), which are the critical components of our methods. These results are natural and direct extensions of Jor- dan's method (26] for the smooth objective. We do not consider them to be our primary technical contribution, but state them for completeness.
3.1 Quantum Gradient Estimator
Quantum gradient estimator is first proposed in [26] for the smooth objective, and its rigorous state- ment is given by Gilyén al. [1]] Chakrabarti et [ van Apeldoor al. [47]. The following one of the statements.

---

Lemma 3.1 (Lemma 2.2 18.. Let f be an Lo Li-Lipschitz continuous and ---soooth function. Given the access a quantum evaluation oracle of f with en accuracy, then for Eg 2 Eg there is quantum algorithm A(f, cg. Lo, L1, z) which outputs an estimate V f(z) of V fZ)). satisfying that Vi E [d]. Pr ( f()) [V]())]: 2 1500 L1dde)) S Moreover, the A algorithm uses ((1) queries
Le to the quantum evaluation oracle and O (d aLice/ quantum gates.
The following lemma allows for an arbitrarily small failure probability 8 E (0, to the quantum gradient estimator, which generalizes the results above.
Lemma 3.2 (Quantum Gradient Estimator). Let f()) be Lo-Lipschitz continuous and L smooth function. Given the access to a quantum evaluation oracle of f with en accuracy, then for eg 2 eo. there exists quantum algorithm QuantumGran adi ent(J, Lo, L1, 2, which ouiputs an estimate < fz) Vf (Z), satisfying
Pr (1))
V V5(()) 2 1500d L16g) SÓ.
Moreover, QuantumGradient uses (1og( queries to U, and O (dlog(atin) Lo atic
log( gates.
3.2 Quantum Hessian-vector Estimator and Quantum Hessian Estimator
In this section, show that the Hessian vector product of smooth object function can also be constructed within the O(1) quantum function evaluation oracle. Furthermore, since fz)
[V fz))(z) ... V fz))e,, the Hessian smooth object function can be constructed within the (d) quantum function evaluation oracle.
We formally present construction of the quantum Hessian vector product estimator in Algo- rithm [and state its complexity in the following lemma.
Algorithm Quanttunllessiianeeetttrro (ʃ, shv, Lo, L1, Lz, 2, v,
1: M ||vl22
2: = 20v T5e 1/4 1/ "/
hv
3: fz(z) QuantumGradient(( Chv, Lo, L1, z, 8/2)
4: Vf(z + Av) = QuantumGradient([f Cvv Lo, In, z + v,8/2)
5: Return Vf(x+Av) -f)-()
Lemma 3.3 (Quantum Hessian Vector Estimator). Suppose f satisfies Assumption 2.2
Given the
access to U, with eo accuracy, let hy Quantummess anVector (f, Ehv, Lo, Li, L2, 2, v, 5) be the oulput of Algorithm SaetmmmZWweee where env 2 eo, then it holds that
(2)(2)/112 P
(IIbv Dr
10vT5(dT (hv
In)1//) (ch s 8.
Moreover, Algorithm Juses (log(())
d)) queries to U, and O (dlog( Lo at. log( gates.
Remark 3.4. He et al. [21]] proposed a quantum estimator for row of Hessian, which can be viewed as a special case of our quantum Hessian vector estimator. Besides, they do not provide results on the query complexity and gate complexity.
Given the Hessian vector estimator, we are ready to construct the Hessian estimator by calculating the estimators of the Hessian vector set fx)eex which formally given in Algorithm 2
The following results show how well the output of Algorithm@lappe @lpproximmaess V fz).
Lemma 3.5 (Quantum Hessian Estimator). Suppose f satisfies Assumption 2.2
Given ac-
cess to quantum evaluation oracle of f with eo accuracy and си 2 let fZ) = Quantunesssian wntteesssianff.... EH, Lo. L1. L2, 2, be the output of Algorithm [2) then it holds that
Pr (1 f(z) V² (=)(2)) 10V15d L, L1
1/1
G 8.
(5)
Moreover, Algorithm uses (d) queries to U, and O (1l log ( log($)) gates.
5

---

Algorithm 2 QuuntuumHsssian <H, Lo. L1, L,, 2,
1: H Oaxd
2: for E [d]
3: H guantunffessiinneectooo (f.cH. Lo, In, L2, 2, C, 6/d)
4: H= ( )
5: Return H
Algorithm 3 HAQZO(Zu, T, Lo. L1, L2,
for = trt==0.... 0,....... , ,T' do
2:
Choose c1,t > 0 and EH. > 0
3: gr QuantumGradient((f 51,t1 Lo, L1, 2, 8/(3)) and g: Jg:
4:
H. = QuantumHessiann an a EH. Lo, L1, L2, zt, 2..6 (3T)) and H. JH,
5:
Compute the inexact cubic step i.e. find 2,41/2 that satisfies
+ (H, (,+26(122 +141//l++11500d" 1,/4 v1500d 1// H.)) (Z441/2 - -2)=0 =0 Lit
g:
d = 6 L2]1zz - 2411/2 + 22 1/4 1/4
6, + v1500d L L2 1/2 (H..)
6:
7: Choose 62, >0 0
8: Ve+1/2 QuantumGradient((ff..m c2 Lo, L1 1441/2 5/(3)) and Vi Jv:
Xi -v
9: Ze-1 Z.
10: end for
return 2T EE Ei= X X-1 7111/2
Remark 3.6. We note an independent work by Zhang and Shao [50], who also employed the finite difference method to construct Hessian estimator for the more general class of complex analytical functions. In contrast to our estimator, which is designed for smooth real functions, their approach utilizes the more sophisticated spectral method to handle the complex case. On the other hand, our theoretical error bound is measured using the spectral norm (Il-112), while the bound in [56] is given in the infinity norm () lloo).
Quantum Speedups for Minimax Optimization
In this section, we introduce quantum algorithms to find the e-saddle point for general convex- concave minimax problems. In Section 4.] we propose Hessian-aware algorithm with -2/3) queries to the quantum function evaluation oracle, which outperforms the classical state-of-the-art algorithm by factor of -1/3, We further improve such query complexity ( 2/3), which outperforms the classical algorithm by factor of d3//3-11/ -1/3, by proposing a double-loop algorithm that reuses the Hessian estimators in Section 4.2 In Section 4.3 we generalize our results to strongly- convex- stanxe--trongly-coneae problems.
1/3
4.1 Hessian-Aware Quantum Algorithm with Better Dependency on -
Our idea is to use the quantum gradient estimator and the quantum Hessian estimator to obtain close approximation of F(z) and (Z(z) and then apply the Newton proximal extragradient frame- work [37]. We present our Hessian-aware quantum zeroth-order method (HAQZO) in Algorithm 3
To analyze Algorithm g we first consider the following generalized NPE update:
Ze+1/2 Z, (H, -x1)-1g
(6)
Ze+1 = X, V:
where gr, Ve, and H. are some approximations to (Z)), F F2z411/2) and VF (z:), which satisfy
Igg - F(z))l < 61,1, |v: F(2++1/2)l S 62,1, and H, VF(z))] S 6HH-- The following lemma shows that the update of i recovers the convergence rates of the NPE method if 81,,, 82,1, .. and HH. small enough.
(7)

---

Algorithm 4 HAQZO* (zo: T, Lo, 11, L2, 2,,,,,M, m,
1: for -0,... , - do
2:
if't mod do
3:
Choose CH >
4: H = Quu.ntumteessiiin(ff...... Lo, L1, L2, Ze, (/(T)) and H JH
5:
end if
6:
Choose 61,1
7: ge QuantumGradient(/ 61,1, Lo, I1, 24, 8/ (3T) and gt = Jg.
8:
Compute the inexact cubic step i.e. find 2/41/2 that satisfies
+ (H 6[ 11+1/2ll 12 1//4 1/4 C1 + v150dd L L1 1/4)1) (zi-1/2 =0)=0
V1500d L// L2 1/2 1/4 1/4 d = 6 M | 21+1/2ll / 12
9:
10: Choose 2, > 0
11:
V2+1/2 QuantumGradient((f.crr Lo, L1 1/21/2 6/())) and V: JV:
Zt-1 Zt. Xx --v Vi-
12:
13: end for
14: return ZT 2i X, 2i=0 Xi 2t+1/2.
T-1 generated from where d 6 (L2 [22lz211/2 zell + ôH, + Vol,e), and ò1,t, 8n and ôH in 7 satisfy
Lemma 4.1. Under Assumptions
2.1 and 2.2 let R S2llzo I)] {2142/2)1=0
R²
82,1
min-
A,R² 10T(
61 SH., / then we have Gap(ør; v3R)
107
8,41/2
no [R]
O
LaR 7512
where žT
X;- Z1+1/2-
El
Remark 4.2. We note that some prior works have also studied the inexact NPE methods [31. However, these methods only consider the case where the Hessian is inexact, while our Lemmal allows inexactness from both the gradient and the Hessian.
Because the iteration rule of Algorithm R can be interpreted the generalized NPE update in (6) with high probability, we can determine the query complexity of Algorithm By incorporating the quantum gradient and Hessian estimators. This result is formally stated in the following theorem.
Theorem 4.3. Under Assumptions 2. and let we run Algorithm 3 with
2.2
2( z² II), given desired accuracy
RA
R CH. 1500 L
T (34561/3 2/3 42/33 R2 61,1
L
R
E and 8 (0.1),
min
15000%T2d>L11 2t+1/2 zol + R)2
then with probability at 1 - 8, Algorithm finds the e-saddle point of f(-) with (dL 2/3 R2 -2/3) queries to Uy, where ((-) hides the polylogarithm dependency on d, Lo, Ln Ly, e- 8-1, and R.
4.2 Hessian-Aware Quantum Algorithm with Better Dependency c- and d
In this section, we further improve the query complexity of HAQZO by proposing double-loop Hessian-aware quantum method HAQZO* in Algorithm which is inspired by the recent advance
in lazy Hessian methods [14, 12 10. 34].
The main difference between Algorithm 4 and Algorithm 3 is that we eliminate calling quantunHessian in every iteration, but only call it at the snapshot point in iterations when / mod m = 0, and reuse such Hessian estimator the next m iterations. addition, we replace T with larger parameter M L2 Line 9 and Line 10 and tune it to guarantee convergence. We
7

---

Algorithm 5 Restart-HAQZO (zo. T, Lo, L1, L2, M, m, S,6)
1: (0)) Ag
2: for = 0, ................................ .......--
-51
3: 2(*+1) HAQZO (z(*), (,,,,T Lo, L1, L2, M, m, 8/5)
4: end for
5: return (9)
first consider the following iteration rule
2t/1/2 = 2 - (H) + A,I)- Zi+1 = X Vz
(8)
where rtt) A t (t mod m) and gt, V1, H (t) are approximations F(z:). F 1(2(41/2)
(Z)))()) such that
gi - F(z))l s 81,6, - F(2e4/2))) & 62,0. and H(())) -VF(ZT()) - бн.
(9)
The following lemma shows that the update of ( still enjoys the rate of -322 if the regularization term X is chosen large enough and ò1,t, 62 and 6h are small.
3/2
Lemma 4.4. Under Assumpions
2. and 2.2
let R 22[1zo =)),), 1/2+122 generated from
8 where d = 6 Zz+1// Ze + 8H
VoL.). and 81,, 52,0 бн in ( satisfies ò1, S 107
R²
52,; < min
A.R²
òH <
R VT
if M
mla then we have Gap(žr; v3R) /3
10T 2| Zo +R)*
O
MR T3/3
where Zr
11= X 1/21/2-
Σ1-0
A,
The iteration rule of Algorithm 4 can also be interpreted as iteration, the algorithm calls QuantumGradient with (1) quantum function evaluation queries to obtain g: and Every iterations, the algorithm calls QuantunHessian with Ó(d) quantum function evaluation queries to obtain H,. The following theorem provides the query complexity of Algorithm 4 with proper choice of m d.
8 with high probability. At each
Theorem 4.5. Under Assumptions and 2.2 let R = 2(11zo - z []), given desired accuracy > 0, we run Algorithm with
R
m = d, M = =dL///3, T = (34561/MM21) + 12 - -2/3
61,t 15000 2 T, T2
Rs
R
c
"H 1500 L10 L2T2
6, min
15000 (1 20 11 + R2)3
S
8 (0.1),
then Algorithmm4 the e-saddle point of f(-) with Od + d2/3 | 2113) queries to U, with probability at 1- 8, where (() hides the polylogarithm dependency on d, Lo. L,, L2, e- 8-1, and R.
4.3 Restarted Hessian-Aware Quantum Algorithm for Strongly-Convex Strongly-Conent Minimax Optimization
In this section, generalize our results to solve strongly-oovee-stronlyyoooom minimax prob- lems. We make the following assumption on f(.), which is stronger than Assumption 2.1
Assumption 4.6. We assume f(z) y)x y) is p-strongly-convex y for some > 0.
and pestrongly-cooneve in
We apply the restart strategy which is widely used in minimization 17 and minimax optimiza- tion 122. 30. [2] on our HAQZO and propose Restart-HAQZO in Algorithm [ To avoid con- fusion, we use the superscript (*) to denote the parameters in the HAQZO subroutine in the s-th iteration of Algorithm [ The following lemma shows that by properly choosing the parameter in
HAQZO (x(11) z == will descend linearly with high probability.

---

Lemma 4.7. Under Assumptions 2.2 4.6 set the parameter in subroutine HAQZO* in the s-th
iteration of Algorithm 5 follows:
M mL2
(100M + 12)3/3 12(0)
2z 11//3/
(4) -2"11-
== v3
12/3
$1
1500"d-IITT2*
(5) [|2(,) x=
(210))9112(0) - 2²11
HH d L L2L3T2'
2,
(5) min
ô E (0, 1).
240002Ta 2412 -
then 1 (0+1) z1 || 1 ( z"| holds with probability at least - 88/5).
Lemma 4.7 means it is enough to set S = (log(1/e) to obtain some z (5) such that | [5( - ==1 Given this, we are ready to present the query complexity of Algorithm
Theorem 4.8. Under Assumptions 2.2 and 4.6 set the parameter in subroutine HAQZO + in the d, and set S = [log[[|z [|| (0) 2 12" /e)], then
iteration of Algorithm as in Lemma 4.7 with
with probability at least 6, the output of Algorithm [ scatisfies that ||z( x-
with
Old + /2/3 1/233 1223312111) -2/3) queries to U, where (-) hides the polylogaritmm dependency on d, Lo.
L,, L2, - 8-1
5 Extension to Non-convex Optimization
In the previous section, we have shown that, using quantum Hessian estimators, it is possible to design fast quantum algorithms which outperform the classical algorithms in terms of accuracy e and dimension d. We highlight that the quantum estimators designed Section not restricted to convex-concave minimax problems. In this section, extend the idea of designing Hessian-aware quantum zeroth-order methods to non-convex problems
min fz),
(10)
xERd
where f(.) is smooth but possibly not convex. We aim find the c-stationary point of (1))
Definition 5.1. We say is an e-stationary point of the nonconvex minimization problem (10 if holds that [[)]l S.
We present the quantum cal gradient and Hessian estimators in the geroth-order CNM method [13] by the quantum estimators
Newton methods in Algorithm O which replace the classi-
designed in Section The following theorem gives the query complexity of Algorithm@6l to find the c-stationary point of ʃ(-)-
Theorem 5.2. Under Assumption 2.2 and suppose f minzez" f(z) > -00, given desired
accuracy > O, we run Algorithm 0 with
/92 --)e
m =d, d, 30I2d, T
3
-2
20004d2L3 CH 15 and EE (0,1),
then with probability at least 1 - 8, the output of Algorithm Binds the c-stationary point of prob-
10 O(d /2 (f(z)) -- -f") queries U, where Õ(-) hides the polylogarithm
dependency on Lo. L1, Tz, c1 8-1.
Conclusion
In this paper, we have proposed quantum algorithms to speed up training for minimax optimization problems. Our Hessian-aware quantum zeroth-order method reduces the query complexity of the function evaluation oracle of the classical methods by factor of d and d1/3 1/3 for convex-concave and moongly-convex-stronne sonnex-strongly--oocvve problems, respectively. Moreover, we find that proposed quantum oracles for estimating the Hessian matrix can be used to solve other important optimization problems, i.e. non-convex optimization. However, the query complexity of the proposed Hessian-aware quantum zeroth-order methods still depends on the dimension, and the quantum lower bound for this question is still unknown. We leave this for future work.

---

Algorithm 6 6CCNM 2n. T. Lo, L1, 12, M, &g. <H, 0)
1: 0g = 1500dL 1/2 1/2 1/2
би = 1500 | 1//2201 1/4
8
(H
2: for = 0, T do
3: if' mod m do
4:
H Quantumiesssian((..rr Lo, L1, L2, Ze, 8/ (2T)
5:
end if
6: gi QuantumGradient(ff. <g. Lo. L1, Ze. 6/ (2T))
7:
Compute the cubic step i.e. find 1 that satisfies
M
Z1+1 arg min zER-
(g zt) +
H (z zi), zi)
+ 6 1 11
8: end for
9:
return Zont uniformly from {2:}T=1
Acknowledgment
We thank the anonymous reviewers for their helpful suggestions. Zongqi Wan, Jialin Zhang, and Xiaoming Sun are supported by the National Natural Science Foundation of China Grants No. 62325210 and 12447107. Chengchang Liu is supported by the National Natural Science Foundation of China (624B2125). John C.S. Lui is supported in part by the GRF-14207721 and SRFS2122- 4S02.
References
[1] Artem Agafonov, Petr Ostroukhov, Roman Mozhaev, Konstantin Yakovlev, Eduard Gorbunov, Martin Takác, Alexander Gasnikov, and Dmitry Kamzolov. Exploring jacobian inexactness in second-order methods for variational inequalities: lower bounds. optimal algorithms and quasi- newton approximations. Advances in Neural Information Processing Systems, 37:1 17:115816- 115860, 2024.
[2] Brandon Augustino, Dylan Herman, Enrico Fontana, Junhyung Lyle Kim, Jacob Watkins, Shouvanik Chakrabarti, and Marco Pistoia. Fast convex optimization with quantum gradient methods. arXiv preprint arXiv:2503. /7356, 2025.
[3] Aharon Ben-Tal, Laurent El Ghaoui, and Arkadi Nemirovski. Robust optimization. Princeton university press, 2009.
[4] Aleksandr Beznosikov, Abdurakhmon Sadiev, and Alexander Gasnikov. Gradient-free meth- ods with inexact oracle for convex-concave stochastic saddle-point problem. In International Conference Mathematical Optimization Theory and Operations Research, pages 105-119. Springer, 2020.
[5] Fernando GSL Brandao and Krysta M Svore. Quantum speed-ups for solving semidefinite pro- grams. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 415 415-426. IEEE, 2017.
[6] Fernando GSL Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yo Yu Lin, Krysta M Svore, and Xiaodi Wu. Quantum sdp solvers: Large speed-ups, optimality, and applications to quan- tum learning. In 46th International Colloquium on Automata, Languages, and Programming Zentrum für Informatik, 2019.
(ICALP 2019). Schloss-Dagstuhl-LLe
[7] Coralia Cartis, Nicholas IM Gould, and Philippe L Toint. On the oracle complexity of first- order and derivative-free algorithms for smooth nonconvex minimization. SIAM Journal on Optimization, 22(1):66 86, 2012.
[8] Shouvanik Chakrabarti, Andrew M Childs, Tongyang Li, and Xiaodi Wu. Quantum algorithms and lower bounds for convex optimization. Quantum, 4:221, 2020.
10

---

[9] Shouvanik Chakrabarti. Andrew M Childs, Shih-Han Hung, Tongyang Li, Chunhao Wang, and Xiaodi Wu. Quantum algorithm for estimating volumes of convex bodies, ACM Transactions on Quantum Computing, 4(3):1-60 2023.
[10] Lesi Chen, Chengchang Liu, Luo Luo, and Jingzhao Zhang. Computationally faster newton methods by lazy evaluations. arXiv preprint arXiv:2501. 2025.
[11] Lesi Chen, Chengchang Liu, Luo Luo, and Jingzhao Zhang. Solving coneave problems with Ö(e-4/7) second-order oracle complexity. The 38th Annual Conference on Learning Theory, 2025.
[12] Lesi Chen, Chengchang Liu, and Jingzhao Zhang. Second-order min-max optimization with lazy hessians. The Thirteenth International Conference on Learning Representations, 2025,
[13] Nikita Doikov and Geovani Nunes Grapiglia. First and zeroth-order implementations of the regularized newton method with lazy approximated hessians. Journal of Scientific Computing. 103(1):32, 2025.
[14] Nikita Doikov, EI Mahdi Chayti, and Martin Jaggi. Second-order optimization with lazy hes- sians. In ICML, 2023.
[15] Simon S. Du, Jianshu Chen, Lihong Li, Lin Xiao, and Dengyong Zhou. Stochastic variance reduction methods for policy evaluation. In ICML, 2017.
[16] Minbo Gao, Zhengfeng Ji, Tongyang Li, and Qisheng Wang. Logarithmic-regret quantum learning algorithms for zero-sum games. Advances in Neural Information Processing Systems, 36:31177-31203. 2023.
[17] Saeed Ghadimi, Han Liu, and Tong Zhang. Second-order methods with cubic regularization under inexact information. arXiv preprint arXiv: 2017.
[18] András Gilyén, Srinivasan Arunachalam, and Nathan Wiebe. Optimizing quantum optimiza- tion algorithms via faster quantum gradient computation. In Proceedings of the Thirtieth An- nual ACM-SIAM Symposium on Discrete Algorithms, pages 1425-1444. SIAM, 2019.
[19] Weiyuan Gong, Chenyi Zhang, and Tongyang Li. Robustness quantum algorithms for non- convex optimization. In The Thirteenth International Conference Learning Representations, 2025.
[20] James A. Hanley and Barbara J. McNeil. The meaning and use of the area under a receiver operating characteristic (ROC) curve. Radiology, 143(1):29-38) 1982.
[21] Jianhao He, Chengehang Liu, Xutong Liu, Lvzhou Li, and John C.S. Lui. Quantum algorithm for online exp-concave optimization. In International Conference on Machine Learning, pages 17946-1797i. PMLR, 2024.
[22] Kevin Huang and Shuzhong Zhang. An approximation- based regularized extra-gradient method for monotone variational inequalities. arXiv preprint arXiv:2210.04440, 2022.
[23] Kevin Huang. Junyu Zhang, and Shuzhong Zhang. Cubic regularized Newton method for sad- dle point models: a global and local convergence analysis. arXiv preprint arXiv:2008.09919 2020.
[24] Ruichen Jiang and Aryan Mokhtari. Generalized optimistic methods for convex-concave sad- dle point problems. arXiv preprint 1xXiv:2202.09674, 2022.
[25] Gangshan Jing, He Bai, Jemin George, Aranya Chakrabortty, and Piyush K Sharma. Asyn- chronous distributed reinforcement learning for lqr control via zeroth-order block coordinate descent. IEEE Transactions on Automatic Control, 2024. 2024.
[26] Stephen P Jordan. Fast quantum algorithm for numerical gradient estimation. Physical review letters, 9555)00000 2005.
[27] G. M. Korpelevich. An extragradient method for finding saddle points and for other problems. Matecon, 12:747-756, 1976.

---

[28] Jiaqi Leng, Yufan Zheng, Zhiyuan Jia, Lei Fan, Chaoyue Zhao, Yuxiang Peng, and Xiaodi Wu. Quantum hamiltonian descent for non non-smooth optimization. arXiv preprint MrXiv:2503.1887. 2025.
[29] 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-8473, 2021.
[30] Tianyi Lin and Michael I. Jordan. Perseus: A simple high-order regularization method for variational inequalities. arXiv preprint arXiv:2205.032002 2022.
[31] Tianyi Lin, Panayotis Mertikopoulos, and Michael I. Jordan. Explicit second-order min min-max optimization methods with optimal convergence guarantee. arXiv preprint arXiv:22 12860, 2022.
[32] Chengchang Liu, Shuxian Bi, Luo Luo, and John C.S. Lui. Partial-quasi-ewtte methods: Efficient algorithms for minimax optimization problems with unbalanced dimensionality. In Proceedings of the 28th ACM SIGKDD conference on knowledge discovery and data mining. pages 1031-1041, 2022.
[33] Chengehang Liu, Chaowen Guan, Jianhao He, and John Lui. Quantum algorithms for non- smooth non-convex optimization. Advances in Neural Information Processing Systems, 37: 05288-35312, 2024.
[34] Chengehang Liu, Luo Luo, and John C.S. Lui. An enhanced Seveeberg-Marqqueee method via gram reduction. Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages 18772-18779, 2025.
[35] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Confer- ence on Learning Representations, 2018.
[36] Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. In AIS- TATS, 2020.
[37] Renato DC Monteiro and Benar F Svaiter. lterationccomplexity of newton proximal extragra- dient method for monotone variational inequalities and inclusion problems. SIAM Journal on Optimization, 22(3):914-935, 2012.
[38] Arkadi Nemirovski. Prox-method with rate of convergence o (I/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point prob- lems. SIAM Journal on Optimizution, 15(1):229-251, 2004.
[39] Yurii Nesterov. Dual extrapolation and applications to solving variational inequalities and related problems. Mathematical Programming, 109(2-3):319-344 2007.
[40] Yurii Nesterov and Laura Scrimali. Solving strongly monotone variational and quasi- variational inequalities. Discrete and Continuous Dynamical Systems, 31(4):1383-1399 2007.
[41] Guneykan Ozgul, Xiantao Li, Mehrdad Mahdavi, and Chunhao Wang. Quantum speedups for markov chain monte carlo methods with application to optimization. arXiv preprint arXiv:2504.0306 2025.
[42] Nicolas Papernot, Patrick McDaniel, Ian Goodfellow, Somesh Jha, Z Berkay Celik, and Anan- thram Swami. Practical black-box attacks against machine learning. Proceedings of the 2017 ACM Asia conference on computer and communications security, pages 506-519, 2017.
[43] Santiago Paternain, Miguel Calvo-Fullana, Luiz FO Chamon, and Alejandro Ribeiro. Safe policies for reinforcement learning via primal-dual methods. IEEE Transactions on Automatic Control, -321):132111336 2022.
12

---

[44] Leonid Denisovich Popov. A modification of the arrow-huriiz method for search of saddle points. Mathematical notes of the Academy of Sciences of the USSR, 28(5):845-84) 1980.
[45] Abdurakhmon Sadiev, Aleksandr Beznosikov, Pavel Dvurechensky, and Alexander Gasnikov. Zeroth-order algorithms for smooth saddle-point problems. In International Conference Mathematical Optimization Theory and Operations Research, pages 71-85. Springer, 2021.
[46] Aaron Sidford and Chenyi Zhang. Quantum speedups for stochastic optimization. In Thirty- seventh Conference on Neural Information Processing Systems, 2023.
[47] Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf. Convex optimiza- tion using quantum oracles. Quantum, 4:220, 2020.
[48] John Von Neumann and Oskar Morgenstern. Theory of games and economic behavior. Prince- ton university press, 2007.
[49] Hao Wang, Chenyi Zhang, and Tongyang Li. Near-optimal quantum algorithm for minimizing the maximal loss. In The Twelfth International Conference Learning Representations.
[50] Yaakov S Weinstein, MA Pravia, EM Fortunato, Seth Lloyd, and David G Cory. Implementa- tion of the quantum fourier transform. Physical review letters, 86(9); 889, 2001.
[51] Yiming Ying, Longyin Wen, and Siwei Lyu. Stochastic online AUC maximization. NIPS, 2016.
[52] Brian Hu Zhang, Blake Lemoine, and Margaret Mitchell. adversarial learning. In AIES, 2018.
Mitigating unwanted biases with
[53] Hualin Zhang and Bin Gu. Faster gradient-free methods for escaping saddle points. In The Eleventh International Conference on Learning Representations, 2022.
[54] Junyu Zhang, Mingyi Hong, and Shuzhong Zhang. On lower iteration complexity bounds for the convex concave saddle point problems. Mathematical Programming, 194(1-2)9911-935
2022.
[55] Yexin Zhang, Chenyi Zhang, Cong Fang. Liwei Wang, and Tongyang Li. Quantum algorithms and lower bounds for finite-sum optimization. arXiv preprint XXi::2406.03000 2024.
[56] Yuxin Zhang and Changpeng Shao. Quantum spectral method for gradient and hessian estima- tion. arXiv preprint arXiv:2407.03833 2024.
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]
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made 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.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
13

---

Answer: [Yes]
Justification:
We discuss them in Section 6
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in 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 au- thors 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 a few datasets or with few runs. general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the ap- proach. For example, a facial recognition algorithm may perform poorly when image resolution is low images taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proof's
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
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 theo- rems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question:
Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided not)?
Answer: [NA]
Guidelines:
The answer NA means that the paper does not include experiments.
14

---

If the paper includes experiments, a 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 the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to 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 a large language model), releasing of model checkpoint, other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution 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 re- produce the model (c.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors are welcome to describe 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 the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and
data submission guidelines for more de-
tails.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurlPS code and data submission guidelines http://iiips.ccppplliie
(CodeSubmissioooooli... for more details.
The authors should provide instructions on data access and preparation, including how to 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. 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 as possible supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
15

---

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]
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 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
Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Question:
Answer: [NA]
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 the 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 to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors 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 enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables 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 reproduce the experiments?
Question:
Answer: [NA]
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate 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 in the paper (c.g., preliminary or failed experiments that didn't i make it into the paper).
9. Code of ethics
16

---

Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics /ttngg//nrrr///rrrrrrcco/oo//o/a
Answer: [Yes]
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations 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]
Justification:
This paper focus on the theory of quantum complexities to solve minimax
problem.
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 or 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), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
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 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 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 technology is being used 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 mitiga- tion strategies (e.g., gated release of models, providing defenses addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g.. pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards quiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
allow for controlled use of the model, for example by re-
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
17

---

We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
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?
Question:
Answer: [NA]
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 used and, if possible, include URL
The name of the license (e.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 pack- age should be provided. For popular datasets, patasets.ppaperssti wwtpppppptthhaaeeeoeeep thcode com datasets has
curated licenses for some datasets. Their licensing guide can help determine the li- cense of a dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the datasct/codd/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the pa- per include the full text instructions given to participants and screenshots, if applicable, well as details about compensation (if any)?
Question:
Answer: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but the main contri- bution of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage the country of the data collector.
18

---

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 the requirements of your country or institution) were obtained?
Answer: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva-
lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to LLM policy for what should or should not be described.
A
Auxiliary Lemmas
Lemma A.l. Given a positive sequence (TITO if EED X2
C, then we have Σt- dc
7a/2
VC
Proof. By Holder's inequality, we have that
2/3
1/3
2/3
T
(27)
1/3
Σ
1
Σ
X
Ae
1=
m=/
1=
Therefore,
Σ
1
T3/2
(11)
X
VC
t=
Lemma A.2 (Lemma 4.2, 12 ). For any sequence of positive numbers fre)ezo it holds for any
m 2 2 that Em
Ei=0 Ti
< m²
2 Em-1 v?
Lemma A.3 (Lemma 4.2, [4 For any sequence of positive numbers freheo it holds for any
m that m- (Σ/=>r)) r4)
< E
19

---

B The Proof of Section
B.1 The Proof of Lemma 3.2
Proof. Running A(f, Eg. Lo, x) for times. Let (Tm) f(z) denotes the output estimates for m-th running. Then for each coordination, take the median of the output estimates, and return the resulting vector the output of QuantumGradient (f: 'g. Lu, L1 z, 5), denoted as (z).
For any E [d], m E [M], Xam denotes the indicator random variable of the event
|[ f(z) [V]())), 1500 Lideg
By Lemma 3.1 we have Pr((mm,)) 3/2 and (xm,i) Im are independent random variables. By Chernoff's bound,
5 M
Pr
X i. S
800
m=
Let Y; denote the event that Σ .M
Dm=1= Xmm 2 5 M, then Pr(V,) 2 e
18M
If Y, happens, we
have [V](u=)]; - [Vf(z)]; - 1500 / Lede By union bound, Pr(n Yi) 2 E 135
Under event n Y,, we have [[v (z(l)l2 I V1500'd Lideg 1500d LIcg. Set M O(log( )), have Pr(n Y2)
8.
Since have invoked for M times, the total query complexity is O(log())) and the total gate complexity is Od aLieg log 4) by Lemma 3.1
La
B.2 The Proof of Lemma 3.3
Proof. Let fx( and f + Δ) be the quantum gradient estimates with probability at least (1 - 8/2). By Lemma and union bound, we have
[[V / S 1500d LIEN and [V -) V + A)ll2 S 1500d LIeNv
hold with probability least 1 5. Condition this good event, we have
hv 22 fxxvvl)
[vf(x + Av) vx(x)) v²f(x)v
A
ff
Av) Vf(x + Av) 1V Vf(x)12
A
L
A
3000d Lienv
|
Since we have choose A 20 15cmv
3/4
M-10MM1222 1/2 1/2 1 1/2 it holds that
M
Pr hv V [x)vll ( 2 21-6.
(12)
B.3 The Proof of Lemma 3.5
Proof. It holds that H estimates 2 fz)e, with fallure probability 8/d, then by Lemma
H ( =] V [(z)e:||, < ( for all i i [d]
holds with probability 5. Under this event, we have
H - (- < Σ
H f(z)e,11 10V L2 1/2 (144
Therefore, we have
H H - < H - v3 vd H - v25(2)1F 10v
(eHLI) (eH
holds with probability at least - 6.
20

---

C
The Proof of Section 4
C.1
The Proof of Lemma 4.1
Proof.
The iteration rule 6 means
g+ + (2 - 2e) + de( - 21) = 0.
(13)
Thus, we have
21+1/2
(zi
1
v1)
2141/2
21
1 F(ze+1/2))
+
1
l/ve F(2++1/2)
),
X
02,t +
1
1
2t+1/2
Z, +
(g:
+ HH(Zt+1/22 2i))
+
(F(Z++1/2) -g: g: H. 21))
(F
At
Ax
15
2
ò2,r
L2]12(41/2
zel1
||: - F(z))l
Hi -FF(FF Z2+1/2 Zz
At
24
de
L2||2++1/2
zel1 1
3
di,e + +.,,llZ4411/2 2ill
d
1
22+1/2
zzll
+ 4 "+=vvo... 5
6
(14)
where the last incquality is due to the choice of A We also have that
(1z 1t-1/2 (2:- ze+11 2/t1/2 2)
X
(z1 21+1, Zc+1 - 2 + (z)- 2 Zi+1> +
(z++1/2
Zet1. 2441/22+1/2 Z(+1) (15)
$ (l|z =112- ||z++1 z|12)
1z+1/2 Z 11 |t
Since | (z: - vi)ll = ||z+ Zi+1ll ll. plugging the bound of (14 into 15 and using
the fact that live F(Z(+1/2)1 5 62.20 have
F ((244122) 2241/2 -z) + i
22-1/22 =212
1
1 A,
(Ve, 2c+1/2 - z) + |
zel1² +
(F(2411/2) Vo, 2241/2 2)
[|zz - -z|²² - 21|=-1 - z1|²)
+ 1
+ ||z =
2
1
12+1/22 - z
|11211//2
2c-111
2
122 Ze+
2011l12 11 + 02,
(16)
||zz - z||²
-1|z(41 - =1|²) +
|z1+1/2
22
2
4
1
1
1
1
| z||
2=11² 12+1/2
$1,1
1 -
-2+1/2211
82,1
2
18
8
2
dx
1
||241//2 2
$ 2 (lzz z|'
|| z|12) + 81 82,1
We let R > 10/|20 z" || and the choice of 81.t and 82, means that we have
22+1/2 z
51, + 82,1
< 61,t + 82 (2.((1211/2 20 + ||z0 - 2
X
R² + 10T 2441/2 2 |l + R) -
R + || ll
R²
10T
5T
Let z z" in 16 and due to (F (Z2z+1122 2 Zx+1/2
x²) 2 0 for all k, we have
1-1
| z¹11 11
< 12
112
Zu
z²1 12 +
61, 82,
2
A=0
21

---

and
1xx+1/2 - z²1l
R²
2R
3R
12+1/2 -Zi = =2 _
61,6 + 62,6
5
5
k=
Thus, we have
14412 - 2=1 2| 2/|1/ - zel1 + 2/|z, - 2²112 3R²
(17)
Summing up the
from 1= to 1, for all 2 E TB: (orr(z"), we have
( F((1+1/2), 2141/2 2)
12411/2 - -2:12
t=
1z++1/2 - z
(|zo z||² - || 2113) + Σ
,1, + 82
(18)
1=0
R²
Ra
TR TR 1/t+1/2
2² + || x² II)
1<
+
+
I 2RR
20
10
10T([ zoll + R)
We then bound the regularization term E"-11 X² by
T-1
T-1
36(3L
22+1/2 - 2zl1 +36 + 3))1;)
t=
3R
3R²
864L3R2
I (864L2 + 4)
T
10T
t=
Thus, we have
Gap(2r; v3R) z
max
(F(z), 2T z)
max
DT-1 1/1
Σ
(F(z).
2441/2 z)
2
12-
IISVOR
18
2R
max || 2 SVVEE Σi= 1/>e t=
1F(2--12),
2)
S
Σーー 1/>
2 864L3 + 4R3
T3/2
where the first inequality from Proposition 2.3 is due to the monotone of F(.), and the last inequality is due to ETD
73/2
according to Lemma A.
(864L3+4)RR
C.2 The Proof of Theorem 4.3
Proof. According Lemmas 3.2 and 3.5 we know that gt. H,, V. can be constructed within Ö())
(d), and (1) quantum function evaluation oracle, respectively. The following statements
R 10T
g: F(z,)) || < ||l:: 8: ff(2,))) 1500d LIcI, <
H, V2(2:)) < ||||| H. {² S 110
1/2 1/4 T.g 'H
R
<
VT
and
||v: - F(2441/2)1 S ||]|| v (5(2+11221
deti
122
< 1500d S min
10T (lIz)-1/2 Zo
R)
27
22

---

hold with probability at least (1 ))
Let ,1,
Ra
R and 82, min 107 [|2+ 2o l
A.
61
we know that the condi-
107
VT"
2
tion of Lemma holld with probability at least (1 - 8). Thus, the output Zy of A holds
that
2/ 2/86 864T2 + 4R
Gap(Zr; v3R)
S,
T3/2
with probability at least (1 6). The total query of quantum evaluation oracle can be bounded by
# Query (0(1)+ 0(1)) 011)+ T - 2/3 R²e R22-
C.3
The Proof Lemma 4.4
Proof. The iteration of 8 means
g+ H (1) 21) + Ae(z++1/2 zz)) 0.
(19)
Thus, we have
1 |
1/+1/2
21
d
)1| || 1
F F(2c+1/2)
d l|v. - -F(Z+1/22
1/21/2
Ō2,r
1
+
2x+1/2
+ d
B: + H (n(t)(Zet1/2 2,))
X
(((Z41122 - -t (2)) 2:)1 -21))
+
82.1
1
+
[[F(2+1/22 F(zz) VF (F(z:)(2+11/2 zt)l
d
+ A
(lgg: - F(z:))l
H| (t) VF (2 + +[[ (F(2,)l>) -zel)
82.1
To2 1/2
1 Ig. Flz))l
X
d H (e) VF(2 II + || - (F(2)))))(())))1111111)) - -zell
+
A
82,1
La (1|2((1) 2x 2:11/2441/2 - zell)
<
+
(122 2, 2:11 + δ1, + 8E [/rl2211/22 - zell) + X
X
A
L2
1
L2
|2++1/2
zell + /o,et +
6M ||z=(1)) zell:
6.M
4
(20)
where the last inequality is due to the choice of A On the other hand, it holds that
(Ve, 1,+1/2 z)
1
1
IIz 2|22
-||1 2|13)= +
21+1ll
2141/211
2
2
2
= |.+ 2c 11112220
211122111 2
(21)
X0
3
L3
1
(lzz 2|12
-l|z411 - 2|13)
+
81,1
1/
||z+1//2-
10a1/2222el zell
16
12M2
L3
1
1
(Z=(() z
2, 1/2
Z++1
Iz
Zt+1
1/211²
1
4
23

---

We denote r Iz++ zell, since r < 2 Z1+1/2 -zell + 2 2/|2(-1 - -zel? and that
(-1
|| (a(()) - zell =
Σ
(z++1 zi)
-
Σ
|z - -2ill
Tb
(22)
(()(()
(==(1)
i= (
then it holds that
1
(ve, 2/11 - 2) + (1)
I.2
12c41/2 zel12
12M2
L3 Ei=n(e)
(23)
361
1 2
(1ze 2|1²- ||ee z11²) +
16
8
12M2
Summing up the above inequality from = x(t) to π
(t) + -
- 1 where 1 S s S m and take
M 2
mbn
we have
v3
Σ
(V,,2411/2 - +)+ 1/11141//22 2il?
A
(=)(r)
(24)
t-1
$ (lzza()) - [112-11zx(0)+ =zl3)+ +
Σ
81,55
16
(=)())
where the last inequality is due to Lemma A.2 Combining the error from Vt, we have that
Σ
(((z41/2) 2:41/22 z)
2i41/2 - 2:113)
(=)(
Σ
V1., Zit1/2 -2) + 1/111/222 11) zill2)
Σ
F((411/2 - vill V 2/
2/41/2
)
i=x(()
(=)(()
||z, z|1 ([Zz(1) 2112-
1-1
3
01,
+
82,1
| 1,-1122- 12/1122-1
16
X;
(t)
(25)
Similar to the proof in Lemma
4.1
we let R 2 10/|20
and the choice of ő1, and 82 means
12+1/2 z²
81,1 + 82,1
< 81, + (2.((12(41/2 2oll + ||z0 - zz
d
(26)
R²
R + ||241/22 20 I)
R²
+
S
10T
10T( [07(1/241/2
20 || + R]) 57
Let z" in 25 we have
[-1
||x21/22 - x"
1|z z² 2²112 < ((x(t)) - -2"12+2 +2 Σ
61, + +022
d
k=T(1)
(27)
1-1
1 20
R²
< ||z0 -2"11 Σ
61,0 + 82
AB
2
k=0
and
12.1122 zi 24|2<4/|zzn0 ((((()
=21 +8 Σ
[-1
81 + 82,6
| -2"ll
26
2R
+
8R2
<
4R²
k=+(t)
Thus, we have
2241122 - z²11² 2|
zel1 2 + 221zz, -z'12 2 < 9R?
(28)
24

---

Summing up the batch of (25), for all z E "
we have
T
1Z 2141/22 -2)
+
Zr 1/2 zell
8
1
80,2 /2/1//2//2 2
(1|z0-
z||²
1ZT =211)
(29)
2
1=
R2
R²
TR (1 2-- 1/2 z
+ z z
+
2122.
20
10
(0T(1]21+))
zo11 + R)
We then bound the regularization term E0 X² can be bounded by
T-1
Σ
36(3M² 12+1/2 - 2:11 + +30 351,t)
T-1
3R
3R
< 432M R2
+
S (432M² + 44)2².
T
107
0=0
Finally, we have
Gap(Zr;3R)
<
2--2" 1332R
max
(F(z), žT
2|2-2"
||
1 $3/2R 2R
max
-1= 1/2
T-1
t=0
(F(z), Zt+1/2
1
T-1
27
2R
2- /3
max
Σ T-1 1/>:
A
(F(z+11/2), 21+1122 - 2
Σ 1/2c
2v 4 + 4R3
T3/2
where the last inequality is due to Lemma
C.4 The Proof of Theorem 4.5
Proof. According to Lemmas 3.2 and 3.5 we know that gr H, v, can be constructed within Ö(1)
(d), and (1) quantum function evaluation oracle, respectively and
R²
fz())l < 1500d s g F(z+)ll S J g
107
VF( & [J H V2 f(z)())) - 10v L 1/4 L
/ cH
1/4
<
R
VT
and
||: - F(2(11/2)l S [|]] v. (2(41//221
R²
S 11000d L1e1, S min 10T (1120-122 zoll + R))
27
hold with probability at least (1 4
Let 81,- = ToT
R²
R δHH = VT' and 62, = min (0 2oll +
4 2 J. we know that the con-
dition of Lemma holds with probability at least (1 6). Thus, the output 2y of Algorithm satisfies that
22432M + 4R3
Gap(žr: V3R) <
T3/2 SC.
with probability at least (1 - 8). The total number of queries to the quantum evaluation oracle can be bounded by
(1+1) o(d) . (d+ 2/3 -2/3)
# Query = Ō(1) +
m
25

---

C,5 The Proof of Lemma 4.7
Proof. We can obtain good approximation of F(z F(z; )) and (2
(x)
7(t) with probability
(x)
at least (1 - 8/5) for all i E (7 - 1]. Recalling the proof of Lemma 4.4 in Appendix C.3]
from (25)
we have
Σ (1)
1(0)
(F(z (+122)
1+1/2 1 2)
+
8
2
4+1/2
(5)
2,
1/
(30)
|| T(t)
z|2 - | (0) z1|²)
+ Σ
((0)
2.6
z|
2
16
1+1/2
(t)
holds with probability at least (1 - 6/5). Assumption 4.6 means that
(F(z)- F(z') z x²) 2 ul|z - z'1?
(31)
Let z = z in
30
we have
Σ
1+1/2 2²112 +
|| /+1/2 2. 100113
(+)
(c)
$ 2
1
(112410)
2²113 - -1z(
(*) - 2|13) +
1-1
16
5(
+
g(3)
2,3
2
14//2
(x)
z||
i=)(1)
Summing up above inequality from 0 T
1, we have
T-1
8(3)
Σ 1=0
1 - zz 2²1 +
8
1 (e)
11
1+1/2
zi
12
5 2 22
(5)
z²112
+
Σ
16
((0)
1
2.2
2
1+122
(e)
zz"
The choice of 6/ and x5 guarantees that
g(s)
3 (s)
2,
(8)
z"11 s (1
(s) =²1
16
1
1/2
Thus have
T
|z
12 = <6|22 - 2 1²
1+1/2
2,
1=0
(0
Σi-0
x
Since ((++
27
and (+)) = 20
using the convexity of || 1|2 and by Jensen's
x
inequality, we have
3
(0(+ =z11²=
zz 1²1
(32)
44 DT
T
0
x(
We then bound the term ETol(
(2(0))2 by
T
T-1
Eap'
<
36(
| 2x 11)112 + ((0 (1)2+((00))) + 30(()) - (648M² + (|2()) - -z"1 =1.
t=
t=0
Since
(100M + 12)2231122 z 11/33/
T
1//
enough to guarantee the linear decent on ||z(0) x= such that
3
1z (x) xz 21112 3 + 6 61(z(()
101
2| (++1)
2" 12 <
[z( =1.
44
>i
4//33/2
2
0-
X
26

---

C.6 The Proof of Theorem 4.8
Proof. Using Lemma have that ||z( 2=11² =112(() =111| holds for all [S 1]
with probability at least 8. Then have ||218) 2²1 - (1) ||z 11
For each call of the subroutine HAQZO*, the query complexity be bounded by
T O(d)
d=/3 L2 2/3
T. ((1 m
(
12213
Thus, the total query complexity can be bounded by
#Query = S (I 0(1+ + m
(-+ 11 Ō(d)) log(E"1) = (d 2/3 2//3//13 2/3
D
The Proof of Section 5
We first present some useful results for one step of lazy CRN
14 131
(g., 2 - z.) + (Hr 2,), x - 22) + M
Ze+1 arg min ZERd
|| z.
(33)
6
where g: and Hi(() are good estimations to ff(z)) and V2 f² respectively, such that
lg:
Vf(zz))l2 6g and H (t) ( 8H.
(34)
Lemma D.1 (Theorem 2.4 13).. Consider the cubic regularization step in 33 where gi and H.())
satisfy 34 then it holds that
[(z,) - (((+11) 2
[V
192
(35)
M
17113
17183
36
+
7+41
2e|13
||z:
2
48
M
M
M1/2
Then we know that by properly choosing 8g. ôH. the CRN step can make the gradient small with rate of (T22)/2.
Lemma D.2. Under Assumptions 2.2 let à be uniformly chosen from {2, (2 generated by then holds that
33
192 (RRMM))())) -*), + (7688/22 200 83
E 33/33)
T
M3/2
27

---

Proof. Summing up B3 from = =t(t) to t, then it holds that
f(2x(1)) f(z))
Σ
V [ (2++ (2 1)1
192M1/2
(x)((t))
M
17T11
1716
36g
Σ
[k+1
2k
1|zk 2x(001²)
Σ
48
M
M2
M1/2
(m)(())
km)(())
Σ
[
192M112
kmmm(()
Mr
1711 ( ((= r5)
Σ
1716
38 3/22
(36)
48
M
M
1112
(1)(()
k=
Σ
[ 1)1
192M11/2
(=)
M
17112
k-1
r3)3
Σ
1716
36
48(1
(1))3
M
M
M/
k==(()
j=x(()
k=m(()
1-1
1716
36 3/2
[Vf(zz+
192
M
1/
(
km)
where the last inequality is due Lemma A.3
and M 30mL2
M
17113
M
17113
2 0.
48(1 (1))3
M
144m3
M2
Summing up (36 from 0 to T - 1, we have
1716
36
3/2
f(z0) - 1x f(z0) ((ZT) >
V [[(( -T
192M
M2
M1/2
and
T
192 (ff(za) - -f¹).
200
E [
[V(()+1)
+
57653/2 3/2
T
M/32
Now are ready to prove Theorem 5.2
D.I The Proof Theorem 5.2
Proof. The choice of &g and means that
c-1
Ig: vf((z)) 17282/3 := 8g
M1/2
H.) 42 f( <
8H1
30
hold with probability at least (1 - 8) for all t [T]. Using Lemma D.2 we have
E
| (2 3//2]]
S -3/2 3/2
28

---

due to the convexity of 29/2, we have
(Zom) Zow )13/2] 2/3 Se
E [ - B
|| V
We require using (1) query complexity of function evaluation oracle to construct the gradient estimator for all iterations and using (dd) query complexity to construct the Hessian estimator for -t + 1 iterations at the snapshot point. Thus, the total query complexity of Algorithm O can be m bounded by
#Query = - + [ + a Ō(d)) Ö (d+ 1 (f(o)) f)z
29


Reviews:
[{"review_id": "MZ0FC1Ndrg", "reviewer": "Reviewer_mnz2", "summary": "This paper studies dimension-dependent quantum algorithms for convex-concave minimax optimization, assuming access to a quantum function value oracle. Classically, the problem can be solved using $O(d/\\epsilon)$ queries to a classical oracle. In contrast, the proposed quantum algorithm achieves a query complexity of $O(d + d^{2/3}\\epsilon^{-2/3})$, yielding an improvement of order $d^{1/3}\\epsilon^{-1/3}$. Additionally, for the strongly convex--strongly concave case, the authors present an algorithm with a query complexity improvement of order $d^{1/3}\\mu^{-1/3}$. The techniques are further extended to the non-convex setting, where the objective is to find an $\\epsilon$-stationary point.\n\nTechnically, this paper introduces quantum algorithms for estimating the Hessian-vector product and the Hessian of the objective function. These techniques are used as subroutines in the main algorithm, which maintains an estimate of the Hessian and performs approximate Newton updates. In particular, the Hessian estimate is updated using a lazy updating framework. The algorithm for finding stationary points of a non-convex function follows a similar high-level approach.", "questions": "1. For every quantum algorithm in this paper, can we have a corresponding classical algorithm with first-order input that achieves the same query complexity, using basically the same algorithms? \n2. Can we have dimension-independent quantum algorithms using an evaluation oracle? If so, can we design algorithms whose complexity interpolate between this dimension-independent bound and the bounds obtained in this paper?\n3. For the dimension dependent non-convex optimization setting, there is a more recent paper \"Improved Complexity for Smooth Nonconvex Optimization: A Two-Level Online Learning Approach with Quasi-Newton Methods\" that might be worth discussing.", "limitations": "yes", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths: \n1. This paper is the first to discuss quantum speedups for convex-concave minimax optimization problem with function value access.\n2. The paper is well-written, and the proofs are presented clearly.\n3. The analysis of the lazy Hessian algorithm (Algorithm 4) is interesting and may be of independent interest\n\nWeaknesses:\n1. The query complexity bounds are not written in a very precise way, it should be $d+\\cdots$, since at the beginning of the algorithm you need $d$ queries to compute the full Hessian. Omitting it is inaccurate.\n2. The algorithms for estimating the Hessian-vector product and the full Hessian appear to be, to some extent, relatively straightforward applications of Jordan’s gradient estimation algorithm.", "was_revised": true, "final_justification": "The authors have addressed my concerns so I updated my score.", "rebuttal": "Thanks for your helpful comments.\n\n## To weakness 1:\n\nThanks for pointing out this, we will update the query complexity of HAQZO+ (Algorithm 4), Restart-HAQZO+, and QCNM to $\\mathcal{O}(d+d^{2/3}\\epsilon^{-2/3})$, $\\mathcal{O}(d+d^{2/3}(L_2/\\mu)^{2/3})$, and $\\mathcal{O}(d+d^{1/2}\\epsilon^{-3/2})$ respectively.  The $\\mathcal{O}(d)$ factor is only an addition term and can be omitted when $d$ is small ($d\\leq \\epsilon^{-2}$ for convex-concave problem and $d\\leq \\epsilon^{-3}$ for non-convex problem).\n\n## To weakness 2:\n\nWe agree that our algorithm for estimating the Hessian-vector and full Hessian is an application of Jordan’s gradient estimation. However, we kindly disagree that this impacts the contribution of this work.\n\nThere are no analytical results for estimating the Hessian by quantum function value oracles before. Our work is the first to study the query complexity for estimating the Hessian with an arbitrary desired accuracy $\\epsilon$. We believe these oracles perform important roles in quantum optimization.\n\nIn addition, our contribution is not limited to the construction of quantum Hessian evaluation oracles, but also lies on how to efficiently use such oracles to demonstrate over classical algorithms and the existing quantum algorithms (please refer to our answer to question 1). \n\n## To question 1:\n\nFor the minimization problem, the complexity of QCNM aligns with the complexity of First-order CNM in [11].\n\nFor the minimax problem, **there are no corresponding classical algorithms with first-order input that achieve the same query complexity**. Unlike FO-CRN [11] for non-convex optimization, our algorithms (HAQZO, HAQZO+) conduct an extra-gradient step, which incurs additional error from the inexact gradient. This require both novel algorithm design, i.e, the choice of the regularziation term $\\lambda_t$, and careful analysis to control the error from the gradient and Hessian estimator. To the best-of-our-knowledge, such Hessian-aware algorithms with zeroth-order or first-order oracles have not been considered under classical settings before.\n\n## To question 2:\n\nThere are no dimension-independent quantum algorithms for minimax problems with a function value oracle. It is possible to design a dimention-free quantum algorithm for minimax problems by using an evaluation oracle on extra-gradient method or optimistic gradient descent ascent method. It is also a very interesting future work to design algorithms with complexity interpolate between dimension-free algorithm and HAQZO/HAQZO+.\n\n## To question 3:\n\nThanks for pointing out the paper. We did not discuss this paper in the current version because we focus on the results for both classical and quantum algorithms with zeroth-order oracles (in Table 3), while this recent paper uses the first-order oracle. We will discuss it in the revision."}, {"review_id": "XzXo3Y7nJK", "reviewer": "Reviewer_iyXU", "summary": "This paper investigates quantum algorithms for convex-concave minimax optimization problems with access to a quantum zeroth-order oracle only. By combining a novel quantum Hessian vector estimator (based on the quantum gradient estimation subroutine) with existing classical (stochastic) second-order methods, such as Newton proximal extragradient, the proposed quantum algorithm achieves an improvement of $d^{1/3}\\epsilon^{-1/3}$ over best-known classical counterparts. Application of the quantum Hessian estimator to non-convex optimization problems also achieves polynomial improvement in the query complexity compared to classical methods.", "questions": "Technical questions:\n- How is the inexact cubic step in Algorithm 3 computed? If this step is performed purely classically, how can we expect any **genuine** quantum speedup, given that representing the Hessian as a classical array may already negate the quantum advantage gained from the Hessian estimation?\n- The classical algorithms for convex-concave minimax optimization problems are already very good (with a provable query upper bound that is sublinear in both $d$ and $1/\\epsilon$). In what parameter regime would we expect practical quantum advantage? Is it possible to have large (i.e., super-quadratic) quantum speedups?\n- Lemma 4.1: Is the Gap() defined anywhere? I do not find it near the lemma, and it is not directly clear to me how this gap is defined.\n\nMinor typos/formatting issues:\n- Line 24: \"When ... is Lipschitz continuous, second-order offers faster convergence rates.\" A word like \"method\" or \"algorithm\" is missing after \"second-order\".\n- Line 29: the h(\\cdot, \\cdot) is not in the mathematical italic format.\n- Line 57: There should be a space between the big-O notation and \"complexity\". \n- Theorem 5.2: what does the $\\Delta$ symbol mean in the in-line math equation: $f^* \\Delta \\min_{x\\in \\mathbb{R}^d}$?", "limitations": "– The main technical contribution (quantum Hessian estimation via a zeroth-order oracle) is relatively straightforward and appears to offer only limited benefit when integrated into a classical algorithm.\n– The quantum speedups achieved are modest compared to classical baselines, and it remains unclear whether these would translate into a meaningful practical advantage once classical computation and post-processing overheads are accounted for.", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The Hessian-vector estimation subroutine is a novel technical contribution that can potentially accelerate other classical (second-order) optimization/minimax algorithms.\n- The theoretical analysis appears complete and solid, with a comprehensive comparison with prior art in Tables 1-3. \n- Extension to non-convex optimization problems is discussed, complementing the discussion on minimax optimization and showcasing the usefulness of the quantum Hessian estimation.\n\nWeaknesses:\n- While the Hessian-vector and Hessian estimation subroutines (Algorithms 1 & 2) appear original and have not been formally analyzed in previous work, they are quite straightforward extensions of the quantum gradient estimators (Lemma 3.2) relying on a standard 2-point estimation technique (e.g., finite difference). \n- While the quantum Hessian estimation subroutine seems to achieve an improvement of $d$ over classical algorithms, the achieved speedups for minimax optimization in terms of quantum queries (Theorem 4.2, 4.4) are quite limited. \n- The quantum advantage is formulated using query complexity. However, in Algorithms 3 and 4, it is still required to find an inexact cubic step using classical methods (e.g., solving linear systems). It is unclear if this algorithm achieves meaningful end-to-end quantum speedups.\n- Besides, there are several obvious typos/formatting issues in this submission, see the questions below.", "was_revised": true, "final_justification": "See the comment for the authors.", "rebuttal": "Thanks for your helpful comments.\n\n## To weakness 1:\n\nOur algorithm for estimating the Hessian-vector and full Hessian is an application of Jordan’s gradient estimation. However, we kindly disagree that this impacts the contribution of this work.\n\nThere are no analytical results for estimating the Hessian by quantum function value oracles before. Our work is the first to study the query complexity for estimating the Hessian with an arbitrary desired accuracy $\\epsilon$. We believe these oracles perform important roles in quantum optimization.\n\nIn addition, our contribution is not limited to the construction of quantum Hessian evaluation oracles, but also lies on how to efficiently use such oracles to demonstrate over classical algorithms and the existing quantum algorithms (please refer to our response to limitation 1). \n\n## To weakness 2:\n\nThe state-of-the-art classical algorithm requires  $\\mathcal{O}(d\\epsilon^{-1})$  queries to find an $\\epsilon$-saddle point, exhibiting a complexity that is linear in both $d$ and $\\epsilon^{-1}$. In contrast, our algorithm (HAQZO+, Algorithm 4) can solve this problem with a query complexity that is **sublinear** in both $d$ and $\\epsilon^{-1}$. \n\nA crucial contribution of our work is that the quantum speedup is achieved with respect to **both** $d$ and $\\epsilon^{-1}$. This marks a significant advance, as previous quantum works in this area typically only provide speedups in the dimension $d$. We therefore believe our work offers a key conceptual contribution beyond the concrete improvement in query complexity.\n\n## To weakness 3 and question 1\n\nWe consider the case where the query complexity dominates the computation complexity of the algorithm, which is a natural setting in both classical and quantum optimization. For example, considering the generalized linear model such that  $f(x)=h(A^{\\top}x)$ where $A\\in R^{d\\times n}$, the complexity of one query is at least $nd$, which can be much larger than the gate complexity if $n\\gg d$. Our algorithm achieves meaningful quantum speedups under such a setting, typically when the dimension is not too large.\n\nThe inexact cubic step is indeed computed classically. This is permissible as any classical computation can, in principle, be performed on a quantum computer. The quantum speedup we present is **not negated** by this classical step. The primary computational bottleneck in many applications is the function value query, especially when the function evaluation is handled by a complex subroutine. In such scenarios, query complexity serves as a crucial proxy for overall computational efficiency.\n\n**Furthermore, we respectfully disagree with the assertion that the presence of classical computation steps precludes a \"genuine\" quantum speedup.** For example, fundamental arithmetic operations, such as addition and multiplication, do not have quantum speedups. These operations are essentially performed classically within quantum algorithms. However, invoking classical arithmetic operations in quantum algorithms is not recognized as weakening the quantum speedup in general. Our position is that quantum advantage can be assessed based on the query complexity for the specific problem at hand. The optimization of the computational aspects, separate from the queries, falls within the domain of quantum compilation and quantum circuit design. \n\n## To question 2:\n\nWe first respectfully point out that the state-of-the-art classical algorithm takes $\\mathcal{O}(d\\epsilon^{-1})$ query complexity to find the $\\epsilon$-saddle point, **which is linear in both $d$ and $\\epsilon^{-1}$**.\n\nOur results demonstrate a query complexity of $\\mathcal{O}(d+d^{2/3}\\epsilon^{-2/3})$, which improve the dependency on both $d$ and $\\epsilon^{-1}$ from **linear** to **sublinear.** This means that **our algorithm always has a quantum advantage over classical algorithms.**\n\nIt is a very interesting future work to show larger quantum speedups, and we believe that the quantum Hessian oracle given in this work is important to achieve this. \n\n## To question 3:\n\nThe Gap() function is defined in Definition 1 (line 104-lin 107), we will emphasize this in the revision.\n\n## To minor typos/formatting issues:\n\nThanks for your careful review, we will modify them in the revision.\n\nThe $f^{\\*}$ defined in line 244 should be modified to $f\\^*\\triangleq \\min\\_{z}f(z)$.\n\n## To limitation 1:\n\nWe kindly argue that our technical contribution is limited and would like to emphasize the parts that the reviewer may have overlooked.\n\nFirstly, our algorithms for solving minimax problems are novel. **Directly integrating the quantum estimation into the classical algorithms leads to additional errors from the inexact gradient/Hessian oracles and the extra-gradient step.** We overcome this issue by adjusting the regularization term $\\lambda_t$ and carefully setting the quantum estimation error. To the best-of-our-knowledge, even under classical settings, there are no results that allow the inexactness in both gradient and Hessian to solve the minimax problems.\n\nSecondly, the quantum Hessian estimation is a natural generalization of Jordan’s gradient estimation method and offers important oracles in quantum optimization. It can not only provide quantum speedup over classical algorithms, but also further accelerates the quantum algorithms. Fot example, our proposed QCNM method demonstrated a further acceleration upon the state-of-the-art quantum algorithms when $d\\leq \\epsilon^{-1/4}$.\n\n \n\n## To limitation 2:\n\nPlease refer to our response to weakness 2 and question 2."}, {"review_id": "C4hT8fhqWT", "reviewer": "Reviewer_77Pf", "summary": "This work studies quantum algorithms for zeroth order optimization problems, and specifically, for the minimax problem. The authors introduce a class of Hessian-aware quantum zeroth-order methods that achieve speedups over classical methods in terms of query complexity to the function value oracle.", "questions": "Typos:\n- Line 136: exits -> exists;\n\nThe writing could be improved. Many theorem statements has grammar mistakes.\n\nCould the authors give more explanations about the novelty of their paper? As far as I can see, the quantum Hessian estimation is a direct application of the quantum gradient estimation method. Whether the method is optimal or not still needs discussion.", "limitations": "The work fails to give lower bounds for query complexity of quantum algorithms in the problem setting, leaving the optimality of their algorithms as an open question.\nThe method of estimating the Hessian matrix seems to be a direct application of quantum gradient estimation, which might not be so novel.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strength:\n\n- The paper has proposed new quantum zeroth order optimization algorithms, with provable speedups in query complexity than classical algorithms.\n- The paper has given new quantum algorithms for estimating the Hessian matrix.\n\nWeakness:\n\n- The acceleration in query complexity of the methods are modest, less than quadratic.\n- In the quantum gradient and Hessian estimation, the gate complexity is similar to the one in the classical case. Therefore, I guess the reason why focusing on the query complexity should be clearly explained with examples.\n- The work fails to give lower bounds for query complexity of quantum algorithms in the problem setting.", "was_revised": true, "final_justification": "Issues solved: \n- I was previously concerned about the main technical novelties of the paper, as the quantum gradient estimation and Hessian estimation has already been discussed in previous literatures like [Jor05, GAW19, ZS24]. After the rebuttal, and especially seeing the discussions between Reviewer mnz2 and authors, I think that a main novelty lies in developing a new ``inexact'' classical gradient-based optimization algorithm with better performance, and the classical framework cooperates well with quantum subroutines. \n\n- Another point that has been clarified is the query complexity part. The authors has claimed that $\\mathcal{O}(d+d^{1/2}\\epsilon^{-3/2})=\\mathcal{O}(d^{1/2}\\epsilon^{-3/2})$. I think the additive term $\\mathcal{O}(d)$ should not be omitted in the main theorem.\n\nIssues remain unresolved:\n- Computational complexity of their algorithms, which is also considered by Reviewer iyXU. Although the authors have provided certain examples about why query complexity could be a dominant term, I am still unclear about the overall time complexity of their algorithms, and the resources needed (like the number of qubits, number of gates, and depth of the circuit, et.c.). I think explicilty showing the computational complexity of the algorithms is rather important for quantum algorithms, and will help us better understand when quantum could provide end-to-end speedups.\n\n- Novelty for quantum algorithm design. Although the authors have made progress in designing quantum gradient and Hessian estimation, I feel their work in this aspect incremental. It may not be so inspiring for quantum people to design new quantum algorithms based on their work.", "rebuttal": "Thanks for your helpful comments.\n\n## To weakness 1:\n\nFor convex-concave minimax problems, the state-of-the-art classical algorithm requires  $\\mathcal{O}(d\\epsilon^{-1})$  queries to find an $\\epsilon$-saddle point, exhibiting a complexity that is linear in both $d$ and $\\epsilon^{-1}$. In contrast, our algorithm (HAQZO+, Algorithm 4) can solve this problem with a query complexity that is **sublinear** in both $d$ and $\\epsilon^{-1}$. \n\nFor non-convex minimization problems, our algorithm (QCNM, Algorithm 6) with query complexity of $\\mathcal{O}(d+d^{1/2}\\epsilon^{-3/2})$demonstrates  **at least a quadratic speedup on the dependency of dimension** upon the prior zeroth-order cubic-regularized-Newton methods $\\mathcal{O}(d^2+d^{3/2}\\epsilon^{-3/2})$.\n\n## To weakness 2:\n\nWe consider the case where the query complexity dominates the computation complexity of the algorithm, which is a natural setting in both classical and quantum optimization. For example, considering the generalized linear model such that  $f(x)=h(A^{\\top}x)$ where $A\\in R^{d\\times n}$, the complexity of one query is at least $nd$, which can be much larger than the gate complexity if $n\\gg d$. Our algorithm achieves meaningful quantum speedups under such a setting, typically when the dimension is not too large.\n\n## To weakness 3:\n\nFor the convex-concave minimax problems, the lower bound for zeroth-order algorithms are even unknown for classical algorithms. \n\nFor the non-convex minimization problems, some negative results claim that there are no-quantum speed-up for higher-order methods when the dimension is large [A], i.e. the best dependency is $\\epsilon^{-2/3}$ even for algorithms with second-order oracles. The lower bound for $d$ is also  unknown even for classicla algorithms.\n\nWe will discuss this in our revision and leave it as an interesting future work.\n\n[A]. Quantum Lower Bounds for Finding Stationary Points of Nonconvex Functions. ICML, 2023.\n\n## To Question 1 (typos and writing)：\n\nThanks for pointing out this, we will modify them in the revision.\n\n## To Question 2:\n\nWe give explanations about the novelty in this paper below.\n\nFrom the quantum mechanism perspective, we give the first analytitcal results on the query complexity for estimating Hessian-vector products and Hessian with an arbitrary desired accuracy $\\epsilon$, which are important oracles in quantum optimization.\n\nBesides the above, **we emphasize that another important contribution of our paper is that our algorithm is the first one to allow both inexactness of Hessian and gradient oracles to solve the minimax problems**, which is more general than the prior classical Hessian-aware algorithm frameworks [9, 27]. To achieve this, our algorithm requires novel design on the regularization term $\\lambda_t$ and techniques to bound the errors from both quantum gradient and Hessian estimations. \n\nFrom the perspective of theoretical results, our algorithm demonstrates quantum speedup on general (strongly)-convex-(strongly)-concave minimax problems. Furthermore, the idea of accelerating classical algorithms by quantum Hessian estimation is new to quantum optimization, which is of independent research interest and can be used to solve other optimization problems. For example, the presented QCNM (Algorithm 6) is even faster than existing quantum algorithms when $d\\leq \\epsilon^{-1/4}$ for non-convex problems.\n\n## To limitations:\n\nPlease refer to our response to weakness 3 and question 2 respectively."}, {"review_id": "ckSz5wgxDG", "reviewer": "Reviewer_eEJb", "summary": "The authors provide a method for solving $\\epsilon$ min-max problems using a zeroth order quantum method that approximates Hessians.  Their algorithm claims a lower query complexity than previous work, improving upon previously known classical methods by a factor of $d^{1/3} \\epsilon^{1/3}$ for convex-concave problems, and $d^{1/3} \\mu^{1/3}$ for strongly convex-concave problems, where $d$  is the dimension of the domain, $\\epsilon$ is the error in the saddle point estimate, and $\\mu$ is the coefficient determining the strength of the strongly concave-convex problems.  The method relies on an oracle which computes function evaluations for a function $f$, which is convex in the first variable and concave in the second variable, as well as Lipschitz continuity in the 0th, 1st, and 2nd derivatives.", "questions": "How well does this method generalize to functions with degenerate saddle points? \n\nHow will the oracle implementation effect the performance of this algorithm?  It strikes me that the algorithm scales with $d^{2/3}$, but just loading the problem would take at least $d$, which could limit your performance.  Is this a limitation?\n\n$x$ and $y$ are said to be real valued, but it is not obvious to me how you would embed real-valued, rather than simply natural valued inputs (i.e. a linear combination over the computational basis).  Does this restriction on your input $x$ and $y$ values pose a problem for your algorithm or is there an amplitude embedding, etc. that avoids this issue (or is it a non-issue)?", "limitations": "It is unclear how generally applicable this method is to real world problem instances.  They claim that these types of problems are important for \"fairness aware learning, AUC maximization, robust optimization, game theory, and reinforcement learning,\" but it is unclear to me what problem scales of these problems become relevant.  This is important, since as was shown in M. Beverland, 2022 (https://arxiv.org/abs/2211.07629), scaling advantages that are sub-quadratic are unlikely to be practically realizable on currently considered quantum hardware.  Again, this is a theory paper, so this limitation is not particularly major in the context of this work, but it is a practical limitation nonetheless.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "The paper is very technically solid, and the appendices go into strong detail about many of the derivations.  They do a good job of listing the core assumptions of their method as well as providing very detailed appendices outlining the derivation of their key lemmas.  That said, the overall readability of the main text is somewhat difficult to follow - most likely due to the page limit.  I would have liked it if they referred readers to the appendices for proofs of their key points in the main text to make it easier to follow where some of the bounds were coming from.  It was also somewhat unclear how viable this method would be to implement on a fault tolerant computer, as hidden overheads in the oracle embedding or mapping onto hardware for general functions is not clear.  That said, this was a theory paper, and those types of concerns are beyond the scope of this work.  There was nothing overall wrong technically with their paper, as far far as I could tell, and it provides a good theoretical foundation for further work in the future.  Therefore I believe that the paper should be accepted.", "was_revised": true, "final_justification": "Upon reading their responses and giving another look through of the paper, I improved their clarity score.  The material is just dense - it is not poorly written.  My overall score remains at accept.  This is a solid paper in my mind.", "rebuttal": "Thanks for your helpful comments and recognition in our work.\n\n## To question 1:\n\nThis method can indeed solve the minimax problems with degenerate saddle point. Both Theorem 4.2 and Theorem 4.4 require only convex-concave assumptions on the objective, which allows the existence of degenerate saddle point.\n\n## To question 2:\n\nThanks for pointing this out, loading this problem takes $\\mathcal{O}(d)$, but only at a very few iterations. The total query complexity is $\\mathcal{O}(d+d^{2/3}\\epsilon^{-2/3})$ where the $\\mathcal{O}(d)$ factor is only an addition term and can be omitted when $d$ is small $(d\\leq \\epsilon^{-2})$.\n\n## To question 3:\nWe do not use amplitude encoding for the real-valued inputs. Instead, we encode these values into the computational basis using a fixed-precision binary representation, analogous to how floating-point numbers are handled in classical computing.\n\nThis approach is standard in the analysis of quantum algorithms, just as it is for classical algorithms designed for classical electronic computers. Classical computers also operate on finite-precision representations of real numbers. Notice that, we assume that the value oracle of $f$ has an error $\\epsilon_0$, which is intended to account for such sources of imprecision, including the truncation errors that arise from this finite-precision encoding.\n\nFor the sake of clarity and notational convenience, we present our analysis assuming the optimization occurs over the real numbers. This is also a common practice in the quantum optimization literature, with the implicit understanding that any practical implementation would rely on a suitable finite-precision encoding. This simplification does not pose a problem for the validity of our algorithm."}, {"review_id": "QF1I3IqICt", "reviewer": "Reviewer_iZ6K", "summary": "The paper tackles convex–concave minimax optimization with only zeroth-order (function-value) access by introducing Hessian-aware quantum zeroth-order algorithms that use fast quantum estimators requiring $\\tilde O(1)$ gradient and $\\tilde{O}(d)$ Hessian queries. The main scheme, HAQZO, achieves query complexity $\\tilde{O}(d\\epsilon^{-2/3})$, while a double-loop variant, HAQZO+, improves this to $\\tilde{O}(d^{2/3}\\epsilon^{-2/3})$, surpassing the classical $\\tilde{O}(d\\epsilon^{-1})$ rate. For $\\mu$-strongly-convex–strongly-concave games, a restarted method reaches $\\tilde{O}(d^{2/3}(L_2/\\mu)^{2/3})$ queries. Extending to non-convex problems, a Quantum Cubic-Regularised Newton Method (QCNM) finds $\\epsilon$-stationary points in $\\tilde{O}(d^{1/2}\\epsilon^{-3/2})$ oracle calls. These complexities establish quantum speedups for gradient-free optimization convex, strongly-convex, and non-convex settings.", "questions": "I hope the authors can respond and address my minor comment in the Strengths And Weaknesses part.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "From my perspective, this is a technically solid work providing quantum algorithms with provably better performance for minimax optimization over best-known classical counterparts given queries to only zero-th order queries to the function. As far as I know, this is the first work that provides quantum algorithms that outperform classical algorithms in all settings of minimax optimization given queries to either function value or gradients. In addition, the result is not a direct application of the well-known quantum gradient estimation algorithm. Instead, improved quantum Hessian-vector estimator and Hessian estimator are proposed with better performance than the best-known classical counterparts. Therefore, I am happy to vote for acceptance of this paper at NeurIPS 2025.\n\nThe weakness of this paper, if I have to provide one, is that this work provides no understanding of whether the query complexity achieved by HAQZO+ or restart-HAOZO+ is optimal in certain parameter regimes. This is also mentioned by the authors in the conclusion. However, I believe the contribution of this work by proposing the quantum algorithm with a provable quantum advantage is already significant enough.\n\nBesides, a minor comment is that I believe the overall presentation of the work can be significantly improved by adding a more detailed literature review regarding classical minimax optimization in different settings, including (strong) convex-(strong) concave functions, non-convex-(strong) concave functions, zeroth-order queries, first-order queries, etc.", "was_revised": true, "final_justification": "This is a technically solid work providing quantum algorithms with provably better performance for minimax optimization over best-known classical counterparts given queries to only zero-th order queries to the function. As far as I know, this is the first work that provides quantum algorithms that outperform classical algorithms in all settings of minimax optimization given queries to either function value or gradients. In addition, the result is not a direct application of the well-known quantum gradient estimation algorithm. Instead, improved quantum Hessian-vector estimator and Hessian estimator are proposed with better performance than the best-known classical counterparts. Besides improving upon Jordan's algorithm to obtain a quantum Hessian estimator, I also find the part of inserting the lazy Hessian technique from classical literature to reduce the $d$ dependence very interesting and technically involved. Therefore, I am happy to vote for acceptance of this paper at NeurIPS 2025.", "rebuttal": "Thanks for your helpful comments and recognition on our work.\n\n## To weakness 1:\n\nFor the convex-concave minimax problems, the lower bound for zeroth-order algorithms are even unknown for classical algorithms. \n\nFor the non-convex minimization problems, some negative results claim that there is no quantum speed-up for higher-order methods when the dimension is large, i.e. the best dependency is $\\epsilon^{-2/3}$ even with second-order oracles. The lower bound for this is also unknown even for classical algorithms.\n\nWe will discuss this in our revision and leave it as an interesting future work.\n\n## To weakness 2:\n\nWe will add a more detailed literature review regarding classical minimax optimization in the revision."}]

Author rebuttal:

Meta-review: This paper studied quantum algorithms for minimax optimization. In particular, this paper gave a quantum zeroth-order algorithm that can find an eps-saddle point within ~O(d+d^{2/3}eps^{-2/3}) function value oracle calls, improving over the O(d*eps^{-1}) classical upper bound of classical zeroth-order methods. A similar result was obtained when strong convexity and concavity present.

Reviewers found the technical results interesting. Nevertheless, some concerns are raised, in particular the time complexity of the algorithm, contribution on the quantum Hessian estimator, and other minor points. There were adequate discussions during the rebuttal, and the reviewers found the answers from authors convincing. In all, considering the overall contribution and positive scores, the decision is to accept this paper in NeurIPS 2025.

Nevertheless, for the final version of the paper, the authors should consider implementing the following changes from reviewer-author discussions as well as some suggestions from AC:
- In the complexity bounds, add the extra linear term in d where appropriate, as pointed out by reviewer mnz2.
- The authors should polish the storyline following the discussion with Reviewer mnz2. In particular, it is more appropriate to tune down quantum Hessian estimation and emphasize more on the analysis of involving both the inexactness of gradient and Hessian.
- The authors should add more discussion about the gate complexity of the proposed quantum algorithm and when it achieves a genuine quantum speedup. A starting point can be the paragraph "We consider the case where the query complexity dominates the computation complexity of the algorithm, which is a natural setting in both classical and quantum optimization… Our algorithm achieves meaningful quantum speedups under such a setting, typically when the dimension is not too large" in rebuttal.
- Regarding quantum Hessian estimation, the authors should also cite the [ZS24] paper mentioned by Reviewer 77Pf, titled "Quantum spectral method for gradient and Hessian estimation", and make a comparison with their bounds and techniques.
- Other minor points promised in rebuttals.
Decision: Accept (poster)