A Locality-Aware Surrogate for Natural-Gradient Descent in Quantum Optimization

Variational quantum algorithms (VQAs) rely on gradient-based optimization over parameterized circuits whose loss landscape lives on a manifold of quantum states. Quantum natural gradient (QNG) accounts for this geometry through the quantum Fisher information matrix (QFIM). However, estimating the full QFIM is prohibitively expensive within practical quantum circuit shot budgets. Existing tractable approximations either discard inter-block couplings, as in block-diagonal QNG, or replace the QFIM with a measurement-induced classical Fisher surrogate, as in random natural gradient (RNG). We propose a locality-aware surrogate that targets the QFIM through its covariance representation in terms of propagated generators, retaining a structured subset of informative cross-parameter couplings while remaining practical to estimate under finite-shot budgets. Our construction combines three ingredients: weight-$k$ Pauli truncation to control estimation variance, support-overlap masking to exploit sparsity, and single-dataset classical-shadow estimation that reuses the same shadow dataset across all retained metric entries. Truncation level $k$ provides a bias--variance tradeoff: larger $k$ captures more of the propagated-generator structure but increases estimation cost, making it a budget-constrained design choice. Circuit parameters whose truncated generators remain nonzero form an active set receiving surrogate-QNG updates, while the rest follow standard gradient descent. We provide finite-shot concentration bounds for the shadow-estimated surrogate and convergence guarantees to a stationary neighborhood under standard smoothness assumptions. Experiments on variational quantum eigensolver (VQE) instances with local ans\"atze for Heisenberg and Ising spin chains show improved convergence per cumulative shot relative to SGD, Adam, block-diagonal QNG, and RNG baselines under finite-shot budgets, including on systems up to 16 qubits.