Shot-Efficient ADAPT-VQE via Reused Pauli Measurements and Variance-Based Shot Allocation

Technical Summary: Shot-Efficient ADAPT-VQE via Reused Pauli Measurements and Variance-Based Shot Allocation

Problem Statement
The Adaptive Variational Quantum Eigensolver (ADAPT-VQE) is a leading algorithm for the Noisy Intermediate-Scale Quantum (NISQ) era, offering advantages over traditional VQE by adaptively constructing ansatz circuits to reduce depth and mitigate barren plateaus. However, ADAPT-VQE faces a critical bottleneck: a high quantum measurement (shot) overhead. This overhead stems from two primary sources within each iteration: (1) the optimization of variational parameters for the current ansatz and (2) the evaluation of operator gradients to select the next operator to add to the ansatz. As the number of iterations increases, the cumulative shot count becomes prohibitive, limiting the algorithm's scalability for complex molecular systems.

Methodology
The authors propose an integrated strategy to reduce shot requirements through two distinct but complementary techniques:

1. Reused Pauli Measurements:
   The authors exploit the structural overlap between the Hamiltonian ($\hat{H}$) and the gradient observables ($[\hat{H}, \hat{A}_k]$). In standard ADAPT-VQE, the gradient calculation for iteration $n+1$ requires measuring the commutator of the Hamiltonian and candidate operators. The proposed method observes that the quantum state $|\psi^{(n)}\rangle$ used for the Hamiltonian expectation value in iteration $n$ is identical to the state $|\psi^{((n+1)-1)}\rangle$ used for the gradient calculation in the subsequent iteration.

   • Mechanism: The algorithm identifies Pauli strings common to both the Hamiltonian decomposition and the gradient commutator decomposition.
   • Implementation: Measurement outcomes (expectation values) obtained during the final VQE parameter optimization of iteration $n$ are stored and reused for the corresponding terms in the gradient calculation of iteration $n+1$.
   • Grouping: This is combined with Qubit-Wise Commutativity (QWC) grouping to maximize the number of simultaneously measurable terms, ensuring that reused measurements are valid for the shared eigenbasis.

2. Variance-Based Shot Allocation:
   The authors extend variance-based shot allocation techniques, previously applied primarily to Hamiltonian expectation values, to include gradient measurements.

   • Strategies: Two specific allocation methods are employed:
     • Variance-Minimized Shot Assignment (VMSA): Allocates shots to minimize the total variance of the energy estimator for a fixed total shot budget.
     • Variance-Preserved Shot Reduction (VPSR): Reduces the total shot budget while maintaining the variance below a specific target threshold $\delta$.
   • Implementation: An initial subset of shots ($N_0$) is used to estimate the empirical variance of each commuting clique (group of Pauli strings). The remaining shots are then distributed proportionally to these variances. This is applied to both the Hamiltonian measurement (for energy) and the gradient measurement (for operator selection).

Key Contributions

• Novel Integration: This work is the first to explore the combined approach of reusing Pauli measurements across ADAPT-VQE iterations and applying variance-based shot allocation to both Hamiltonian and gradient measurements simultaneously.
• Algorithmic Modification: The authors present a modified ADAPT-VQE workflow (Algorithm 1) that incorporates a "Pauli-reused measurement protocol" and dynamic shot allocation, significantly altering the standard measurement cost structure.
• Operator Pool Agnosticism: The study validates the strategy across four different operator pools (Fermionic, Qubit, Qubit-Excitation, and Coupled Exchange Operator), demonstrating the robustness of the approach regardless of the specific ansatz construction pool.

Results
Numerical simulations were conducted on molecular systems ranging from $H_2$ (4 qubits) to $N_2H_4$ (16 qubits) using statevector and shot-based simulators (Qiskit Aer).

• Measurement Reuse Efficiency:

  • Compared to a naive full measurement scheme, using measurement grouping (QWC) alone reduced average shot usage to 38.59%.
  • Combining measurement grouping with the reuse protocol further reduced average shot usage to 32.29%.
  • The reuse strategy consistently reduced shot requirements across all tested molecules and operator pools, with savings increasing for larger molecules requiring more ADAPT iterations.

• Variance-Based Allocation Efficiency:

  • For the $H_2$ molecule, variance-based allocation reduced the shots required to reach chemical accuracy by 6.71% (VMSA) and 43.21% (VPSR) compared to uniform distribution.
  • For the $LiH$ molecule, reductions were 5.77% (VMSA) and 51.23% (VPSR).
  • The VPSR method proved particularly effective, achieving competitive accuracy with the fewest cumulative shots.

• Noise Resilience:

  • Simulations under varying noise levels ($p = 0.00001$ to $0.001$) showed that while high noise levels ($p=0.001$) prevented all methods from reaching chemical accuracy, the variance-based methods (VMSA and VPSR) maintained comparable accuracy to uniform methods with fewer cumulative shots.

Significance and Claims
The paper claims that these strategies represent a meaningful step toward practical quantum simulations in the NISQ era by directly addressing the measurement bottleneck of ADAPT-VQE. The authors emphasize that:

• The proposed methods significantly reduce the number of shots needed to achieve chemical accuracy while maintaining result fidelity.
• The classical computational overhead introduced by the reuse protocol is minimal, as Pauli string analysis is performed only once during the initial setup.
• While the work focuses on ADAPT-VQE, the approaches are applicable to other adaptive algorithms (e.g., ADAPT-QAOA).
• The study acknowledges that while noise simulations were performed, future work is needed to evaluate these methods on real quantum hardware noise profiles and to explore larger molecular systems.

The authors conclude that optimizing measurement costs is essential for the efficient computation of quantum algorithms when quantum resources are limited, and their integrated approach offers a viable path to mitigating the high shot overhead inherent in adaptive variational algorithms.