Hadamard Test is Sufficient for Efficient Quantum Gradient Estimation with Lie Algebraic Symmetries
Authors: Mohsen Heidari
Masih Mozakka
Wojciech Szpankowski
Venue: NeurIPS 2025 poster ()
Keywords: quantum machine learning
sample complexity
Lie algebras
shadow tomography
Primary area: theory
TL;DR: A new framework for efficient gradient estimation using the Lie algebraic structures and the Hadamard test.

Abstract: Gradient estimation is a central challenge in training parameterized quantum circuits ( PQCs) for hybrid quantum-classical optimization and learning problems. This difficulty arises from several factors,  including the exponential dimensionality of the Hilbert spaces and the information loss in quantum measurements.  Existing estimators, such as finite difference and the parameter shift rule, often fail to adequately address these challenges for certain classes of PQCs. In this work, we propose a novel gradient estimation framework that leverages the underlying Lie algebraic structure of PQCs, combined with the Hadamard test. By analyzing the differential of the matrix exponential in Lie algebras, we derive an expression for the gradient as a linear combination of expectation values obtained via Hadamard tests. The coefficients in this decomposition depend solely on the circuit's parameterization and can be computed efficiently. Also, these expectation values can be estimated using state-of-the-art shadow tomography techniques. Our approach enables efficient gradient estimation, requiring a number of measurement shots that scales logarithmically with the number of parameters, and with polynomial classical and quantum time. This is an exponential reduction in the measurement cost and a polynomial speed-up in time compared to existing works.

Hadamard Test is Sufficient for Efficient Quantum Gradient Estimation with Lie Algebraic Symmetries
Mohsen Heidari",
Masih Mozakka', CCoo,, Purdue University
Wojciech Szpankowski
Indiana University
$Jagiellonian University
Abstract
Gradient estimation is central challenge in training parameterized quantum cir- cuits (PQCs) for hybrid quantum-classin optimization and learning problems. This difficuuty arises from several factors, including the exponential dimension- ality of the Hilbert spaces and the information loss in quantum measurements. Existing estimators, such finite difference and the parameter shift rule, often fail to adequately address these challenges for certain classes of PQCs. In this work, propose novel gradient estimation framework that leverages the un- derlying Lie algebraic structure of PQCs, combined with the Hadamard test. By analyzing the differential of the matrix exponential in Lie algebras, derive expression for the gradient as a linear combination of expectation values obtained via Hadamard tests. The coefficients in this decomposition depend solely on the circuit's 's parameterization and can be computed efficiently. Furthermore, these expectation values can be estimated using state-of-the-art shadow tomography techniques. Our approach enables efficient gradient estimation, requiring number of measurement shots that scales logarithmically with the number of parameters, and with polynomial classical and quantum time. This is an exponential reduction in the measurement cost and polynomial speed-up in time compared existing works.
Introduction
Hybrid quantum-classicae strategies have emerged as a leading approach for quantum optimization and learning [BLSF19, CAB 21], and have been extensively studied across broad range of domains, including optimization [FGG14], quantum chemistry [JEM 19, AWGP21, GEBM19, DAJ 21]. and quantum machine learning from classical and quantum data [FN18, SK19, MNKFI8, LW 18, HCT+ 19, HPS21, HS24, HS23, HBM 21]. Variational quantum algorithm (VQA) particularly has been a promising paradigm for quantum learning and inference, where PQC (a.k.a ansatz) is trained in classical-gue -uuattul loop. Gradient-bart based training methods have gained significant attention in the literature [HN21, SWM+20, SBG+ 18, FGG14, FN18, SK 19, MNKF18 8] and have demonstrated significant advantages in convergence rates compared gradient-fres methods.
However, estimation of the gradient can be computationally challenging due to several factors including the exponential dimensionality of the Hilbert spaces, the no-cloning, information loss of quantum measurements, and non-commutativity of Hamiltonian terms. Therefore, each gradient estimation can have an exponential sample complexity leading high overhead and hence bottleneck for the scalability of gradient-based VQAs.
Several approaches have been introduced estimate the gradient [FN18, MNKF18, SWM+20 HGS22, HN21, SBG* 18, MKF19, W SKP24]; but they often yield suboptimal gradient circuits for certain PQCs. Methods based finite differences evaluate the objective function in
"Corespooning author. Email: mheidar@iu.edu
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

the neighborhood of the parameters. They can be applied to general POCs, but suffer from a slow convergence rate [HN21]. The well-known parameter shift rule (PSR) [SBG* 18. MNKF18] relies on the Hadamard test with Pauli operators to estimate the partial derivatives. The Hadamard test is an efficient method that directly measures the partial derivatives and does not have the numerical instability of indirect methods such as finite differences. However, PSR with Hadamard test is restricted to ansätze with two distinct eigenvalues. It can be adapted for more complex circuits via backpropagation, but it comes with high computational costs in terms of gate decomposition. Other existing methods often apply to more general circuits but have high overhead due to the extensive use of the ansatz with repeated measurements, and exponential classical computation [BC21, WIWL22, The23].
Lie algebraic structures in PQCs have been increasingly important in analysis and design of hybrid chantum-classical strategies. Ansätze that have dynamical Lie algebra (DLA) with polynomial dimensionality may not exhibit any Barren plateaus, which are flat regions in the parameter landscape (CSV+21, FHC+23, MBS+ 18]. Moreover, such Lie algebraic symmetries have be used for classical simulation of quantum models [GLC+23]. In this work, we build upon the Lie algebraic characteri- zations and we develop an efficient gradient estimation for general circuits based on the Hadamard test followed by post-processing steps. With that, we enable efficient applicability of the Hadamard test to generic PQCs without the need to change the ansatz structure and with low classical overhead.
1.1 Summary of The Main Results
We analytically derive an explicit expression for the gradient of generic PQCs in terms of the expectation values of the Hadamard tests corresponding to a certain set of Pauli strings. Then, develop a gradient estimation method using a series of Hadamard tests at the output of the ansatz followed by classical post-processing techniques including classical shadow tomography (CST) [HKP20). A generic PQC on n qubits can be represented as U d e'A(&), where A is the parameterized Hamiltonian with d' = (01. : ap) as the vector of parameters. Typically, the Hamiltonian is written in term of Pauli strings as A a,P, where a, E and P are tensor products of Pauli operators. This formulation includes multi-layered PQCs (c.g., the hardware- efficient ansatz) and appears in wide range of setups including quantum approximate optimization algorithm (QAOA), many-body quantum systems (e.g., Ising model), and adiabatic evolutions. Typically, the objective minimizing loss function L( d ) depending on the parameterization of the PQC, the input state, and the measurement observable. Hence, a mradient-based optimization can be used given an estimation of VL.
Our gradient estimation method is based on a binary encoding of Pauli strings to capture the structural properties of their commutation relations. Similar techniques have been used before in the context of the stabilizer formulation in quantum eтror correction [CRSS96, Got97]. Then, we make a connection between this binary encoding and the differential of the matrix exponential map, studied in Lie algebra [Ros06]. We write the partial derivatives of the PQC as an infinite-length linear combination of expectation values of Hadamard tests for various Pauli strings. We show that when the Pauli strings in A(7) are closed under the commutation, the infinite-enngth linear combination collapses to a finite number of terms that can be computed efficiently using the binary encoding. Such terms are written as the expectation value of a set of observables that can be estimated using CST, as an estimation procedure to estimate several observables with minimal sample complexity [HKP20] growing logarithmically with the number of observables.
When the closedness condition not directly satisfied, one can consider the sub algebra generated by P. terms in A( d') and apply the proposed gradient estimation method. In that case, the sample complexity and running time depend on the dimensionality of this sub-algebra. Therefore, the proposed estimation is efficient when the dimensionality is polynomial with n. The polynomial size assumption is already satisfied for several well-known Hamiltonian models, including variants of 2-laca Ising model (e.g., the cransverse-field) and Kitaev chain [WKKB23] used to model molecular dynamics. In addition, the polynomial dimensionality an essential component to avoid the barren plateaus [LCS-22 22, FHC+23, MBS+18, CSV+21] which are flat regions in the parameters landscape that have exponentially small gradients. This stems from the fact that the variance of the gradient inversely proportional to the dimension of the DLA [FHC+23) 23].

---

Circuit Changes
Sample Complexity
Running Time*
SPSRIBC21, WIWL22] NPSR[The23]
((p)
O
(pp|A|] p
(p]l
O(
(UN)
((p)
exp(@(n)) pexp (O(n) O(n" + n a))
[3
O p)
This work (bounded shadow norm)
0
O (logp)
Table 1: Rough comparison of various methods for estimating the gradient of a PQC with p parameters and DLA based on Pauli strings with poly(n) dimensionality. "For presentation convenience of the runtime, it is assumed that p = (nx)) and that each use of the ansatz takes ((n)) quantum time, where a and b are arbitrary constants. Also, the detailed dependencies ! and ||0 are ignored.
Nevertheless, there still is a curiosity to understand the gradient estimation when DLA dimensionality grows exponentially with n. For that, approximation techniques proposed in the more complete version of the paper [HMS24].
A more specific summary of our contributions is give below:
where Showing the gradient of the loss function can be written as VL VC=
D is the vector of the expectation values of Hadamard tests for a set of Pauli strings, and V is matrix constructed based on the parameters d (see Theorem 2).
An algorithm that estimates VL(() using ((p) Hadamard tests and O(p" + pn) classical time.
When the shadow norm of the observable bounded, the gradient can be estimated with Ollog) p) copies and (oly(n) time (see Section 3.3).
A master's theorem for the general case where the Pauli terms are not closed under commu- tation (see Theorem 4),
1.2 Comparison With Related Methods
We consider the three complexity measures: (1) sample complexity, (2) the classical post-processing time, and (3) the number of distinct circuits that need to be evaluated to obtain all the partial derivatives. Although this measure is less restrictive, it important to ensure it scales polynomially with the number of qubits. Table demonstrates a simplified comparison with existing works for gradient estimation. For a more intuitive comparison, with gate complexity (nn²) and p O(z") parameters, where and are arbitrary constants. The table shows that our approach provides an exponential advantage in terms of the copy complexity and polynomial speed-up in classical running time. Below, highlight some of the most relevant approaches for comparison to our work.
assumed that the PQC acts on n qubits
This method is a generalization of PSR [BC21, WIWL22], where each partial derivative is written as an integral, and Monte Carlo strategy is used estimate it. David al. [WIWL22] also presented a generalization of the PSR using the Discrete Fourier series. Here, the parameters are jointly shifted depending on the spectrum the Hamiltonian A is promised to have equidistant eigenvalues. However, for generic PQC one first needs to compute the spectral dccomposition of A to find the pattern of the parameter shifts. This process in general takes exp (O(n) classical time A is an exponentially large matrix.
Stochastic PSR:
ansatz. This method efficient when
Nyquist PSR: Recently [The23] proposed shift rule for PQCs where only the parameters are shifted without any other modifications of the ansatz. The method relies on a beautiful connection between the Ayquist-Shannon Sampling theorem and the Fourier series that was observed earlier in [WIWL22, VT18]. The number of unique circuits for this estimation scales with p and the difference between the maximum and minimum eigenvalues of A - quantity bounded by the operator norm ||||] As the authors reported, this method has low approximation emror when the parameter value is large enough. More precisely, the approximation error is O( as long as 0 = (1 - 2(1)),, where e is the maximum magnitude of parameter value.
3

---

This is another approach [WLW 24] based on Lie algebra and a nice connection to the geometry of S2(2") matrices and the adjoint operator. The gradient is calculated by finding the Jacobian matrix of the matrix representation of PQC. Hence, the running time scales as p29(x).
Lie algebraic:
Shadow tomography: A recent work [AKH 23] proposes a quantum backpropagation method for PQC of the form U(d) - I1 1 é Ps Uj. where U3 are fixed unitaries and P3 are fixed Pauli words. Leveraging the shadow tomography of [Aar 88, the method achieves sample complexity scaling as log" p. but with the cost of an exponential classical memory requirement of p20(m).
Classical simulation: Existing simulation methods such as g-sim [GLC*23 23] can efficiently simulate quantum system and hence compute the gradient, under the assumption that both the Hamiltonian A( d and the observable O have polynomial Lie dimensionality. In contrast, we only require A( ( to have polynomial Lie dimensionality.
Assuming both o and are efficiently classically simulatable, our work and that of [GLC have time complexity scaling polynomially with the dimension of the Lie algebra. Our work is complementary to [GLC+23] and offers distinct advantages when p and/or are not classically simulatable. This arises, for example, when O does not lie in Lie algebra of polynomial dimension, and p is physical quantum state obtained via an external process (e.g., quantum sensing) or generated by unitary that does not have polynomial Lie dimensionality.
When p is stored in a physical quantum state, [GLC 23] relies on computing expectation values of the Lie algebra basis elements (A) in the reference) under p. This is only efficient when certain classes of p including product states or stabilizer states. In more general setting, such expectation values must be estimated in a quantum computer and the sample complexity of the estimation may not be polynomial in n. Furthermore, even when p is classically simulatable, we expect significant (possibly exponential) separation from [GIC+ when the observable does not have polynomial Lie dimensionality while can be implemented polynomial quantum time on a quantum device and has bounded shadow norm. For example, in fidelity estimation, O (o)) where ()) e |0) and H is a Hamiltonian not admitting polynomial Lie decomposition. Here, is a low-rank observable with bounded shadow norm, but exponential Lie dimensionality. Hence, classical simulation runs exponentially in time.
2 Preliminaries and Model
2.1 General Framework
The objective is to minimize cost function defined
<( = =()=
(I)
where O is a fixed observable, is the initial (mixed) state, and U(d)) ) is a parameterized quantum circuit with d = (a).- ... (p) as the vector parameters. As U unitary, we can always write U(d)= = e (A((T) ) for some Hamiltonian matrix A. To ensure computational tractability, it is assumed that the number of parameters p po)y(n), with n being the number of qubits.
Making iterative progress in the direction of the steepest descent is one of the most popular optimiza- tion techniques in VQAs, it has been in classical problems. Ideally, gradient descent optimizer applies the following update rule at each iteration t:
a (++1) (1) - - M VL(T").
(2)
where 7) E R is the learning rate at iteration t. The above update rule is not realistic as the objective function ((d)) is an expectation value, and the characteristics are either unknown or computationally intractable.
2.2 Pauli Group
The Pauli gates are fundamental quantum gates that correspond to rotations around the respective axes of the Bloch sphere and form the basis for many quantum algorithms. Together with the identity,

---

they are denoted as fo 1o",o', ,0',0?, with
0² -1= 0 d'=x=
1- d=x=(111 () d= d 7)) d² = = 1 0 -
(
The single-qubit Pauli group P1 the 16 element set fco* :8 8 0. 1,2,3, c= +1, +i). The product of the Pauli operators is governed by the identities XYZ iT and X =
For n qubit systems, the Pauli tensor products are denoted as o² ṭ² 0 8..-80'4 for all E {0, 1, 2, 3}". The n-qubit Pauli group Ps, is then defined as the group generated by n-folld tensor products of the Pauli matrices:
Pn (co (0,1,2,3)", c= =1,
This group has 4d+1 elements and spans any operator the space of n qubits:
Fact 1. Any bounded operator A on qubits can be uniquely written as A = (0,1,0)) as o*, where ag 2 tr }
In light of this statement, we can assume that the parameterized circuit of the ansatz is of the form U(d) = (iA((i)))))))) where A(d)) Eves 0g0 for some S 3
2.3 Hadamard Test
Given a unitary U, the Hadamard test, which is a special case of the phase estimation, is quantum circuit that can circuit consists of two Hadamard gates and a controlled version of U.
estimate the real imaginary value of (y/ (U(b)) for some state (g).. The
When the ansatz has a simple form ( eida* its derivative can be directly estimated via Hadamard test [MNKF18 8] giving the following quantity
Dg = i
where pout = U(Z) is the output of the ansatz on input The above equation is based on the fact that di computing efficiency, and allows for the use of mcasurement optimization techniques. Moreover, can be used to compute higher-order partial derivatives used in higher-order optimization algorithms [2D]
20 = (0). Estimating the gradient through the Hadamard test can enhance
2.4 Differential of The Matrix Exponential
The matrix exponential is defined as
X
exp(X) =
k!
where X is a square matrix. Due to non-commutativity of matrix product, the differential of the exponential map has more complex formula compared to the exponential function. Suppose X(r) is differentiable matrix (linear operator)
function of the variable R. The adjoint map is defined as the mapping ad (Y) = [X, Y] = XY -Y for square n n matrixes X, Y E GL(n, C). Then, for any k 0, 1, .... we can define
a (Y) [X, [X.Y]...].
The exponential map and the adjoint are fundamental concepts in the theory Lie groups and Lie algebras, describing how Lie group Lie algebra acts on its own Lie algebra by conjugation (a standard text book on this topic is [Ros06]). The adjoint operator connected to the derivative the matrix exponential.
Theorem ([Ro006]). Suppose X X(T) is a differentiable (linear) operator with respect to a variable E R. Then, the differential of the matrix exponential is given by
d dexp(X(F)) exp(X(r)) 1 expp -xpx- dx(r) dr
(4)
adx
dr
5

---

3 Main Results
We introduce an approach for estimating the gradient of the loss for a generic ansatz using the Hadamard test followed by classical post-processing. We start with a binary encoding of the Pauli matrices.
3.1 Binary Encoding of Pauli Operators
is well-known that the Pauli group Pn. is isomorphic to the semi direct product of Σ1 and Z3".. In this work, present an explicit form of such mapping. This binary representation allows to write the partial derivatives of L a') as linear combination of terms related to the Hadamard tests applied to the ansatz output.
Note that the phase scalar c E {+1, Pn can be written 1", where a E Z4. the modulo-four group. As for the Pauli operators, consider the binary vector group E2 x Z2 {(0)0), (o)1), (1)0), (1]1)} with the element-wise modulo two addition:
(a (a (b"1b") (a b0 @ b²),
where @ is the binary addition. We use (.I-) distinguish between the first and the second components of elements of Øg x Zz. We associate the identity and each Pauli operator with elements of Eg x Z2
as
σ - (0)0).
o - (0]1),
a² - (1)0).
+ (1)1).
Extending n-qubits, (Z-2 x ) is defined the set of all (a*)at) for binary strings a a Z with the element-wise addition:
(a" + (b"lb²) (a ba + bb)).
We sometimes write z to denote this group for more compactly. Any Pauli string 0²,s E {0, 1, 2, 3) is associated with (s" where s" = (sf. ... s.......)))))'' = (s)..... Therefore, frequently switch between representations of member of 2 and (Zn x Σ2)".
s.) .............. are binary strings.
Example 1. The Pauli string X @ Y & X which is associated with O with s = (1,2, 1) has the following binary encoding: ((0, 1, 0)101, 1))-
Definition 1. Any element of Pn, written as o" is represented as (a, where a E Z1 and s E Z2 Such a representation is defined by the mapping à P,, + E, x Z that sends 6(i² = (a, s).
The above mapping can be used to encode the product of the Pauli matrices.
Encoding the products of Pauli words. function on i.j E Z4 (or Zo x Z22 as
Inspired by the Levi-Civita symbol, define sign
if (2.3, if. = (1, (2,3), (3,1) otherwise.
8(i.j) = {
1
(5)
For vectors u, v, define 8(u, v) = E, 8(u,
Lemma 1. The product any pair Pauli strings a², o" equals o²
Proof. It is not difficult to verify the lemma for single qubit case. For general dl >> 1, with the tensor product, we have that
8 0
(le sre,, 22c 6(e
0 220, o(8).r))
With this result, and by adding the phase scalars, for any pair o and ot from the Pauli group Pn. the product is characterized by the map in Definition
(i"'") s ((moss +b 8(s,r)), r)).

---

Example 2. Consider P. ix and P2 Z that are encoded to (L. ((010) and (0. (1001)) respectively. Then, P2P associated the binary en- coding (0, ((11)((111) which represents Y 0 Z & Z.
This binary representation is used to characterize the commutation relations between Pauli strings. Lemma 2. The commutator of any pair of Pauli strings o², ,o" is given by [aa, .a1 ()
3.2 Gradient Estimation
Recall that the objective function L( L(d)) in (1) and the expectation values Dx (3) can be estimated using Hadamard test. In what follows, we show how the gradient of L can be evaluated in terms of D, quantities. Recall the Hamiltonian Pauli decomposition: A( d') = -ees ag0". We first assume that the set of Pauli strings o², s S appearing in this decomposition is closed under the commutation, that is for any pair s, t E S the commutator [o*, o²) also appears in the above decomposition. The more general case where the Pauli terms are not closed under the commutation is also considered in more complete version of the paper [HMS24]].
We consider geometric representation of the gradient in terms of D, terms. Let S - (s1, Sph. where is the number of parameters. Let es (1,0,-.. 0)" ep .'".....
(0. ... 1)² be the canonical basis vectors in R2. We associate each S, with By which is also denoted by ((e,)- Now
:
consider the vector of the expectation terms D (Da.: "., DDp) as a row vector in RP, Then, the gradient is expressed vector derived from B.
(e((((())))) (2)) with A(d)= Eses ag0", where S is closed Theorem 2. For the ansatz ((d)= = exp exp(iA((
under commutation, the gradient satisfies V D(I e- V--, where V is the p p matrix with the ith column given by
2i
agi ((5,5)) e(sEay))
(6)
#ES Moreover there is an algorithum (Algorithm 1) that computes VL in O(p² + pn) time with ((p) use of the Hadamard tests.
The proof outline is given in Section 4.2. This representation is the key to the efficient computation of the gradient from the estimation of D,,s E S, summarized as Algorithm 1. The runtime of the algorithm is Opp pn) because each column v; is computed in O(pn) time and, and the matrix B can be computed in Ó(p²) time with a proper matrix exponentiation algorithm.
Algorithm 1 Gradient Estimation
Input: S
1: procedure GRADIENT ESTIMATION
2: Estimate D,, E S with Hadamard tests.
3: Compute the matrix V where the column i is computed as in (6).
4: Compute the matrix B (I = where V-1 is the generalized inverse of V.
VVV-,
5:
Return VL DB.
A simple example of a Hamiltonian closed under commutation is = ai X + azY + az 8 The gradient in this case be computed by 3 x 3 matrix and 3 Hadamard tests, irrespective of the dimensionality of the quantum system. Another class is K-junta Hamiltonians, that acting non-trivially on k qubits. In that case, all the Pauli strings σ E S, will be of the form of ln-k. the set S will be closed under commutation.
Remark 1. When the closedness condition is not directly satisfied, one can apply Theorem 2 to the DLA generated by the terms in A( d:). When the dimensionality of the DLA is m, Algorithm computes V. in O + dm) time with (mm) use of the Hadamard tests. Hence, Algorithm 1 is efficient when the DLA has dimensionality polynomial in n.
Example 3. The following Hamiltonian has a DLA with dimensionality O(n?):
H Σ Z, Z,Z411 + X
7

---

where X,, Zi are the corresponding Pauli operators. In this case, applying Theorem 2 to the DLA generated by H, Algorithm 1 computes VC (n²) time with (n²) use of the Hadamard tests.
As sanity check, Appendix A present explicit derivation of the gradient in the single qubit case.
3.3 Efficient Estimation with Classical Shadow Tomography
Turning the gradient estimation to series of Hadamard tests has another benefit that can further reduce the number of shots to (log p). This can be done using shadow tomography [Aar 18, HKP20, HBM CGY24, KGKB25]. The components of the gradient V correspond to observables that only depend paue without any reconfigurations. In that case, having several copies of p we can efficiently estimate all the components of the gradient. Based on Theorem 2, the observables are p different Hadamard tests denoted by H E [p] for measuring Da, The following lemma gives an explicit characterization of these observables.
Lemma It holds that Dx = tr Ha where pout the ansatz output state and Hs R OR - R2. O R with R = expl -i - 08) for Pauli string a².
Proof. Recall that D3 ir((O po Moreover, from [MNKF18] the following property holds for any operator B and Pauli string o²:
10 B]
[a 2t ( - (a(- BRa( (
where (0) = 000 With this observation, we obtain
D₂ un{ ir(o( (x(5)) aT ) nut (a(5)1
R₂( Rs(- ) Ral 17 ( 1O ) } + to Ra( " 110Rm(((( 2 pout
= tnf Ra á
where we used the cyclic property of the trace. The last equation gives the expression for Hg.
In order to estimate the gradient, one needs to estimate all the expectation values tr RR, } for s E S. We use CST to exponentially reduce the measurement shots for the gradient estimation.
Theorem 3 ([HKP20]). Given an observable O, state prnt, and a set S S 1,,,,,,3)" the ex- pectation values of = ur ORs for s S can be estimated with additive error using
N N N=ol o log|s max
1 OR (
shadow
copies of pout, where |-Ilshadow is the shadow norm.
The shadow norm (Definition in Appendix B) is closely related to the variance of the observable and the of the unitary transformation used for taking the classical shadows. For random Clifford measurements, it is bounded by the Silbert-SShhiit norm; whereas for random Pauli measurements, is bounded by 4 where is the the locality of the observable, not the actual number of qubits [HKP20]. For completeness, a brief summary of CST is provided in Appendix B.
Proofs Overview
4.1
Master's Theorem
We prove a master's theorem for the partial derivatives of an ansatz with generic subset S that is not necessarily closed under the commutations, This result can be used is for generic PQCs and as step to prove our main results.
8

---

Theorem 4. For the ansatz ( = exp(iA(d)) with A(d) = Eses aso" for some generic
subset S _ 20,1,2,3 ", the partial derivative with respect to or is given by
Oc(d)
(2i)* (k (I+1)
h
Σ ...
Σ SLES
II
asy 88 (60)) 0 0my-
D510..
8ür
5: ES
f=1
Proof outline. Noting that pon UpU the partial derivative of the loss with respect to og is
ac
tr 8an
pout pout
9
J. where
Bo.
Op aU
dag Ja, (pU1) (Up) aU
(8)
aa
aa
and we used the fact that pone is Fréchet differentiable with respect to ag Based on Theorem 1, we prove slightly different expression of the differential of the matrix exponential.
Lemma 4. Suppose U = exp(iH(T)), where H(T) is differentiable. Then, dr
du
1-exp(iada ( J. adw dr
Proof. We can write U = (e (e Therefore, given that dxt dr = dr )², from (4) we can write
4X
dU
de dd--HH())
(expl (exp(-iH(T))
exp( - ad m d( d(-iH(TT))
dr
dr
ad_
dr
exp(
-ad
im1) d( d()iH((T))
dr U.
ad_
Note that for any E gg we have the following equality by its convergent power series:
exp(-ad
(-1)*
(ad
(9)
ad
k=
Therefore, replacing H with -ill in this equation, the derivative equals to the following
dU
(+)* (ad )*(
dH ((ar))
2c (-i)*
(adn)**
dH t
=
U.
dr
(k + 1)!
dr
(1+ I1
dr
Note that for any X, Y E Egg (Y)x(t))t x Therefore,
dU
(i)*
dHl (ad
dHl dr
( JU
U
dr
(k + 1)!
ad
k=0
From this lemma, obtain the first part of (8):
Opout
1 - exp((iaa 0A
Out
) (U (U + (Up) Da,
dag
ad
Dag
Next, from Theorem and (4), the partial derivative of Ut be written as da, Ut 1-exp(-iaddl (d,,) where used the fact that A is Hermitian. Therefore, the partial derivative
out
ada of oou equals
ou 1 1 exp((add) 0A oue oou 1 - exp(iad A} 0A
ad By simplifying the terms in the right-hand side, the partial derivative can be written as the commutator:
dag
a
Das
day
ac
tr {o
② putt)
offo {ol folpoe exp(iada) 0AA
(10)
Zug 0ag
ad
Dag

---

Next, based on the Taylor expansion of the matrix exponential and from the fact that above quantity decomposes as
04
= =o,
the
Bus
ac
(i)* to tr(Olpoee (ad (o
(11)
aa,
(k 1)!
k=
Then, building on the binary encoding of Pauli operators, and Lemma we can write the adjoint operator as below.
Lemma 5. For any A, B, ad = Er. (s o where Oa 2 (r(Aa*) and by 1 tr ] are the Pauli coefficients of A and B, respectively.
2n
Therefore, omitting the details, and as the partial derivative in the statement of Theorem 4.
write the series decomposition of ad (a*), appearing in (11),
4.2 Proof of Theorem 2
Proof outline. The proof of this results based the master theorem. Since the Pauli terms o*, s E S are closed under commutation, then per Lemma 2, S is closed under the "@" operation, that is for any pair s. E Hence, each term $1 ① ... + Sk + (7) in Theorem 4 remains in S. As result the infinite-length sum in Theorem 4 reduces to linear combination with finite BC = Exes 9s Dr) where (x) E R are some coefficients. This means that the partial terms as der derivative is always linear combination of Dz. s E S terms. However, the challenge is in computing the coefficients 9s (r) that coming from infinite-length sum. We present method address this issue.
s ①
Recall that V is the p matrix with the jth column given by V, 2i Σ Eges (2,55)),,,) ((ebe,)) By an induction argument, and from the definition of the matrix exponential, it is not difficult to check that
(T- V---IV- (r) =
Σ k=
(2: 1k
Σ B
II j=1
k
(8,, 00 10)) eaie--ooer-
Gg
BLES
If one replaces eş with D& for any s, the obtain (7) for the partial derivative of L. Omitting some details, the gradient is then calculated by VL = D(I - v-v-
Discussion and Conclusion
This paper provides a framework to estimate the gradient generic PQCs via Hadamard tests for Pauli operators followed by classical post-processing. It is shown that the proposed approach is polynomial in classical and quantum resources when the DLA of the associated Hamiltonian of the PQC has a dimensionality polynomial in the number of qubits. Moreover, this method does not change the ansatz structure and can be used to reduce the measurement shot complexity to scale logarithmically with the number of parameters. The results would be beneficial in various optimization or learning quantum algorithms that rely on the estimation of the gradient.
One limitation of this work is when the Hamiltonian has exponentially many Pauli terms. In that case, we can only approximate the gradient by truncation of the nested summations in Theorem to fixed number of terms. However, this will be biased approximation. As future work, one can extend the proposed framework to the estimation of bigher-order derivatives. Deriving lower bounds on the classical and quantum resources needed to estimate the gradient or higher-order derivatives is another important direction.
Acknowledgments and Disclosure of Funding
This work partially supported by the NSF Center for Science of Information (CSol) Grant CCF- 0939370, and also by NSF Grants CCF-2006440 and and CCF-2211423.
10

---

References
[Aar18] Scott Aaronson. Shadow tomography of quantum states. In Proceedings of the 50th Annual ACM SIGACT Symposium Theory of Computing. STOC 2018, page 325-338, New York, NY, USA, 2018. Association for Computing Machinery.
[3KH*23] Amira Abbas, Robbie King, Hsin- Yuan Huang, William J. Huggins, Ramis Movassagh, Dar Gilboa, and Jarrod McClean. On quantum backpropagation, information reuse, and cheating measurement collapse. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 44792 44819. Curran Associates, Inc., 2023.
[AWGP21] Gian-Luca Anselmetti, David Wierichs, Christian Gogolin, and Robert M Parrish. Local, expressive, cennnttm-nmmbbrppee preserving vqe ansätze for fermionic systems. New Journal of Physics, 13:1)): 1311000 November 2021.
[BC21] Leonardo Banchi and Gavin E. Crooks. Measuring analytic gradients of general quantum evolution with the stochastic parameter shift rule. Quantum, 5:386, January 2021.
[BLSFI9] Marcello Benedetti, Erika Lloyd, Stefan Sack, and Mattia Fiorentini. Parameterized quantum circuits machine learning models. Quantum Science and Technology, 4(4):043001, 2019.
[CAB+21] M. Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C. Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R. McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, and Patrick J. Coles. Variational quantum algorithms. Nature Reviews Physics, 3(9):225-64,, aug 2021.
[CGY24] Sitan Chen, Weiyuan Gong, and Qi Ye. Optimal tradeoff's for estimating pauli observ- ables. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 1086-1 1105. IEEE, October 2024.
[CRSS96] A. R. Calderbank, E. M Rains, P. W. Shor, and N. J. A. Sloane. Quantum error correction via codes over gf(4). August 1996.
[CSV+21] M. Cerezo, Akira Sone, Tyler Volkoff, Lukasz Cincio, and Patrick J. Coles. Cost function dependent barren plateaus in shallow parametrized quantum circuits. Nature Communications, 12(1), March 2021.
[DAJ+21] Alain Delgado, Juan Miguel Arrazola, Soran Jahangiri, Zeyue Niu, Josh Izaac, Chase Roberts, and Nathan Killoran. Variational quantum algorithm for molecular geometry optimization. Physical Review A, 104(5):052402, November 2021.
[FGG14] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimiza- tion algorithm, 2014.
[3]C+23] Enrico Fontana, Dylan Herman, Shouvanik Chakrabarti, Niraj Kumar, Romina Yalovet- zky, Jamie Heredge, Shree Hari Sureshbabu, and Marco Pistoia. The adjoint is all you need: Characterizing barren plateaus in quantum ansätze. September 2023.
[FN18] Edward Farhi and Hartmut Neven. Classification with quantum neural networks on near term processors. February 2018.
[GEBM19] Harper R. Grimsley, Sophia E. Economou, Edwin Barnes, and Nicholas J. Mayhall. An adaptive variational algorithm for exact molecular simulations on quantum computer. Nature Communications, 10(1), July 2019.
[GLC+23] Matthew L. Goh, Martin Larocca, Lukasz Cincio. M. Cerezo, and Frédéric Sauvage. Lie-algebraic classical simulations for quantum computing. arXiv:2308.01433 August 2023.
[Go197] Daniel Gottesman. Stabilizer codes and quantum error correction. California Institute of Technology, 1997.

---

[HBM*21] Hsin- Yuan Huang. Michael Broughton, Masoud Mohseni, Ryan Babbush, Sergio Boixo, Hartmut Neven, and Jarrod R. McClean. Power of data in quantum machine learning. Nature Communications, 12(1), May 2021.
[9C Vojtëch Havliček, Antonio D. Córcoles, Kristan Temme, Aram W. Harrow, Abhinav Kandala, Jerry M. Chow, and Jay M. Gambetta. Supervised learning with quantum- enhanced feature spaces. Nature, 567(7744):2009-22 March 2019.
[HGS22] Mohsen Heidari, Ananth Y. Grama, and Wojciech Szpankowski. Toward physically realizable quantum neural networks. Association for the Advancement of Articial Intelligence (AAAI), 2022.
[HKP20] Hsin-Yuan Huang, Richard Kueng, and John Preskill, Predicting many properties of a quantum system from very few measurements. Nature Physics 16, 1050-1057 (2020), February 2020.
[HMS24) Mohsen Heidari, Masih Mozakka, and Wojeiech Szpankowski. Hadamard test is sufficient for efficient quantungradient estimation with lie algebraic symmetries. arXiv preprint 2404.05 1004.05/08. 108, April 2024.
[HN21] Aram W. Harrow and John C. Napp. Low-depth gradient measurements can improve convergence in variational hybrid quantum-classical algorithms. Physical Review Letters, 126(14):14002,,, apr 2021.
[HPS21] Mohsen Heidari, Arun Padakandla, and Wojciech Szpankowski. A theoretical framework for learning from quantum data. IEEE International Symposium on Information Theory (ISIT), 2021.
[HS23] Mohsen Heidari and Wojciech Szpankowski. Learning k-qubit quantum operators via pauli decomposition. In Francisco Ruiz, Jennifer Dy, and an-Willlm van de Meent, editors, Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research. PMLR, 25-27 Apr 2023.
[HS24] Mohsen Heidari and Wojciech Szpankowski. New bounds on quantum sample complex- ity of measurement classes. 2024 IEEE International Symposium on Information Theory (ISIT), pages 1515-1520. IEEE, July 2024.
19] Tyson Jones, Suguru Endo, Sam McArdle, Xiao Yuan, and Simon C. Benjamin. Vari- ational quantum algorithms for discovering hamiltonian spectra. Physical Review A, 99(6)4062304, June 2019.
[KGKB25] Robbie King, David Gosset, Robin Kothari, and Ryan Babbush. Triply efficient shadow tomography. PRX Quantum, 6(1):010336, February 2025.
[2CS+22) Martin Larocca, Piotr Czamik, Kunal Sharma, Gopikrishnan Muraleedharan, Patrick J. Coles, and M. Cerezo. Diagnosing barren plateaus with tools from quantum optimal control. Quantum, 6:824, September 2022.
[LDO+24] Dantong Li, Dikshant Dulal, Mykhailo Ohorodnikov, Hanrui Wang, and Yongshan Ding, Efficient quantum gradient and higher-order derivative estimation via generalized hadamard test. arXiv: 2408.00 054661,, August 2024.
[LW18] Jin-Guo Liu and Lei Wang. Differentiable learning of quantum circuit born machines. Physical Review A, 98(6):062324, December 2018.
[MBS+18] 18] Jarrod R. McClean, Sergio Boixo, Vadim N. Smelyanskiy, Ryan Babbush, and Hart- mut Neven. Barren plateaus in quantum neural network training landscapes. Nature Communications, 9(1), November 2018.
[MKF19] Kosuke Mitarai, Masahiro Kitagawa, and Keisuke Fujii. Quantum analog-digital con- version. Physical Review A, 99110:1 January 2019.
12

---

[MNKF18] K. Mitarai, M. Negoro, M. Kitagawa, and K. Fujii. Quantum circuit learning. Physical Review 98(3):032309, sep 2018.
[Ros06] Wulf Rossmann. Lie groups: An Introduction through Linear Groups. Number 5 in Oxford graduate texts in mathematics. Oxford University Press, Oxford [u.a.], 1, publ. in paperback edition, 2006. Reprinted 2011.
[SBG+18 18) Maria Schuld, Ville Bergholm, Christian Gogolin, Josh Izaac, and Nathan Killoran. Evaluating analytic gradients quantum hardware. Phys. Rev. A 99, 032331 (2019), November 2018.
[SK19] Maria Schuld and Nathan Killoran. Quantum machine learning in feature hilbert spaces. Physical Review Letters, 122(4):040504, February 2019.
[SKP24] Mohammad Aamir Sohail, Mohsen Heidari Khoozani, and Sandeep Pradhan. Quan- tum natural stochastic pairwise coordinate descent. arXiv:2407. July 2024.
[SWM*20] Ryan Sweke, Frederik Wilde, Johannes Meyer, Maria Schuld, Paul K. Faehrmann, Barthélémy Meynard- Piganreau and Jens Eisert. Stochastic gradient descent for hybrid quantum-classies optimization. Quantum, 4:314, aug 2020.
[The23] Dirk Oliver Theis. Proper shift rules for derivatives of perturbed-paramette quantum evolutions. Quantum, 7: 7:1052, July 2023.
[VTI8] Javier Gil Vidal and Dirk Oliver Theis. Calculus on parameterized quantum circuits. 11X1v:1812.063323, December 2018.
[WIWL,22] David Wierichs, Josh Izaac, Cody Wang, and Cedric Yen- Yu Lin, General parameter- shift rules for quantum gradients. Quantum, 6:677, March 2022.
[WKKB23] Roeland Wiersema, Efekan Kökcü,, Alexander F. Kemper, and Bojko N. Bakalov. Classification of dynamical lie algebras for cranslationiivvaiinn 2-local spin systems in one dimension, 2023.
[WLW+24] Roeland Wiersema, Dylan Lewis, David Wierichs, Juan Carrasquilla, and Nathan Killoran. Here comes the su(n): multivariate quantum gates and gradients. Quantum, 8:1275, March 2024.
13

---

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

---

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

---

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

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: the paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: httppp////errrp...c/a/clc//ee/ee http/p/ccc//ticcccieeeeeee ines?
Answer:
[Yes]
Justification:
We believe this research within NeurIPS Code of Ethies.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS 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 a 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: there is societal impact of the work performed.
Guidelines:
The answer NA means that there is 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), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific 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
17

---

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 the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a 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]
Justification: the paper poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards 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 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]
Justification: the paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.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 package should be provided. For popular datasets, paperswi. thcode com con/dataset has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
18

---

Answer: [NA]
Justification: the paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/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
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
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 equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to 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
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
19

---

Justification: the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non- non-standard components.
Please refer to our LLM policy (https: / //neurrisss scc//oonfeeeece/222022 for what should or should not be described.
20

---

A Derivation of The Gradient for a Single Qubit PQC
Consider general single-qubit unitary of the form
u(d)= = exp i((jo' + az2 + a3o²))}
Let O be generic observable and consider the associated loss L(d)) ) in (1). As an illustrative example, we examine the partial derivative of L with respect to aj, evaluated at the point aj and dg 0. In the following compute this derivative using two approaches: first, by applying Theorem 4, and through direct calculation.
Closed-form expression based on Theorem In the context of Theorem 4, let D2 be the result of the Hadamard test with Pauli σ², where j 2, Then, (7) in Theorem 4 simplifies to the following:
OC ( = (0. 02, 0))
(2i) (k + 1)!
(2,
U2i
(2,
@
D ... 2011)
da1
k=
times
where we used the fact that only terms with s, 2 are surviving. Because for even j we have 2 + ... + 2 @1 3, and for odd j it is equal to 0 Therefore,
43 0. Note that
j-1 times
(2.000.0020)) = (6(23)
even k
((221) = -1 odd
times
where we used (5). Plugging it in the first equation, we have
(a2i) (-1)b/2 even (a
II 02 j=1
(22 +
20i1)
odd k.
As result, the partial derivative simplifies
OC ( (0, (0,02.0)) 0)) da
(-2) 28 (2p + 22 (-1)
(-2) 24+1 (2q 2)!
Σ
(-1) Da-
22
Hence, one needs to measure Dj and D3 to compute the above partial derivative. Next, by simplifying the summations, it is not difficult to show that
Oc ( (0, a2 0)) =
-1
Σ
(-2ag) 22++1 )
(2p + 1)! (-1)0 D1 +
-1
Σ
(-2ag) )4-2
(-1)0+1 D3
Oag
202
20²
(2g 2)!
-1
(sin( 22z) Di + (cos (-2a2) - -1)
20²
1
(sin(2
Dr
(2mz)) Dz)
202
Notice the presence of D3 which relates the Pauli 3 and not appear in the ansatz expression. One can verify that this is indeed equal to the analytic gradient of this ansatz.
Direct derivation. Note that from (8) the partial derivative of the objective function can be written
0c Dag
info
OU (pU + (UP) aU
}
dag
Da.
21

---

Given that a0' Da,
(0 "0,
Then, by denoting Ú
ØU Dag
we have that
Oc tr OUp Upūit..
aa.
Next, UUT have
0C = ir {o (O(Ti(UNttt) (UN } Oa,
tr :rfo pane + (())))
where pat the ansatz output. Note that the single qubit ansatz can also be written as
U(d)= cos +
Σ
0.00
sin
(12)
(E(0,12.33)
where 0 =
VV a is normalizing parameter and å, respect single parameter a, appearing the sum:
g. Now, we can differentiate U with
@ (- as sin 0) +i
Ug
0² 0 Os
0²
sin 0
0a,
g3
f3
(13)
co8
0
ày.0%'
+i i
0
Therefore,
a0( d)
sin 02
ig
0a1
02
Using (12) find U1, have that
sin 02
= i ūut
(cos a20
- sin a2o3).
02
Which when plugged into the derivative expression gives
aL
sin 02
sin 202
D1 + (1 cos 2a²)
(cos D1 + sin Dz)
D3.
da
a1=0
02
2a2
202
This is identical to the expression based on Theorem 4.
B Classical Shadow Tomography
For completeness, in this section we briefly describe the classical shadow tomography procedure. For more details see [HKP20). Classical shadow tomography a technique used quantum computing to efficiently learn properties of quantum state using only few measurements. It was introduced to extract useful information from quantum states without requiring full quantum state tomography, which is costly in terms of the number of measurements and computational resources.
More precisely, let O [M] be a of observables. The goal is estimate the expectation value of these observable for measuring an unknown state p in Hilbert space H.
Theorem 5 ([HKP20J). Suppose the observables Oj.j E M are traceless, then the expectation values (rpp)p [M] can be approximated up additive error with probability (1 8) with
1
M
log 2
max 11 Ishaddoo
8
copies of p.
22

---

The shadow norm is a measure that resembles the variance in the worst case state, defined in the following. We first describe the steps in this procedure for generic state p in Hilbert space H.
First, generate a unitary operator U randomly from class of choices U to be determined. Apply U the input state resulting in the state PU, Measure the resulted state in the canonical basis Ij) E [dimx]. From Born's rule the probability of getting the output is Pj (iIU" p Given an outcome j. define wij U liXi Ut. The expectation E,, over the measurement randomness (p,) and the choice of U equals to Míp]. where .M a mapping defined as
M[O] = EU Σ
GIUtOUl) U
(14)
JE [diimm
for any operator O H. Observe that M is linear mapping on B(H) and hence has inverse denoted by M-1 We note that M is the shadow channel M introduced in [HKP20]. We apply M on wy resulting in the so called shadow
ò := (U
(15)
Note that is classical matrix and hence can be copied several times. Morcover, á is not valid density operator as it is not necessarily a positive semi-definite matrix. However, it is an unbiased estimate of the original state.
When U is tomographically complete, the classical shadow ý is unbiased, that is Eu p. Definition 2. The shadow norm of any operator O with respect to a set U of tomographically complete unitaries is defined
(Eu-u Σguloub) (1UM~1110""")))
max DED
JE sE|dmx)
B.1 CST with Pauli Measurements
Shadow tomography with Pauli measurements. Suppose the observable O, act non trivially on at most k qubits. For that U in CST is the tensor product of randomly chosen Pauli operators:
U U1 @ @ Un E C2 8
where each Uy is chosen randomly and uniformly from the Clifford group CL(2). In this case, = (2 Moreover, the shadow matrix computed as
3U
by
X
U,-
U,
In that case, the shadow norm is bounded by the locality of the observables as
|0 10lloshaoow < 2 10
As result the sample complexity of CST is given by
of log max 10,
J
The CST algorithm runs in ((29(k) m log m) classical time.
B.2 CST with Clifford Measurements
The Clifford group is a set unitary operations that map Pauli operators to other Pauli operators under conjugation. For system of n qubits, the Clifford group C'L(2") consists of unitaries U such that for any Pauli string P:
UPU = P',
where P' is another Pauli operator.
Clifford circuits are particularly useful because they can be efficiently simulated classically, and their structure allows for easy manipulation of Pauli observables, making them useful for shadow
23

---

tomography. In that case, U is chosen randomly from the Clifford group. The shadow norm is bounded
10 shadow 3tr((2),
when tr tr{0 < oo. The shadow matrix is given by
(2" + 1YUT - I.
As result the sample complexity of CST is bounded as
log m max tr (0)))
and the CST algorithm runs ((2 log m) classical time.
24


Reviews:
[{"review_id": "QkvW8NM9cD", "reviewer": "Reviewer_8q5a", "summary": "The paper proposes an efficient method for estimating gradients in parameterized quantum circuits (PQCs) by utilizing Lie algebraic structures in combination with the Hadamard test. Traditional methods often face exponential complexity or computational overhead, but the authors derive a concise mathematical formulation leveraging commutation relations, significantly reducing the computational complexity. Their method integrates classical shadow tomography, achieving logarithmic sample complexity in the number of parameters, and polynomial classical and quantum runtime, thus substantially improving efficiency for quantum optimization and learning tasks.", "questions": "1. Could you discuss explicitly how restrictive your condition (closure of commutators) is in practice? It would be helpful to provide more intuition or realistic examples of quantum systems that do or do not satisfy this condition.\n \n\n2. Given that your theoretical results have restricted generality, can you provide additional examples or numerical experiments involving realistic quantum applications (e.g., quantum chemistry Hamiltonians, QAOA circuits, or real-world quantum hardware ansätze)?\n \n\n3. Your method achieves impressive complexity improvements but sacrifices generality. Could you discuss or compare explicitly this trade-off against existing gradient estimation methods, especially highlighting scenarios where your method significantly outperforms others despite its restrictions?\n \n\n4. Are there natural or straightforward extensions of your framework to handle circuits whose commutators do not form a closed group, possibly via approximations or truncation? If so, briefly outline how that might work.\n \n\n5. Could you clarify the practical feasibility and computational overhead of employing shadow tomography in realistic scenarios? Specifically, under which conditions would shadow tomography actually offer substantial practical benefits over standard measurement techniques?", "limitations": "The authors clearly acknowledge the primary limitation of their work—the reliance on a closed Lie algebra structure with polynomial dimensionality—which restricts the method’s applicability to non-universal quantum circuits. They also discuss strategies to address this, such as closure computation, truncation, and Poisson sampling. While there is no explicit discussion of societal impact, the work is theoretical in nature and focused on quantum algorithm optimization, which does not currently pose immediate societal risks. No critical omissions were identified in this regard.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "The paper does a nice job introducing a theoretically rigorous method for efficient gradient estimation in parameterized quantum circuits, using Lie algebra and Hadamard tests to significantly cut down complexity. Its theoretical analysis is clear and thorough, highlighting substantial improvements in efficiency. However, a major downside is the limited generality—the key condition (commutators forming a closed algebra) means it won't work for highly expressive or universal quantum circuits. Given this limitation, it would have been helpful if the authors provided more concrete examples of realistic quantum systems to clearly illustrate practical usefulness.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful and constructive comments on our paper. We appreciate your engagement with our work. Below, we provide responses to your questions and concerns.\n## Q1: Generality of the results:\nThe condition of closedness under commutation is indeed satisfied by many well-known Hamiltonian structures. This includes several physically relevant models where the underlying algebraic structure naturally adheres to this property (see Examples 1 and 2 below). \n\nOn the other hand, many-body Hamiltonians such as those in quantum chemistry (e.g., electronic structure Hamiltonians) sometimes do not satisfy this closure condition globally. However, local approximations or block-structured truncations sometimes do. Our approach is still applicable to such Hamiltonians  via two techniques:  \n\n1.   Adding additional auxiliary elements so that the overall terms become closed under commutation. This is generally known as the dynamical sub-algebra (DLA) that has been studied literature. As long as the dimensionality of DLA is polynomial in the number of qubits, our results will be efficient. \n2. Approximation techniques discussed in Section 5 via Truncation and Poisson Sampling. \n\nWe argued polynomial dimensionality of DLA is a non-issue for quantum learning and optimization, as polynomial dimensionality is needed to ensure the absence of barren plateaus. This relates to the tradeoff between generalizability/expressibility (related to the dimensionality of Lie algebra) and trainability (absence of barren plateaus) [CSV+21,FHC+23,MBS+18].  \n\n## Q2: Examples of realistic quantum systems closed under commutation:  \n**Example 1:** Variations of the Heisenberg spin model that have been widely used to describe the spin interactions in condensed matter systems and appear in quantum magnetism, nuclear magnetic resonance (NMR), and in quantum computing (e.g., Hamiltonian simulation or benchmarking).\nThis Hamiltonian takes the following form: \n$$\nH=\\sum_{i,j} (J_{x}X_{i}X_{j}+J_{y}Y_{i}Y_{j}+J_{z}Z_{i}Z_{j}),\n$$\nwhere $X_i, Y_i, Z_i$ are Pauli $X, Y, Z$ on the $i$th, qubit, respectively. One can check that the above Hamiltonian is closed under commutation of these terms. \n\n**Example 2:** Another example is the class of stabilizer Hamiltonians used in quantum error correction codes such as  Toric Code and Surface Code. The Hamiltonian is of the form: \n$$H_{TC}=− J_e\\sum_v A_v - J_m\\sum_p B_p$$\nwhere  ​$A_v = \\prod_{i \\in v} X_i$, and $B_p = \\prod_{i \\in p} Z_i$ with $v,p$ are the vertices and plaquettes of the toric code lattice.  \n\n**Example 3: A realistic quantum system that is not closed under commutation but has a polynomial closure**\nA concrete example discussed in the extended version of the paper is the transverse-field Ising model:\n$$H=\\sum_{i} Z_{i}Z_{i+1}+X_{i}$$\nWhile this Hamiltonian does not satisfy closedness on its own, the inclusion of auxiliary terms yields a closed subalgebra with dimensionality $O(d^2),$ where $d$ is the number of qubits.\n\n\n\n\n## Q2: Regarding Numerical Results\nWe plan to explore numerical experiments of our results for a class of Hamiltonians with polynomial dimensionality as future work, including the following models:\n- **QAOA Hamiltonians for MAXCUT**: We plan to demonstrate that even partial closure (e.g., commuting subsets) suffices for practical gains.\n- **Quantum chemistry Hamiltonians**, while these do not satisfy our closure condition exactly, we plan to show that low-rank approximations of the Hamiltonian often concentrate weight on terms that approximately commute, allowing our method to apply effectively on truncated versions.\n\n\n## Q3: Trade-off against existing methods\nExisting methods, such as parameter shift rules or finite-differencing, are broadly applicable but suffer from high sample complexity, especially in scenarios involving deep quantum circuits or large observables.\n\nIn contrast, our method significantly reduces the complexity of gradient estimation when the PQC exhibits Lie algebraic structure. By leveraging this structure, we achieve more efficient and accurate gradient evaluations. We anticipate substantial performance gains in quantum systems where such algebraic properties naturally arise, including variations of the Heisenberg spin model and classes of stabilizer Hamiltonians used in quantum error correction codes.\n\n\n## Q4: Extensions to more general Hamiltonians\nSection 5 addresses extensions of our framework to handle circuits whose commutators do not form a closed group. We proposed two methods:\n1. **Truncation-based approximation**, which limits the expansion to a manageable subset of terms,\n2. **Poisson sampling**, a stochastic method for estimating gradients efficiently. \nTheorems 6 and 7 briefly highlight our analysis of such methods. \n\n## Q5: Shadow tomography\nShadow tomography is particularly well-suited for scenarios where multiple properties of a quantum state need to be estimated. This corresponds to the case when the number of parameters $p$ is large, as in our setting. As discussed in the original reference [HSP20], shadow tomography offers substantial practical advantages, especially for low-depth Clifford circuits and observables with favorable structure, such as low locality or low rank.\n\nThe referenced work demonstrates the effectiveness of shadow tomography in several concrete applications, including fidelity estimation, entanglement verification, and quantum simulation of models like the lattice Schwinger model. These examples highlight the method’s efficiency and scalability in realistic quantum computing tasks."}, {"review_id": "ygVOdnqQhh", "reviewer": "Reviewer_P3Rm", "summary": "This paper addresses the problem of gradient estimation in parameterized quantum circuits (PQCs). Specifically, it investigates an approach based on Lie algebraic structures within PQCs. Without loss of generality, a PQC can be represented as the exponential of $iA$, where $A$ is a parameterized Hamiltonian expressed as a linear combination of Pauli strings. In this formulation, the parameters of the PQC correspond to the coefficients of these Pauli strings.\n\nThe algorithm begins with the observation that the Hadamard test can be used to estimate both the real and imaginary components of $\\langle\\psi|U|\\psi\\rangle$ for a given unitary $U$ and quantum state $\\ket{\\psi}$. This procedure can be extended to estimate the quantity $D = \\mathrm{Tr}\\left(O[\\sigma, \\rho]\\right)$, where $O$ is an observable, $\\sigma$ is a Pauli string, and $\\rho$ is the output state of the quantum circuit. The authors show that, in the special case where the Pauli decomposition of the Hamiltonian $A$ is closed under commutation, the gradient of the PQC can be computed using $p$ distinct values of $D$, each associated with a different Pauli string, requiring $p$ corresponding Hadamard tests. Furthermore, the number of measurement shots can be reduced to $O(\\log p)$ by leveraging techniques from shadow tomography. To address the more general case where the Pauli decomposition is not closed under commutation, the authors propose three solutions: computing the closure, applying truncation, and using Poisson sampling.", "questions": "1. Could you elaborate more on why WLOG we can assume the parameters of the PQCs are the coefficients of the Pauli decomposition? If we use different parameter choices for the same circuit family, would your results still apply?\n\n2. In Section 3.3, can you give a self-contained theorem statement on the overall resources for gradient estimation, similar to Theorem 2?\n\n3. In Section 5, can you give some self-contained description on the overall resources for gradient estimation for the three solutions you mentioned, similar to Theorem 2?\n\n4. Can you elaborate more on how Eq. 3 is obtained? I think it would be beneficial for readers to better understand the overall algorithm\n\n5. Typos & minor issues: Below line 175 it should be b^1 instead of b^2; in Eq. 6 it is probably better not to use 'i' as subscript given that you already used it to denote the imaginary unit;", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. The algorithm and the corresponding analysis is novel and interesting.\n\n2. The algorithm obtains a significant improvement on the number of shots in the special case where the decomposition is closed under commutation.\n\n\nWeaknesses:\n\n1. Beyond the examples provided in the paper, it remains unclear how broadly applicable the proposed framework is to more general settings. Please refer to the \"Questions\" part for more details\n2. The organization and presentation of part of the results are not super clear. Please refer to the \"Questions\" part for more details.", "was_revised": true, "final_justification": "my questions are basically unchanged so I keep my score", "rebuttal": "Thank you for your encouraging and constructive review of the paper. Also, thank you for the list of typos and suggestions to improve the paper. We will address the minor comments in the revised manuscript. \n\nBelow we present our brief reply to your questions. \n## Q1: Generalized Parameterizations Beyond Pauli Decomposition\nThe assumption that parameters correspond directly to coefficients in the Pauli decomposition is made primarily for analytical convenience, given that any Hamiltonian can be expressed in this basis.\n\nHowever, as discussed in **Section 6 of the extended version**, our framework naturally extends to more general Hamiltonian parameterizations.   Even more generally, our framework extends to the parameterizations of the form: $$A(\\overrightarrow{a})=\\sum_{i}f_{i}(\\overrightarrow{a})G_{i},$$where $f_{i}$ are real-valued functions of the parameters and $G_i$ arbitrary traceless Hermitian operators, that might be decomposed as a linear combination of Pauli terms.\nWe will clarify this point in the revised version of the paper. \n\n## Q2, 3:  self-contained theorem statements\nThank you for the suggestion. We will revise the paper accordingly. \n\n## Q4: elaborate more on  Eq. 3\nWe will add more details and explanations for Eq. 3.  The equation is obtained from the derivative of a single-parameter PQC as done by [MNKF18]. Particularly this expression is based on Eq. 2 of this reference which connects the commutation with any Pauli word $P_j$ to parameter shifting as in Hadamard test:\n$$\n[P_j, \\rho] = i \\left[ U_j\\left( \\frac{\\pi}{2} \\right) \\rho U_j^\\dagger\\left( \\frac{\\pi}{2} \\right) - U_j\\left( -\\frac{\\pi}{2} \\right) \\rho U_j^\\dagger\\left( -\\frac{\\pi}{2} \\right) \\right]\n$$\nWe will add a short derivation in the text and, if space permits, a more detailed explanation in the appendix."}, {"review_id": "E1HnuKzd5i", "reviewer": "Reviewer_sJbZ", "summary": "This paper proposes a new framework for performing quantum gradient estimation in hybrid quantum-classical setups such as VQAs. The paper crucially identifies that the presence of symmetries in the Lie algebraic structure can exponentially reduce the sample complexity and number of measurements, while conceding at most a polynomial speedup during the classical post processing phase, in comparison to existing PSR based techniques in the literature. This uniquely positions the contributions of the paper as complementary to the existing literature on gradient estimation in hybrid setups.", "questions": "It is unclear to me when the framework proposed in this paper would be more beneficial in the context of the classical simulatibility results of [GLC+23]. If the observable $O$ does not have polynomial dimensionality in the number of qubits, does the shadow norm of $O$ still remain bounded? How do we compare the sample complexity and time complexity of the current paper with those of [GLC+23] and other classical simulatibility techniques?\n\n\n----\n\n**Note to authors:** I am extremely willing to improve my score if the authors provide a reasonable justification to the above question.", "limitations": "See above sections - weaknesses and questions for the limitations.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths\n----\n\nThe paper is extremely well written. The assumptions are reasonable, well studied in existing literature, and clearly stated. The theorem statements and the proofs are easy to read. The contributions are well placed in the context of existing results such as [WLW+24]. The Lie-algebraic Hadamard-test framework is of broad interest in the community in its own right.\n\nWeaknesses\n---\n\nIt has been known for some time that constraining the underlying Lie-algebraic structure paves the way for classical simultability results, for example see [GLC+23]. The paper does not do a good job of convincing the reader why one would still prefer to have hybrid frameworks for gradient estimation, given the cost of quantum resources involved. See the questions section for this one point of weakness that is not properly addressed.\n\nIn my opinion, the paper is devoid of any major weaknesses barring its lack of comparison with respect to classical simulatibility results.  Another minor squabble one might have is the lack of experimental results demonstrating that the proposed framework performs well in practice. Since I am a theorist myself, I lack the technical know-how to suggest incorporating reasonable experiments into the paper, and I will defer to the opinion of the other reviewers on this matter. However,  in my opinion, the theoretical contributions of this work are solid enough to merit a discussion for acceptance.\n\nThere are a few minor typos I list here:\n\n- Line 27: Extra \"the\" before convergence rates.\n- Line 30: The phrase \"each gradient can have an exponential sample complexity\" does not make sense. I assume the authors are referring to the sample complexity of **gradient estimation**.\n- Line 146: Extra \"the\" before phase estimation.\n- Line 151: Missing \"the\" before Hadamard test.\n- Line 481-482: There should be $D_i$s instead of $D_i$ in multiple places.", "was_revised": true, "final_justification": "The responses by the authors have addressed my main concern with the viability of the results. I have raised my score to reflect this opinion.", "rebuttal": "Thank you for your encouraging and thoughtful comments. We also appreciate your engagement with our work and a list of typos and other suggestions to improve the paper. Below, we address your questions and concerns. We hope that, upon reviewing our responses, you will consider raising your evaluation.\n\n\n\n## Comparison with [GLC+23]\nIn summary,  our work is complementary to [GLC+23] and offers distinct advantages in the following two scenarios:\n\n### **1. The input state $\\rho$ is not classically simulatable**\nThis arises, for example, when $\\rho$ is a physical quantum state obtained from an external process (e.g., quantum sensing) or generated by a unitary that does not have polynomial Lie dimensionality.\n\nWhile [GLC+23] relies on computing expectation values of the Lie algebra basis elements ($B_{\\alpha}^{(\\lambda)}$ in the reference) under $\\rho$, this is only efficient when certain classes of $\\rho$, including product states or stabilizer states. In a more general setting, such expectation values must be estimated on a quantum computer. A natural approach, for that matter, is shadow tomography.  However, this introduces a new limitation: **the shadow norm of the Lie basis elements must be bounded**, which might not be the case in practice.\n\n**Example 1 (Shadow norm blow-up for basis elements):** In Section III.C of [GLC+23], the authors construct a Lie algebra basis for a free-fermion system as shown in Eq. (23). One can verify that the shadow norm of these basis elements grows exponentially in the number of qubits. Hence,  our framework would be more favorable as we avoid estimating such expectations.\n\n### **2. The observable $O$ is not classically simulatable**\nThis occurs when $O$ does not lie in a Lie algebra of polynomial dimension. We expect significant (possibly exponential) separation from [GLC+23] when the observable: \n1. Does not have polynomial Lie dimensionality,\n2. Can be implemented in polynomial quantum time or measured efficiently on a quantum device, \n3. Has bounded shadow norm.\n\nWe will add a detailed comparison in the revised manuscript. The following example shows such an observable:\n\n**Example 2 (Low-rank observables vs Lie dimensionality):** Consider the observable used in **fidelity estimation**, $O=\\ketbra{\\phi}{\\phi}$, where $\\ket{\\phi}=e^{iH}\\ket{0}$ and $H$ is a Hamiltonian not admitting a polynomial Lie decomposition. Here, $O$ is a **low-rank observable** with bounded shadow norm, but exponential Lie dimensionality. \n\nIn general, low-rank observables will have low shadow norm and hence lead to lower sample complexity and are suitable for our approach.  \n\nThis addresses the reviewer’s question:\n>\"If the observable $O$ does not have polynomial dimensionality in the number of qubits, does the shadow norm of $O$ still remain bounded?\"\n\nThe answer is yes. In many relevant cases, particularly for low-rank or structured observables, the shadow norm remains bounded even when Lie dimensionality is not polynomial.\n\n\nThe second question regarding the sample complexity and time complexity is addressed below. \n\n## Time complexity Comparison\nAssuming  both $\\rho$ and $O$ are efficiently classically simulatable, our work and that of [GLC+23] have **similar (classical or quantum) time complexity**, scaling polynomially with the dimension of the Lie algebra  \n\nHowever, as noted above, our approach is more efficient (with potentially exponential improvements) in scenarios where:\n- $O$ does not belong to a low-dimensional Lie algebra but has bounded shadow norm, or\n- $\\rho$ is not classically simulatable, and the Lie basis elements have large shadow norm.\n\n\n## Sample Complexity Comparison\nWhile [GLC+23] does not explicitly analyze sample complexity, one could, in principle, use shadow tomography to achieve a similar sample complexity as in our case. However, this again introduces a dependency on the shadow norm of the Lie basis elements. \n\nIn contrast, as our approach directly targets gradient estimation, we can achieve logarithmic sample complexity by only requiring that $O$ has a bounded shadow norm. Thus, we expect improvements in sample complexity in certain regimes where classical simulation is not tractable.\n\nStudying [GLC+23] with shadow tomography and a combination of ideas from  [GLC+23] and our methodology are interesting future directions. \n \n## Why Hybrid Frameworks Remain Valuable?\nThis is an important question that we plan to address more clearly in the revised paper. We argue that the hybrid quantum-classical framework remains valuable in two main scenarios: \n1. When the input data is inherently quantum, generated from external hardware, and is not classically simulatable.\n2. When parts of the model, such as the observable $O$, are not classically simulable."}, {"review_id": "o8engrurcZ", "reviewer": "Reviewer_w9T8", "summary": "This paper introduces an efficient framework for gradient estimation in parameterized quantum circuits (PQCs) used in variational quantum algorithms (VQAs). While traditional methods such as finite differences and the parameter shift rule (PSR) suffer from inefficiencies and limited applicability, the proposed approach overcomes these limitations by leveraging the Lie algebraic structure of PQCs along with the Hadamard test. To achieve this, the authors derive an analytical expression for the gradient of a generic PQC using the differential of the matrix exponential map in Lie algebras. This expression represents the gradient as a linear combination of expectation values computable via Hadamard tests under certain constraints. Moreover, these expectation values can be efficiently estimated using shadow tomography, resulting in a logarithmic scaling of the number of measurement shots when the shadow norms of the observables are bounded, with the number of parameters and polynomial time complexity in both classical and quantum resources.", "questions": "I would like the authors to fix the minor points in the Strengths And Weaknesses part.", "limitations": "yes", "rating": 5, "confidence": 3, "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 a gradient estimation algorithm for VQAs with provably fewer requirements on the quantum resources in some realistic settings. Although I feel that similar ideas of encoding Pauli strings into binary representations have been proposed, the observation that this encoding enables efficient characterization of their commutation relations and works particularly well when the set of Pauli terms in the Hamiltonian is closed under commutation is essential. This observation further allows a finite and efficiently computable gradient representation. Even when this closure property does not hold, the paper proposes approximation strategies via truncation or Poisson sampling. Overall, I believe this work should be a natural fit for NeurIPS 2025. \n\nRegarding the weakness, I only have some minor comments that do not affect my overall evaluation. \n\n- I suggest the authors using the notation $n$ instead of $d$ to represent the system size (number of qubits). I think $d=2^n$ usually refers to the dimension of the Hilbert space. I notice that the authors also use $n$ for system size at line 103, maybe due to a typo.\n\n- I suggest the authors mentioning a recent work [Abbas et al, NeurIPS 2023]. In this work, a backpropagation algorithm for VQAs is provided based on another line of shadow tomography techniques (Actually, I think the shadow tomography technique in this submission should be called classical shadow). A comparison between this submission and the recent work mentioned should be helpful.\n\n- There is a typo in the equation below line 175: $b^2$ should be $b^1$.", "was_revised": true, "final_justification": "From my perspective, this is a technically solid work providing a gradient estimation algorithm for VQAs with provably fewer requirements on the quantum resources in some realistic settings. Although I feel that similar ideas of encoding Pauli strings into binary representations have been proposed, the observation that this encoding enables efficient characterization of their commutation relations and works particularly well when the set of Pauli terms in the Hamiltonian is closed under commutation is essential. This observation further allows a finite and efficiently computable gradient representation. Even when this closure property does not hold, the paper proposes approximation strategies via truncation or Poisson sampling. Overall, I believe this work should be a natural fit for NeurIPS 2025.", "rebuttal": "We thank the reviewer for their positive assessment and thoughtful feedback. We also appreciate the list of typos and other suggestions to improve the paper. We are glad that you find this work to be a good fit for NeurIPS 2025.\n\nWe will address the minor comments mentioned by the reviewer and add a brief discussion citing the suggested reference."}]

Author rebuttal:

Meta-review: (a) Summary of claims and findings:
The paper introduces a framework for efficient gradient estimation in parameterized quantum circuits (PQCs) by leveraging Lie algebraic structure together with the Hadamard test. Using the differential of the matrix exponential on Lie algebras, the gradient is expressed as a linear combination of expectation values that can be measured via Hadamard tests; the coefficients depend only on the circuit parameterization and are classically precomputable. When the set of generators closes to a polynomial‑dimensional Lie algebra (or its dynamical subalgebra), the method yields logarithmic dependence on the number of parameters for measurement shots via classical shadows, with polynomial classical and quantum time. For non‑closed settings, the paper proposes extensions based on computing the closure, truncation, and Poisson sampling. Theoretical bounds are provided; no experiments are reported.

(b) Strengths:

- Clear conceptual advance: ties Lie algebra structure to gradient estimability through Hadamard tests, yielding logarithmic shot complexity in the number of parameters under bounded shadow norms.
- Solid, readable theory: concrete decomposition of gradients, efficient coefficient computation, and clean use of shadow tomography to aggregate many required expectations.
- Practical guidance: identifies realistic families where closure or small dynamical subalgebras hold (e.g., Heisenberg‑type models, stabilizer Hamiltonians), and outlines approximations (truncation/Poisson sampling) when closure fails.
- Good positioning relative to prior work: explains complementarity to parameter‑shift rules and to classical simulatability results; articulates regimes where a hybrid approach remains necessary (non‑simulable input states or observables with bounded shadow norm but large Lie dimension).

(c) Limitations and remaining concerns:

- Applicability depends on Lie‑algebraic structure: closure (or small dynamical subalgebra) is restrictive for highly expressive/universal circuits; the method’s strongest guarantees target those structured regimes.
- No empirical validation: results are purely theoretical; while common for quantum‑theory papers, even small‑scale simulations or case studies would help accessibility.
- Clarity and presentation: reviewers noted notation issues and requested self‑contained resource theorems for Sections 3.3 and 5, clearer derivations (e.g., Eq. 3), and minor typos; these should be addressed in camera‑ready.
- Shadow tomography assumptions: benefits depend on bounded shadow norms; guidance on checking or ensuring these bounds in practice would strengthen the paper.

(d) Reasons for decision:

Despite scope limitations, the paper presents a novel and well‑argued framework with strong theoretical guarantees and a plausible path to practical impact in structured PQCs. The rebuttal addressed key concerns: it clarified when the closed/dynamical Lie algebra assumption holds, why hybrid advantages persist relative to classical simulatability, and how the approach extends beyond exact closure. Multiple reviewers updated to borderline‑accept or accept, and there is consensus that the theoretical contribution is solid and relevant to NeurIPS’s Optimization/Theory tracks. Given the value of the ideas and the constructive, specific revision plan, acceptance as a poster is warranted.

(e) Suggestions for camera‑ready:

Clarity and completeness:

- Provide a self‑contained theorem summarizing overall resource bounds for the closed‑algebra case (shots, quantum/classical time) and a companion theorem for the approximate cases (closure, truncation, Poisson sampling).
- Expand the derivation around Eq. 3 and include an intuitive pipeline diagram: parameterization → Lie decomposition → Hadamard‑test observables → classical‑shadows aggregation → gradient reconstruction.
- Unify notation (use n for qubits; avoid using i both as index and imaginary unit; fix b^2→b^1 typo; avoid reusing symbols). Add definitions for shadow norm and its role in sample complexity.

Positioning and scope:

- Add concrete examples where closure/dynamical subalgebra is polynomial (Heisenberg variants, stabilizer Hamiltonians), and one example where Lie dimension is large but observables have bounded shadow norm (e.g., low‑rank fidelity estimators).
- Include a short comparison to classical simulatability (e.g., GLC+23): when input states or observables are not classically simulable, and when shadow norms for basis elements blow up.
- Briefly cite and contrast with NeurIPS 2023 shadow‑based backpropagation work as suggested by reviewers.

Practical guidance:

- Provide a checklist to assess applicability: how to test/estimate closure or dynamical subalgebra size; heuristics for truncation/Poisson parameters; how to upper‑bound shadow norms in common settings.
- If space allows, add a small illustrative simulation (even on few qubits) to demonstrate reconstruction accuracy vs. shots and the impact of bounded shadow norms.
Decision: Accept (poster)