Analysis of Hessian Scaling for Local and Global Costs in Variational Quantum Algorithm

• URL: http://arxiv.org/abs/2602.00783v1
• Date: Sat, 31 Jan 2026 15:49:23 GMT
• Title: Analysis of Hessian Scaling for Local and Global Costs in Variational Quantum Algorithm
• Authors: Yihan Huang, Yangshuai Wang,
• Abstract summary: We quantify the entrywise resolvability of the Hessian for Variational Quantum Algorithms.<n>We show two distinct scaling regimes that govern the sample complexity required to resolve Hessian entries against shot noise.
• Score: 0.42970700836450487
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: Barren plateaus are typically characterized by vanishing gradients, yet the feasibility of curvature-based optimization fundamentally relies on the statistical resolvability of the Hessian matrix. In this work, we quantify the entrywise resolvability of the Hessian for Variational Quantum Algorithms at random initialization. By leveraging exact second-order parameter-shift rules, we derive a structural representation that reduces the variance of Hessian entries to a finite covariance quadratic form of shifted cost evaluations. This framework reveals two distinct scaling regimes that govern the sample complexity required to resolve Hessian entries against shot noise. For global objectives, we prove that Hessian variances are exponentially suppressed, implying that the number of measurement shots must scale as $O(e^{αn})$ with the number of qubits $n$ to maintain a constant signal-to-noise ratio. In contrast, for termwise local objectives in bounded-depth circuits, the variance decay is polynomial and explicitly controlled by the backward lightcone growth on the interaction graph, ensuring that curvature information remains statistically accessible with $O(\mathrm{poly}(n))$ shots. Extensive numerical experiments across varying system sizes and circuit depths demonstrate these theoretical bounds and the associated sampling costs. Our results provide a rigorous criterion for the computational tractability of second-order methods at initialization.

Related papers

• Stability and Generalization of Push-Sum Based Decentralized Optimization over Directed Graphs [55.77845440440496]
  Push-based decentralized communication enables optimization over communication networks, where information exchange may be asymmetric.<n>We develop a unified uniform-stability framework for the Gradient Push (SGP) algorithm.<n>A key technical ingredient is an imbalance-aware generalization bound through two quantities.
  arXiv  Detail & Related papers  (2026-02-24T05:32:03Z)
• Bregman geometry-aware split Gibbs sampling for Bayesian Poisson inverse problems [8.115032818930457]
  We propose a novel framework for solving inverse problems by a Monte Carlo sampling algorithm.<n>We show that the method achieves competitive performance in terms of reconstruction quality.
  arXiv  Detail & Related papers  (2025-11-15T15:27:31Z)
• Estimation of Toeplitz Covariance Matrices using Overparameterized Gradient Descent [1.7188280334580195]
  We revisit Toeplitz covariance estimation through the lens of simple descent (GD)<n>We show that when $K = P$, GD may converge to suboptimal solutions.<n>We propose an accelerated GD variant with separate learning rates for amplitudes and frequencies.
  arXiv  Detail & Related papers  (2025-11-03T14:07:53Z)
• Harmonic Path Integral Diffusion [0.4527270266697462]
  We present a novel approach for sampling from a continuous multivariate probability distribution, which may either be explicitly known (up to a normalization factor) or represented via empirical samples. Our method constructs a time-dependent bridge from a delta function centered at the origin of the state space at $t=0$, transforming it into the target distribution at $t=1$. We contrast these algorithms with other sampling methods, particularly simulated and path integral sampling, highlighting their advantages in terms of analytical control, accuracy, and computational efficiency.
  arXiv  Detail & Related papers  (2024-09-23T16:20:21Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a suitable space to model functions by neural networks. In this paper, we study a suitable function space for over- parameterized two-layer neural networks with bounded norms.
  arXiv  Detail & Related papers  (2024-04-29T15:04:07Z)
• Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
  We consider clipped optimization problems with heavy-tailed noise with structured density. We show that it is possible to get faster rates of convergence than $mathcalO(K-(alpha - 1)/alpha)$, when the gradients have finite moments of order. We prove that the resulting estimates have negligible bias and controllable variance.
  arXiv  Detail & Related papers  (2023-11-07T17:39:17Z)
• GRAPE optimization for open quantum systems with time-dependent decoherence rates driven by coherent and incoherent controls [77.34726150561087]
  The GRadient Ascent Pulse Engineering (GRAPE) method is widely used for optimization in quantum control. We adopt GRAPE method for optimizing objective functionals for open quantum systems driven by both coherent and incoherent controls. The efficiency of the algorithm is demonstrated through numerical simulations for the state-to-state transition problem.
  arXiv  Detail & Related papers  (2023-07-17T13:37:18Z)
• Robust scalable initialization for Bayesian variational inference with multi-modal Laplace approximations [0.0]
  Variational mixtures with full-covariance structures suffer from a quadratic growth due to variational parameters with the number of parameters. We propose a method for constructing an initial Gaussian model approximation that can be used to warm-start variational inference.
  arXiv  Detail & Related papers  (2023-07-12T19:30:04Z)
• Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimization [50.83356836818667]
  gradient Langevin Dynamics is one of the most fundamental algorithms to solve non-eps optimization problems. In this paper, we show two variants of this kind, namely the Variance Reduced Langevin Dynamics and the Recursive Gradient Langevin Dynamics.
  arXiv  Detail & Related papers  (2022-03-30T11:39:00Z)
• Error-Correcting Neural Networks for Two-Dimensional Curvature Computation in the Level-Set Method [0.0]
  We present an error-neural-modeling-based strategy for approximating two-dimensional curvature in the level-set method. Our main contribution is a redesigned hybrid solver that relies on numerical schemes to enable machine-learning operations on demand.
  arXiv  Detail & Related papers  (2022-01-22T05:14:40Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  We use kernel Hilbert spaces for estimating the value function of an infinite-horizon discounted Markov reward process. We derive a non-asymptotic upper bound on the error with explicit dependence on the eigenvalues of the associated kernel operator. We prove minimax lower bounds over sub-classes of MRPs.
  arXiv  Detail & Related papers  (2021-09-24T14:48:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.