Efficient Quantum Gradient and Higher-order Derivative Estimation via Generalized Hadamard Test

Hanrui Wang, Dantong Li, Dikshant Dulal, Mykhailo Ohorodnikov, Hanrui Wang 0002, Yongshan Ding

Abstract

Variational Quantum Algorithms (VQAs) are a cornerstone of the Noisy Intermediate-Scale Quantum (NISQ) era, yet their performance is often limited by the high computational cost and noise sensitivity of gradient estimation. This paper presents a novel framework for efficient quantum differentiation. By introducing the Flexible Hadamard Test (FHT) and a $k$-fold variant, the authors enable the calculation of gradients and higher-order derivatives with significantly reduced circuit complexity. Furthermore, the proposed Quantum Automatic Differentiation (QAD) framework adaptively optimizes the choice of gradient estimation methods for each parameter. Experimental results across various benchmarks, including quantum neural networks and optimization tasks, show up to a 9× improvement in convergence speed.

Introduction

In the NISQ era, VQAs like the Variational Quantum Eigensolver (VQE) and the Quantum Approximate Optimization Algorithm (QAOA) rely on a hybrid quantum-classical loop. A classical optimizer iteratively updates the parameters of a quantum circuit to minimize a cost function. The efficiency of this process hinges on the accurate and fast estimation of the gradient—the derivative of the cost function with respect to the circuit parameters.

Current methods, such as the Parameter Shift Rule (PSR) and the standard Hadamard Test (HT), face significant challenges. PSR is limited to specific gate types, while HT often requires additional ancilla qubits and complex controlled operations that are highly susceptible to noise in current hardware.

Methodology

Flexible and Reversed Hadamard Tests

The researchers propose the Flexible Hadamard Test (FHT), which leverages the mathematical symmetry between the gate generator and the observable in the gradient formula. In standard gradient estimation, the observable is fixed. FHT allows for "role reversal," where the roles of the generator and observable are swapped to minimize measurement costs.

Specifically, the Reversed Hadamard Test (RHT) is advantageous when the gate generator is simpler to group into fewer measurements than the observable. This flexibility allows developers to choose the configuration that minimizes circuit depth or the number of required "shots."

Comparison of standard, direct, and reversed Hadamard Test variants for gradient estimation.

Higher-Order Derivatives and $k$-fold HT

Estimating higher-order derivatives (like the Hessian) is typically exponentially expensive, requiring $2^k$ circuit executions for a $k$-th order derivative. The authors introduce a $k$-fold Hadamard Test that utilizes $k$ ancilla qubits to estimate these derivatives in a single quantum circuit, potentially overcoming the "curse of dimensionality" for sophisticated second-order optimizers.

Quantum Automatic Differentiation (QAD)

The Quantum Automatic Differentiation (QAD) framework serves as an intelligent orchestration layer. Instead of applying a single gradient method globally, QAD analyzes the hardware's noise profile and the specific properties of each gate to select the most efficient method (e.g., PSR vs. RHT) for every individual parameter.

The QAD Pipeline integrates derivatives evaluation with hardware-aware method selection to accelerate convergence.

Experimental Evaluation and Results

The methods were benchmarked on tasks including Quantum-Assisted Quantum Compilation (QAQC), Quantum Neural Networks (QNN) using the Iris dataset, and QAOA for MaxCut on IBM quantum devices (ibm_lagos and ibm_cairo).

Key findings include:

  • Significant Speedups: Reversed methods achieved an $O(N)$ factor improvement in circuit executions for compilation tasks.
  • Accelerated Convergence: The QAD framework demonstrated a 9× faster convergence in QNN training compared to the standard Parameter Shift Rule.
  • Noise Resilience: "Direct" versions of the tests, which avoid ancilla qubits and the associated high-error SWAP gates, showed superior fidelity on real noisy hardware despite requiring more runs.

Conclusion

This work provides a comprehensive toolkit for making quantum optimization more practical on NISQ devices. By "flipping the script" on how gradients are measured and introducing adaptive, hardware-aware selection through QAD, the researchers have paved the way for more efficient training of variational circuits. Future work may involve integrating these techniques with classical shadows to further reduce measurement overhead.

Citation: Li, D., et al. (2024). Efficient Quantum Gradient and Higher-order Derivative Estimation via Generalized Hadamard Test. arXiv:2408.05406v1 [quant-ph].

Summary updated

Abstract

In the context of Noisy Intermediate-Scale Quantum (NISQ) computing, parameterized quantum circuits (PQCs) are a promising paradigm for quantum sensing, optimal control, optimization, and machine learning on near-term quantum hardware. Gradient-based methods are crucial for analyzing PQCs and offer significant advantages in the convergence rates of Variational Quantum Algorithms (VQAs) compared to gradient-free methods. However, existing gradient estimation techniques-such as Finite Difference, Parameter Shift Rule, Hadamard Test, and Direct Hadamard Test-can yield suboptimal circuits for certain PQCs. To address these limitations, we introduce the Flexible Hadamard Test, which can invert the roles of ansatz generators and observables in first-order gradient estimation, enabling the use of measurement optimization techniques to improve circuit efficiency. For higher-order derivatives, we propose the <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$k$</tex>-fold Hadamard Test, which evaluates higher-order partial derivatives using a single quantum circuit. Additionally, we present Quantum Automatic Differentiation (QAD)-a unified gradient estimation framework that adaptively selects the most efficient method for each parameter in a PQC, departing from the standard practice of using a single method uniformly. Through extensive numerical experiments, we demonstrate that our proposed methods yield up to a linear-factor reduction in circuit execution cost for real VQA applications. These advances accelerate quantum algorithm training and provide practical utility in the NISQ era.
BibTeX
@misc{wang2024efficient,
  author = {Hanrui Wang and Dantong Li and Dikshant Dulal and Mykhailo Ohorodnikov and Hanrui Wang and Yongshan Ding},
  title = {{Efficient Quantum Gradient and Higher-order Derivative Estimation via Generalized Hadamard Test}},
  year = {2024},
  eprint = {2408.05406},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2408.05406},
}
Figure