Hadamard Test is Sufficient for Efficient Quantum Gradient Estimation with Lie Algebraic Symmetries

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.

We will address the minor comments mentioned by the reviewer and add a brief discussion citing the suggested reference.

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.

Comparison with [GLC+23]

In summary,  our work is complementary to [GLC+23] and offers distinct advantages in the following two scenarios:

1. The input state $\rho$ is not classically simulatable

This 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.

While [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.

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.

2. The observable $O$ is not classically simulatable

This 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:

1. Does not have polynomial Lie dimensionality,
2. Can be implemented in polynomial quantum time or measured efficiently on a quantum device,
3. Has bounded shadow norm.

We will add a detailed comparison in the revised manuscript. The following example shows such an observable:

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.

In general, low-rank observables will have low shadow norm and hence lead to lower sample complexity and are suitable for our approach.

This addresses the reviewer’s question:

"If the observable $O$ does not have polynomial dimensionality in the number of qubits, does the shadow norm of $O$ still remain bounded?"

The 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.

The second question regarding the sample complexity and time complexity is addressed below.

Time complexity Comparison

Assuming 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

However, as noted above, our approach is more efficient (with potentially exponential improvements) in scenarios where:

• $O$ does not belong to a low-dimensional Lie algebra but has bounded shadow norm, or
• $\rho$ is not classically simulatable, and the Lie basis elements have large shadow norm.

Sample Complexity Comparison

While [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.

In 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.

Studying [GLC+23] with shadow tomography and a combination of ideas from [GLC+23] and our methodology are interesting future directions.  

Why Hybrid Frameworks Remain Valuable?

This 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:

1. When the input data is inherently quantum, generated from external hardware, and is not classically simulatable.
2. When parts of the model, such as the observable $O$, are not classically simulable.

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.

Below we present our brief reply to your questions.

Q1: Generalized Parameterizations Beyond Pauli Decomposition

The 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.

However, 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. We will clarify this point in the revised version of the paper.

Q2, 3: self-contained theorem statements

Thank you for the suggestion. We will revise the paper accordingly.

Q4: elaborate more on Eq. 3

We 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:

$$[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]$$

We will add a short derivation in the text and, if space permits, a more detailed explanation in the appendix.

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.

Q1: Generality of the results:

The 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).

On 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:

1. 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.
2. Approximation techniques discussed in Section 5 via Truncation and Poisson Sampling.

We 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].

Q2: Examples of realistic quantum systems closed under commutation:

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). This Hamiltonian takes the following form:

$$H=\sum_{i,j} (J_{x}X_{i}X_{j}+J_{y}Y_{i}Y_{j}+J_{z}Z_{i}Z_{j}),$$

where $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.

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: $H_{TC}=− J_e\sum_v A_v - J_m\sum_p B_p$ where ​$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.

Example 3: A realistic quantum system that is not closed under commutation but has a polynomial closure A concrete example discussed in the extended version of the paper is the transverse-field Ising model: $H=\sum_{i} Z_{i}Z_{i+1}+X_{i}$ While 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.

Q2: Regarding Numerical Results

We plan to explore numerical experiments of our results for a class of Hamiltonians with polynomial dimensionality as future work, including the following models:

• QAOA Hamiltonians for MAXCUT: We plan to demonstrate that even partial closure (e.g., commuting subsets) suffices for practical gains.
• 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.

Q3: Trade-off against existing methods

Existing 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.

In 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.

Q4: Extensions to more general Hamiltonians

Section 5 addresses extensions of our framework to handle circuits whose commutators do not form a closed group. We proposed two methods:

1. Truncation-based approximation, which limits the expansion to a manageable subset of terms,
2. Poisson sampling, a stochastic method for estimating gradients efficiently. Theorems 6 and 7 briefly highlight our analysis of such methods.

Q5: Shadow tomography

Shadow 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.

The 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.