Query-Efficient Quantum Approximate Optimization via Graph-Conditioned Trust Regions

• URL: http://arxiv.org/abs/2604.24803v1
• Date: Mon, 27 Apr 2026 03:48:48 GMT
• Title: Query-Efficient Quantum Approximate Optimization via Graph-Conditioned Trust Regions
• Abstract summary: A graph neural network predicts a Gaussian distribution N(mu Sigma) over QAOA.<n>The learned distribution defines a search policy rather than only an initial estimate.<n>Relative to random restarts and the strongest learned point-prediction baseline, the method reduces the mean number of circuit evaluations from 343 and 85 to 45 +/- 7.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In low-depth implementations of the Quantum Approximate Optimization Algorithm (QAOA), the dominant cost is often the number of objective evaluations rather than circuit depth. We introduce a graph-conditioned trust-region method for reducing this query cost. A graph neural network predicts a Gaussian distribution N(mu, Sigma) over QAOA angles. The mean initializes a local optimizer, the covariance defines an ellipsoidal trust region that constrains the search, and the predicted uncertainty determines an instance-dependent evaluation budget. Thus the learned distribution defines a search policy rather than only an initial parameter estimate. Under explicit assumptions on local smoothness, curvature, calibration, and noise, we derive bounds on objective degradation within the trust region, lower bounds on gradient variance, preservation of expected objective ordering under depolarizing noise, and finite-sample coverage guarantees. We evaluate the method for MaxCut at depth p = 2 on Erdos-Renyi, 3-regular, Barabasi-Albert, and Watts-Strogatz graphs with n = 8-16 vertices. Relative to random restarts and the strongest learned point-prediction baseline, the method reduces the mean number of circuit evaluations from 343 and 85 to 45 +/- 7, while maintaining sampled approximation ratios within 3 percentage points of concentration-based heuristics. The method does not improve absolute approximation ratios; its advantage is reduced query cost at comparable solution quality. The predictive uncertainty is calibrated in the experiments, with ECE = 0.052 and Spearman correlation rho = 0.770, and the learned trust regions transfer to graph sizes not used during training. The results identify a low-depth, query-dominated regime in which graph-conditioned trust regions reduce the query cost of QAOA without modifying the ansatz.

Related papers

• Optimal Recovery Meets Minimax Estimation [20.84190812813031]
  The goal is to design a numerical algorithm to construct an approximation $hat f$ to $f$ in a prescribed norm.<n>This paper handles this issue and determines the noise-level-aware (NLA) minimax rates for Besov classes when error is measured in an $L_q$-norm.
  arXiv  Detail & Related papers  (2025-02-24T21:37:54Z)
• Learning minimal volume uncertainty ellipsoids [1.6795461001108096]
  We consider the problem of learning uncertainty regions for parameter estimation problems. Under the assumption of jointly Gaussian data, we prove that the optimal ellipsoid is centered around the conditional mean. In more practical cases, we propose a differentiable optimization approach for approximately computing the optimal ellipsoids.
  arXiv  Detail & Related papers  (2024-05-03T19:11:35Z)
• Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Time [45.72323731094864]
  In this paper, we study the optimality gap between two-layer ReLULU networks regularized with weight decay and their convex relaxations. Our study sheds new light on understanding why local methods work well.
  arXiv  Detail & Related papers  (2024-02-06T01:29:35Z)
• Robust Non-parametric Knowledge-based Diffusion Least Mean Squares over Adaptive Networks [12.266804067030455]
  The proposed algorithm leads to a robust estimation of an unknown parameter vector in a group of cooperative estimators. Results show the robustness of the proposed algorithm in the presence of different noise types.
  arXiv  Detail & Related papers  (2023-12-03T06:18:59Z)
• Robust Stochastic Optimization via Gradient Quantile Clipping [6.2844649973308835]
  We introduce a quant clipping strategy for Gradient Descent (SGD) We use gradient new outliers as norm clipping chains. We propose an implementation of the algorithm using Huberiles.
  arXiv  Detail & Related papers  (2023-09-29T15:24:48Z)
• Sampling from Gaussian Process Posteriors using Stochastic Gradient Descent [43.097493761380186]
  gradient algorithms are an efficient method of approximately solving linear systems. We show that gradient descent produces accurate predictions, even in cases where it does not converge quickly to the optimum. Experimentally, gradient descent achieves state-of-the-art performance on sufficiently large-scale or ill-conditioned regression tasks.
  arXiv  Detail & Related papers  (2023-06-20T15:07:37Z)
• Scalable Gaussian-process regression and variable selection using Vecchia approximations [3.4163060063961255]
  Vecchia-based mini-batch subsampling provides unbiased gradient estimators. We propose Vecchia-based mini-batch subsampling, which provides unbiased gradient estimators.
  arXiv  Detail & Related papers  (2022-02-25T21:22:38Z)
• Learning to Estimate Without Bias [57.82628598276623]
  Gauss theorem states that the weighted least squares estimator is a linear minimum variance unbiased estimation (MVUE) in linear models. In this paper, we take a first step towards extending this result to non linear settings via deep learning with bias constraints. A second motivation to BCE is in applications where multiple estimates of the same unknown are averaged for improved performance.
  arXiv  Detail & Related papers  (2021-10-24T10:23:51Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sampling (AIS) and related algorithms are highly effective tools for marginal likelihood estimation. Differentiability is a desirable property as it would admit the possibility of optimizing marginal likelihood as an objective. We propose a differentiable algorithm by abandoning Metropolis-Hastings steps, which further unlocks mini-batch computation.
  arXiv  Detail & Related papers  (2021-07-21T17:10:14Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  It is essential to theoretically guarantee that algorithms provide small objective residual with high probability. Existing methods for non-smooth convex optimization have complexity bounds with dependence on confidence level. We propose novel stepsize rules for two methods with gradient clipping.
  arXiv  Detail & Related papers  (2021-06-10T17:54:21Z)
• Amortized Conditional Normalized Maximum Likelihood: Reliable Out of Distribution Uncertainty Estimation [99.92568326314667]
  We propose the amortized conditional normalized maximum likelihood (ACNML) method as a scalable general-purpose approach for uncertainty estimation. Our algorithm builds on the conditional normalized maximum likelihood (CNML) coding scheme, which has minimax optimal properties according to the minimum description length principle. We demonstrate that ACNML compares favorably to a number of prior techniques for uncertainty estimation in terms of calibration on out-of-distribution inputs.
  arXiv  Detail & Related papers  (2020-11-05T08:04:34Z)
• Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
  We prove that our algorithms require a number of evaluations gradient independent of training set size and number of parameters. Experiments on MNIST and ImageNet confirm the theoretical scaling of our algorithms, which are 9--36 times more efficient than full-batch methods.
  arXiv  Detail & Related papers  (2020-10-12T17:41:44Z)
• Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds [72.63031036770425]
  We propose differentially private (DP) algorithms for bound non-dimensional optimization. We demonstrate two popular deep learning methods on the empirical advantages over standard gradient methods.
  arXiv  Detail & Related papers  (2020-06-24T06:01:24Z)

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.