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

Molena Huynh · arXiv:2604.24803 · cross submission, quant-ph (cs.LG primary) · score 9/10

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.

Executive summary

UQ-QAOA is a query-cost reduction framework that wraps a learned graph-conditioned Gaussian over QAOA angles around a local optimiser. A GIN with Laplacian positional encodings predicts both a mean (initialisation) and an ellipsoidal Mahalanobis covariance (search region), and the trace of the covariance further sets an instance-dependent number of evaluations. On MaxCut (p=2, n=8-16) the method cuts mean circuit evaluations from 343 (random restarts) and 85 (the best learned point baseline) to 45 ± 7 at essentially equal approximation ratio. The paper backs this with a battery of conditional theorems (objective degradation, gradient anti-concentration, depolarising-noise ordering, conformal coverage) and an ablation that isolates the contribution of distributional vs. point prediction.

Main contribution

The paper reframes warm-starting as a search policy, not just an initialisation. The learned Gaussian (a) initialises the local search, (b) defines a hard ellipsoidal trust region in QAOA-angle space that is enforced by projection during the inner optimiser's step, and (c) controls how many circuit evaluations are spent: instances whose covariance trace is large (high uncertainty) are allotted more queries, low-uncertainty instances fewer. The composite of these three uses of one prediction is what the paper calls UQ-QAOA. The conditional guarantees (Section V) connect the predicted variance directly to bounds on suboptimality within the trust region and to preservation of ordering under depolarising noise.

Key theorems / results / algorithms

Definition (Trust region, Sec. IV): a Mahalanobis ball M_alpha = { theta : (theta-mu)^T Sigma^{-1} (theta-mu) <= chi^2_{2p}(alpha) } around the predicted mean.
Proposition (Local Lipschitz regularity): the QAOA objective is locally L-Lipschitz on the trust region under standard smoothness of the cost Hamiltonian.
Theorem (Lower bound on objective within trust region): with high probability, objective degradation versus the predicted mean is bounded by a function of the covariance eigenvalues — small Sigma = small worst-case loss.
Theorem (Local gradient anti-concentration): within the trust region, gradient variance is lower-bounded so the inner optimiser does not stall — directly relevant to barren-plateau concerns.
Theorem (Best-of-K guarantee): for K samples drawn from the predicted Gaussian, the expected best objective concentrates as a function of trust-region volume.
Theorem (Adaptive-allocation guarantee under calibration): if the predicted variance is calibrated and difficulty is monotone in variance, the per-instance evaluation budget is provably matched to required effort.
Proposition (Finite-sample conformal coverage): standard conformal-prediction bounds extend to the QAOA-angle predictor.
Theorem (Preservation of expected ordering under depolarizing noise): noisy expectation values preserve the ordering of trust-region candidates, so the policy is robust to NISQ depolarisation.

Detailed walkthrough

The architecture (Sec. IV) is a Graph Isomorphism Network with Laplacian positional encodings; for each graph instance G it outputs a mean vector mu(G) and a covariance Sigma(G) over the 2p QAOA angles. Training uses a Wasserstein-regularised loss against an empirical distribution of high-quality angles per instance, plus a contrastive metric-learning term so that graphs with similar QAOA landscapes get similar embeddings (Sec. IV.B–IV.C).

The inference loop (Algorithm in Sec. IV.D–IV.E) is: (1) the GIN emits N(mu, Sigma) for the test graph; (2) trace(Sigma) maps through a calibrated rule to a sample budget K and a refinement budget T_base; (3) K samples are drawn from the Gaussian, evaluated on the QAOA circuit, and the best is taken as the seed; (4) a local optimiser refines from that seed, but every step is projected back onto M_alpha so the search never leaves the trust region. Total cost is K + T evaluations, vs. the hundreds typical of random restarts.

The theoretical core (Sec. V) is the bridge between the geometric quantity (trust-region volume, equivalently det(Sigma)) and the operational quantities the user cares about. The local Lipschitz regularity proposition gives the smoothness assumption needed for the trust-region bound; the ordering-preservation theorem under depolarisation handles the noise concern; the conformal-coverage proposition gives the calibration needed for the adaptive-allocation theorem to apply.

Empirically (Sec. VI) at n=14, p=2, 48 test instances per family across four graph families: UQ-QAOA reaches sampled approximation ratio 0.94 ± 0.01 with 45 ± 7 evaluations, vs. 343 (random init) and 85 (GNN point baseline) for ratios in [0.91, 0.95]. Cross-size generalisation (Table III, Fig. 4) trains only at n=14 but evaluates at n=8,10,12,16 and retains 4-7x speedup over random initialisation throughout. Per-family analysis (Sec. VI.E) shows uniform speedup across Erdős-Rényi, 3-regular, Barabási-Albert, and Watts-Strogatz, with leave-one-family-out generalisation (Sec. VI.F) confirming cross-family transfer at modest cost.

The calibration analysis (Sec. VI.J) reports ECE = 0.052 with 10 decile bins and Spearman rho = 0.770 between predicted variance and actual difficulty — strong evidence that the variance is meaningful and not just an internal regularisation artefact. The ablation (Sec. VI.G, Table V) isolates the trust-region projection: removing it (point prediction only) recovers the GNN baseline numbers, confirming that the policy effect, not better initialisation alone, drives the savings.

The shot-noise simulation (Sec. VI.K) repeats the experiments with realistic measurement budgets and confirms the savings persist; the discussion (Sec. VII) is careful to note that absolute approximation ratios are not improved — the contribution is strictly query-cost reduction at fixed quality.

Figures

Figure 1. Median wall-clock runtime at n=14 on a logarithmic scale (UQ-QAOA vs. random restarts and learned baselines).

Figure 2. Mean number of circuit evaluations at n=14.

Figure 3. Efficiency-adjusted quality at n=14 — sampled best-bitstring ratio per 100 circuit evaluations.

Figure 4. Speedup over random initialisation across graph sizes — transfer beyond the n=14 training size.

Figure 5. Reduction in circuit evaluations relative to random initialisation at n=14.

Figure 6. Reliability diagram showing how predicted uncertainty maps to actual loss — calibration of the GIN predictor.

Figure 10. Expected calibration error (ECE) diagram with 10 decile bins. Observed ECE = 0.052.

Figure 11. Adaptive budget allocation: how the per-instance evaluation budget tracks predicted uncertainty.

Citations to Yuan's papers

No direct citation to any of Y1–Y6 found in bibliography.

Overlap with Y1–Y6

Y1. Direct method overlap. Y1's iterative warm-start prepares a high-quality seed state via measurement of a previous QAOA layer; UQ-QAOA prepares a high-quality seed and a constraint region via a learned distribution. Both treat warm-starting as more than a single-point initialisation, but Y1's mechanism is intrinsic to the quantum circuit while this paper's is a classical surrogate.

Y3. Direct method overlap. Y3 found that dual annealing + layerwise optimisation was the most robust optimiser for QAOA on the DGMVP portfolio. UQ-QAOA fits the same axis: a structured search policy beats unstructured local search at a fixed query budget. The paper's ECE/calibration analysis is the kind of diagnostic Y3-style end-to-end studies would benefit from when comparing optimisers.

Y4. Light scope overlap only. Y4's ADMM hybrid is structurally different (no learned predictor, no QAOA) but shares the philosophy of allocating a fixed quantum query budget intelligently across iterations.

Recommended action for Yuan

Read deeper. Section V is unusually careful for a QAOA-with-ML paper — the trust-region bound + conformal coverage + ordering-under-depolarisation triple is a useful template for arguing about Y3-style end-to-end pipelines.
Adapt for the DGMVP portfolio (Y3). Train a graph-conditioned predictor over QAOA angles for portfolio QUBO instances and report query-cost reductions in the same noise regimes Y3 already characterised. The cross-size generalisation result suggests this should transfer well across asset-universe sizes.
Cite in next QAOA-warm-start draft. The framing of "policy, not initialisation" is closer to Y1's iterative warm-start picture than the standard "good init" framing — citing this paper sharpens the contrast.